External-memory algorithms organise computation around the cost of moving data between a limited fast memory and a larger storage system. They are useful when a dataset does not fit in memory, or when repeatedly fetching scattered data costs more than the arithmetic performed on it. Their central design question is simple: how much useful work can we finish with each block that we bring into memory?
The gold standard is a correct answer, an explicit memory budget, and a defensible count of reads, writes and intermediate data. A method that performs fewer comparisons can still be slower if it causes many more transfers. This guide explains scans, external merge sorting, wide search trees, batching and locality through calculations you can reproduce, then shows how to test whether the model describes a real workload.
The numerical cases are constructed examples, not hardware benchmarks. Follow the Gold Standard master, the Education parent and the How X Works hub for the wider collection. Here, external memory means storage outside the model’s fast working memory; it does not refer to human memory aids.
Choose your external-memory algorithms route
Chapters 1–3: Understand the cost model
Chapters 7–9: Choose access patterns
Chapters 10–12: Build and diagnose
Chapter index
Understand the cost model · Chapters 1–3
1. Start with the journey of a record
Sort and search · Chapters 4–6
4. Sort data that cannot fit in memory
Choose access patterns · Chapters 7–9
7. Decide between an index and a scan
Build and diagnose · Chapters 10–12
10. Improve locality through layout
Transfer and continue · Chapters 13–14
Why moving data changes the algorithm
Imagine a file containing a billion transaction records. The task is to compute a total for every account. Reading each record once is unavoidable if every record can affect the answer. But the order in which records are visited, and the state retained between visits, can change the number of storage operations enormously. Reopening a distant part of the file for every account is a different algorithm from scanning the file in order.
A processor normally works on data already available in its memory hierarchy. A request for absent data must bring it closer before the useful computation can proceed. The physical hierarchy may contain caches, main memory and storage devices. A mathematical model simplifies that hierarchy into levels so that we can reason about a particular expensive boundary.
This simplification is useful only when its units are clear. A block might represent a storage page or a cache line, depending on the analysis. One must not use a disk-page block size while interpreting the predicted transfers as CPU cache misses. The same design principle can apply at both boundaries, but the numerical model must be rebuilt for each.
Specify the answer before optimising access
For account totals, decide whether records can repeat, whether corrections replace or reverse earlier transactions, and whether the output must be sorted by account. Those decisions determine what information may be discarded and whether intermediate results can be combined. Efficiently summing duplicate records twice is still wrong if the task requires deduplication.
Also decide when the result must be available. A nightly batch can reorder millions of records before answering. An interactive lookup may need one answer immediately. External-memory thinking applies to both, but a batch-friendly solution can violate an interactive deadline even while achieving excellent overall throughput. Performance belongs to a specified task, not to a data structure’s name.
A two-level model
Let N be the number of records, M the number that fit in fast working memory, and B the number transferred together in one block. The simple external-memory model charges for transfers between the two levels. Arithmetic on resident data is not the principal cost being counted. Real execution still pays for arithmetic, so the model is a lens rather than a complete stopwatch.
Assume fixed-size records for the first calculations. If a record occupies 32 bytes and a block contains 4,096 bytes with no overhead, one block holds 128 records. If a page has headers or records have variable lengths, that quotient no longer describes the usable capacity. Round down when estimating what fits; round up when estimating how many blocks must be fetched.
Suppose a working-memory budget is 1,024 records and blocks contain 64 records. That allows sixteen blocks in total. It does not allow sixteen input buffers plus an output buffer, a selection structure and the program’s bookkeeping. Every retained object consumes part of the same budget unless the model explicitly provides separate space.
Separate logical and physical costs
A logical request for a block may be satisfied by an existing cache. Conversely, one logical update may eventually cause more than one physical write because the system logs changes, maintains metadata or rewrites a larger storage unit. State which layer is measured. Do not compare logical block requests in one experiment with physical device operations in another.
The traditional model often treats block reads and writes equally. Some systems make that inappropriate. It can then be useful to retain separate counts R and W and evaluate a weighted cost such as R + ωW for a stated write weight ω. The weight is a modelling assumption or a measured ratio, not a universal constant. Keeping the counts separate makes it possible to revisit the conclusion when the storage system changes.
A complete arithmetic example
Consider 10,000 fixed-size records stored contiguously in blocks of 128 records. Starting at a block boundary, a complete scan reads ceil(10,000/128) = 79 blocks. Seventy-eight full blocks hold 9,984 records; the last block contains sixteen useful records. The algorithm must know the logical length so that unused bytes in that final block are not treated as additional input.
Now compare a deliberately unfavourable layout: each useful record occupies a different block and none of those blocks is already cached. Reading all 10,000 records requires 10,000 block reads. The arithmetic per record may be identical, but the transfer count is over 126 times larger. This ratio is about the constructed layouts; it is not a claim about the speed of any particular device.
A scan uses spatial locality: after paying to fetch a block, it uses many records from that block. Reusing a fetched record several times before eviction adds temporal locality. These are different opportunities. A program can have one without the other, and recognising which is available helps determine whether to change layout, traversal order or buffering.
Fuse compatible calculations
If the task needs a count, sum, minimum and maximum of the same records, all four can often be maintained during one scan. Four independent scans would read the file four times in a cold-cache transfer model. The fused version retains a small amount of state and avoids repeated input movement.
Fusion is not automatically legal. A later calculation may require the final mean, a different ordering or a record-level transformation that changes the input interpretation. Explain dependencies before combining passes. For numerical statistics, also choose a stable arithmetic method rather than assuming that a convenient one-pass formula is accurate for every magnitude of input.
Sorted runs are manageable pieces
External merge sorting first reads a chunk that fits in memory, sorts it there and writes a sorted run. It repeats until all input has become runs. A merge then combines several runs into a larger sorted run by repeatedly selecting the smallest available front record. The front of a run is enough to represent its next candidate because the rest of that run is already sorted.
For a small exact example, take twelve numbers in input order: 9, 2, 7, 1, 8, 3, 12, 4, 11, 6, 10, 5. With a run capacity of four numbers, the first stage writes runs (1, 2, 7, 9), (3, 4, 8, 12) and (5, 6, 10, 11). A three-way merge yields the integers one through twelve in ascending order.
The correctness invariant is that the output prefix is sorted and contains the smallest records already removed from the input runs. The next global minimum must be among the current run fronts. After emitting it, advance only that run. This argument does not depend on all runs being resident: the next block is fetched when its current input buffer is exhausted.
Count writes as well as reads
Run generation reads the original data and writes the runs. Each fully materialised merge pass reads its input and writes its output. Omitting the writes makes a storage-heavy algorithm look artificially cheap. Temporary files also require capacity: an algorithm may fit its working buffers while exhausting the space needed to hold old and new runs during a merge.
Stable sorting requires an additional ordering rule for equal keys. One simple specification is to compare the pair consisting of the key and original position. That makes the intended order explicit, although storing the extra position increases record size. Changing record size changes B and may change the number of passes. Correctness details can therefore affect the performance calculation directly.
A deliberately auditable design
Suppose N = 4,096 records, block size B = 64 and total working memory M = 1,024 records. Reserve space for bookkeeping and choose a run payload of 512 records. This produces eight initial runs. During merging, allocate eight input buffers of 64 records and one output buffer of 64 records. They consume 576 record slots, leaving 448 slots for the selection structure and other state under this simplified accounting.
There are 4,096/64 = 64 blocks of data. Run generation reads 64 and writes 64, costing 128 transfers. All eight runs can be merged in one pass with the stated buffers. That pass reads 64 and writes 64, another 128. Total data transfers are 256, excluding metadata, headers, retries and any initial generation of the source file.
Compare two-way merging from the same eight runs. Three merge passes are needed: eight runs become four, then two, then one. Each materialised pass costs 128 transfers. Including initial run generation gives 128 + 3 × 128 = 512. The multiway design halves this constructed transfer count while doing additional work to select among more run fronts.
Explain the breakpoints
If only four input runs fit at once, eight runs require two merge levels. Increasing memory enough to accommodate eight inputs removes an entire level. Performance can therefore change in steps rather than smoothly. Doubling a buffer does not always halve elapsed time; it may do nothing until a capacity threshold is crossed.
MIT’s external-memory sorting notes explain the dependence of sorting transfers on N/B and the merge fan-out associated with M/B. The familiar asymptotic bound concerns a particular comparison model. The exact pass calculation above is more useful for this concrete budget because it includes the chosen reserves and explicitly counts materialised output.
Fetch many routing choices at once
A binary search tree offers two child choices at each node. If each visited node costs a separate block fetch, many transfers may be needed. A B-tree stores multiple separator keys and child references in one page, allowing one fetched node to choose among many subtrees. The objective is not merely fewer comparisons; it is more progress per page transfer.
Consider an illustrative internal page of 4,096 bytes with a 32-byte header. Suppose each separator key is eight bytes and each child pointer is eight bytes. A node with f children needs f pointers and f − 1 keys, so its size is 32 + 8f + 8(f − 1) = 24 + 16f bytes. The largest integer f satisfying this budget is 254: it needs 4,088 bytes. A fan-out of 255 would need 4,104 and would not fit.
This is an upper capacity under a deliberately simple layout, not a prediction of a database’s actual node occupancy. Variable-length keys, alignment, compression, sibling pointers and free-space management change the result. An index designer needs the actual page format rather than a remembered fan-out from another system.
Balance preserves the search argument
Wide nodes help only if structural invariants remain true. Separator ranges must route each key to the correct child, and balancing rules prevent updates from producing arbitrarily deep paths. Splits and merges maintain the structure but introduce writes. An analysis of read-only lookup is therefore incomplete for a workload dominated by insertion.
The existing B-tree specialist article develops node capacity, balancing and page transfers in more detail. Use it after establishing the external-memory model here. A logarithmic comparison count and a logarithmic page-transfer count have different bases and different practical meanings; specify which one supports the performance claim.
Selectivity is not the whole story
An index is attractive when it finds a small part of a large dataset without reading everything. But if matching records are scattered, fetching their full contents may require many separate block reads. A scan can win when enough records qualify, especially when it uses blocks efficiently and the index does not cover the requested output fields.
Return to the 10,000-record file occupying 79 blocks. Suppose an index lookup has a simplified three-transfer navigation cost and each requested record requires one additional distinct block fetch. Retrieving twenty records costs 23 transfers under these assumptions; retrieving one hundred costs 103. The complete scan costs 79. The crossover is not a universal percentage: caching, clustering, repeated blocks and output requirements can change it.
If the index contains every field needed by the query, fetching base records may be unnecessary. If the data are clustered by the queried key, many matches may share adjacent blocks. The same count of qualifying records can therefore lead to very different I/O costs. Ask where the answers live, not only how many answers exist.
Include the cost of building the index
For a single query over a newly arrived file, creating an index may cost more than scanning once. For thousands of repeated queries, that construction cost can be amortised. Write the comparison as construction cost plus the cost of all subsequent queries, and include maintenance if records change during the period.
For a hypothetical index costing 400 transfers to build, with each later query costing 20 rather than an 80-transfer scan, the saving per query is 60. Six queries save 360 and do not repay construction; seven save 420 and do. This simple break-even calculation assumes comparable outputs and ignores maintenance. It is useful precisely because the assumptions are visible and can be replaced.
Bring equal keys together
Suppose records are pairs of account and amount: (B, 7), (A, 5), (B, −2), (C, 9), (A, 4), (C, 1). Sorting by account gives adjacent groups. A scan then produces A = 9, B = 5 and C = 10. The aggregation state needs only the current account and its partial total once sorting has established adjacency.
The invariant is that an account’s final total is emitted only after all records with that key have been consumed. Sorting makes that moment recognisable: a different key marks the end of the group. Without ordering, the next record could return to any earlier account, requiring more retained state or another strategy.
Hash partitioning is an alternative. Records with the same key are sent to the same partition, and each partition is processed separately. The difficulty is that partition sizes may be uneven. A frequent key or poor distribution can create a partition that still exceeds memory. The repair must handle skew or repartitioning, not simply assume the average partition size applies everywhere.
Preserve multiplicity and meaning
Aggregation is not deduplication. Two identical account-amount pairs may represent two valid transactions. Deleting one because it looks repeated changes the total unless the input contract supplies an identifier or rule establishing duplication. Conversely, summing a retransmitted event twice may be wrong when an event identifier should be unique.
Carry enough information through intermediate files to enforce the declared semantics. If a later step needs timestamps, currencies or correction identifiers, dropping them early can make the final answer impossible to validate. Smaller records improve block capacity only when they still contain the information needed to solve the task correctly.
CHAPTER 9 OF 14 · Choose access patterns
9. Batch requests while preserving their identities
Reorder work, then restore the requested order
Suppose many independent lookups arrive together. Instead of following their original random order through storage, a system may sort requests by the blocks or key ranges they need. It processes nearby requests together, then restores output order using request identifiers. The optimisation changes execution order while preserving the association between each question and its answer.
Take requests numbered zero through five that need blocks 8, 2, 8, 5, 2 and 8. With a one-block cache and the original sequence, there are six misses because successive requests always change blocks. Grouping by block needs three reads: one each for blocks 2, 5 and 8. Results must still be placed into slots zero through five correctly. Returning answers in storage order would violate the original interface.
This example ignores the cost of sorting requests, storing results and waiting to form the batch. Those costs can outweigh the saved reads when the batch is small or answers are urgent. Batching trades latency and temporary state for better locality. Measure both the total throughput and the wait experienced by an individual request.
A snapshot may be required
Reordering independent reads is straightforward only if they are meant to observe a compatible state. If updates occur between requests, changing the order may change what each request sees. The algorithm needs a stated consistency model or a fixed input snapshot. An I/O optimisation is not permission to alter the meaning of time-sensitive results.
The Parallel Algorithms root asks which operations may overlap. External-memory analysis asks which transfers may be combined or avoided. These questions can reinforce each other, but adding workers does not guarantee fewer transfers. Several workers can also compete for the same bandwidth or duplicate the same reads.
A matrix traversal exposes the issue
Imagine a 4-by-4 matrix stored row by row, with exactly four entries per block and a cache holding only one block. Reading in row order touches four blocks once each. Reading down columns alternates among all four row blocks. Under the stated one-block cache model, all sixteen accesses miss. The values and arithmetic are unchanged; the traversal order changes the movement.
Blocking processes a small tile before moving to the next. If the data needed for that tile fit together in memory, multiple useful operations can reuse them. The tile size must account for all active inputs, outputs and temporary values. Choosing it from the size of just one array can produce a working set that does not actually fit.
The Z-order specialist article explains a recursive spatial ordering that can place related cells near one another. Such layouts preserve some locality, not every distance or every query shape. A rectangular region can still require several intervals in the one-dimensional storage order.
Cache-aware and cache-oblivious methods
A cache-aware design uses parameters such as block size and memory capacity explicitly. A cache-oblivious design does not use those parameters in its algorithm, but its analysis still depends on a memory model and assumptions. Recursive decomposition can expose subproblems at many sizes so that some levels fit the available cache.
Demaine’s cache-oblivious survey develops this distinction and its qualifications. Cache-oblivious does not mean data-oblivious: hiding an access pattern from an observer is a separate property. Nor does a theoretical cache bound guarantee the fastest implementation on every processor. Constants, layout details and the real replacement policy still require measurement.
A partial run is not a finished run
Suppose a sorting job stops halfway through writing a merged run. A later restart must not treat that prefix as a complete replacement for its inputs. Useful run metadata include the record count, ordering convention, source identity and a completion state. A checksum can help detect corruption but does not prove that all required input records were processed.
A robust workflow preserves input runs until their replacement has been completed and validated according to the storage system’s guarantees. The exact commit mechanism depends on that system; do not assume that renaming, flushing or uploading has identical durability semantics everywhere. The algorithm’s recovery state should distinguish produced bytes from an accepted complete stage.
For the eight-run example, record which runs belong to the merge and the expected total of 4,096 records. After merging, verify the output count and nondecreasing key order. Those checks catch many failures, but counts and ordering alone cannot establish that the correct multiset was preserved. Stronger validation may compare identifiers or use additional checks suited to the data.
Plan temporary capacity explicitly
Keeping old runs until a new run is accepted means both generations can coexist. Compression, replication and filesystem overhead further complicate capacity planning. Calculate a conservative peak rather than assuming temporary space equals the final output size. Running out of storage after hours of work is a design failure that a simple stage-by-stage inventory may prevent.
Recovery also changes performance interpretation. A method that is slightly slower in uninterrupted execution may finish sooner in a failure-prone setting if it resumes from validated stages. Report whether timing includes retries and recovery. A benchmark that silently discards failed attempts describes a different experience from the one a user receives.
CHAPTER 12 OF 14 · Build and diagnose
12. Diagnose the bottleneck before changing the algorithm
Read the symptoms carefully
If a job performs many small reads, inspect locality and request batching. If it reads sequentially but remains slow, examine transfer bandwidth, decoding, decompression and arithmetic. If writes dominate, inspect intermediate materialisation, logging and repeated rewriting. A processor utilisation number by itself does not identify which of these costs is limiting progress.
If increasing memory suddenly improves performance, check whether a merge level disappeared or a working set began to fit. If adding memory does nothing, the algorithm may not use it, or a different resource may dominate. If a supposedly memory-bounded process grows without limit, inspect output queues, retained objects and auxiliary metadata as well as its main input buffers.
Measure cold and warm conditions separately when relevant. A second run may reuse cached data from the first, making an unchanged algorithm look dramatically better. Record the initial state and the boundary being timed. Avoid claiming cold-storage performance from a measurement served mostly from memory.
Make experiments comparable
Hold the input, output contract and validation constant when comparing designs. Record record size, data distribution, memory budget, block accounting, intermediate volume and elapsed time. Repeated trials reveal variability, while block counts explain why a change helped. Neither replaces the other: a lower predicted count can coexist with worse measured time because omitted costs increased.
Use a small exact oracle before a large performance test. Sorting should preserve multiplicities and order keys correctly. Aggregation should match manually computed totals. A batch lookup should map every answer to the correct request. Testing a larger file first makes an incorrect answer expensive without making it more convincing.
CHAPTER 13 OF 14 · Transfer and continue
13. Test what changes when assumptions change
Records become variable-sized
If a record can be hundreds of times larger than another, counting records is a poor memory budget. Budget bytes and include the cost of keys, references and decoded representations. A file that fits on storage in compressed form may expand beyond available working memory. The repair is to account for the representation used during computation, not merely the input file size.
The output becomes much larger
A join or expansion can produce more records than it reads. Scanning inputs efficiently does not remove the cost of writing a huge answer. Establish an output-size term and a backpressure strategy so that generated results do not accumulate indefinitely. Streaming the output can reduce retained memory, but it cannot erase the required output volume.
Only an estimate is required
If exact results are unnecessary, a compact summary may replace expensive storage and sorting. The Streaming Algorithms root explains summaries and their error guarantees. This is a change to the answer contract, not a free acceleration of the original exact task. State what information is lost and how the approximation is assessed.
The storage device changes
Faster random access can change the practical balance between an index and a scan. Asymmetric writes, parallel devices and remote storage can change it again. Keep the original counts and replace the cost assumptions rather than repeating an old timing claim. A transferable understanding explains the mechanism under the old conditions and predicts which measurement should be repeated under the new ones.
CHAPTER 14 OF 14 · Transfer and continue
14. Questions, learning routes and next reading
Does external memory mean the data must exceed RAM?
That is a common application, but the idea is broader. The analysis can describe an expensive boundary within a hierarchy even when the whole dataset fits at a larger level. Always identify the fast-memory capacity and transfer unit being modelled. Without them, a claim about avoiding I/O can be ambiguous.
Is every sequential algorithm I/O-efficient?
No. Sequential execution means operations are performed in an order; it does not mean storage is visited contiguously. A single-threaded pointer-chasing program can fetch a different block for almost every operation. Conversely, a parallel algorithm can have excellent locality if its partitions and buffers are designed carefully.
Should every large dataset be sorted?
No. Sorting can enable grouping, merging and repeated range queries, but a single aggregate may need only a scan. An existing index may already provide the required order. The useful question is whether the later savings repay construction and intermediate storage costs for the actual workload.
How can a learner demonstrate mastery?
Start with a block simulator. Give each record a block identifier, set a tiny cache capacity and count misses for a declared replacement rule. Reproduce the 4-by-4 matrix traversal and the six-request batching example. Then change cache capacity and explain why the earlier counts no longer apply unchanged.
Next, implement run generation and a multiway merge on small integer files. Preserve duplicates, handle empty input and verify uneven final blocks. Record every read and write in the simulator, then compare those logical counts with elapsed time in a real implementation. Explain differences rather than adjusting the model retrospectively until it appears perfect.
Finally, build an account-aggregation experiment that compares scanning resident state, sorting then grouping, and partitioning. Include a skewed input and a record-size change. The Education parent frames this as transfer: the learner should be able to repair a method when its original assumptions fail.
For technical foundations, use MIT’s sorting lecture and Demaine’s survey, then connect the model to the verified B-tree and Z-order articles above. Return to the Gold Standard master for adjacent subjects. A convincing result explains both why the answer is correct and why the necessary data movement fits the available resources.