External-Memory Algorithms & Data Structures

An algorithm that is excellent in RAM can be unusable when its working set lives on SSD, disk, or a remote object store. The expensive event is no longer one comparison: it is moving a page or a large contiguous range into faster memory. External-memory design makes that transfer explicit, then arranges computation so that each transferred block does useful work on many records.

The core techniques are batching, sequential access, high fanout, and deferred reorganization. External merge sort batches comparisons into streaming passes; B-trees make one page choose among hundreds of subtrees; log-structured merge trees turn small random updates into sorted sequential runs and pay for consolidation later.

The I/O model changes what “fast” means #

The Aggarwal–Vitter external-memory model has two storage levels:

$N$

Number of data items in the problem.

$M$

Number of items that fit in internal memory.

$B$

Number of consecutive items transferred by one I/O block.

External storage is unbounded for the analysis. One I/O moves one block of $B$ contiguous items between external and internal memory; computation on resident items is free. The parameters satisfy $1\le B\le M<N$ for a genuinely external problem, and algorithms normally need several blocks of memory so that input and output can be buffered independently.

The fundamental costs are conventionally named:

$$\mathop{\mathrm{Scan}}(N)=\Theta\!\left(\frac{N}{B}\right),$$

$$\mathop{\mathrm{Sort}}(N)= \Theta\!\left( \frac{N}{B} \max\left\{1,\log_{M/B}\frac{N}{B}\right\} \right)$$

for comparison sorting under the model's usual parameter conditions. The maximum keeps the expression honest when the logarithm is below one: reading and writing the data still costs a scan.

This model deliberately omits CPU comparisons, decompression, checksum work, queue depth, device parallelism, operating-system caching, and crash recovery. It is a first-order locality proof, not a latency prediction. A design must satisfy the model and then be measured on its actual storage stack.

Why ordinary merge sort is not enough #

Two-way merge sort performs $\Theta(\log_2 N)$ full-data merge levels. That is optimal for comparison count in RAM, but external memory can hold many input buffers at once. Merging only two runs wastes the available fan-in.

External merge sort has two phases.

Phase 1: create sorted runs #

Repeatedly read up to $M$ items, sort them internally with any suitable sorting algorithm, and write one sorted run. This produces approximately

$$R_0=\left\lceil\frac{N}{M}\right\rceil$$

initial runs and costs one full read plus one full write: about $2N/B$ I/Os.

Phase 2: merge many runs at once #

Reserve one block-sized input buffer per run and at least one output buffer. With simple buffering, the merge fan-in is bounded by

$$k\le\left\lfloor\frac{M}{B}\right\rfloor-1.$$

Keep the smallest current record from each nonempty input buffer in a min-heap. Remove the smallest, append it to the output buffer, refill an input buffer when exhausted, and flush the output buffer when full. One merge pass reads and writes every item once, again about $2N/B$ I/Os, and reduces the run count by a factor of up to $k$.

create_runs(input, memory_capacity M):
    while input remains:
        chunk = read up to M items
        sort chunk in memory
        write chunk as a new run

while more than one run remains:
    group runs into batches of at most floor(M/B) - 1
    for each batch:
        allocate one B-item input buffer per run
        allocate a B-item output buffer
        heap = first item from every nonempty input buffer

        while heap is not empty:
            item, run = heap.pop_min()
            append item to output buffer
            refill or advance that run's input buffer
            push its next item when one exists
            flush output whenever its buffer fills

        flush the final partial output block

The heap performs $O(\log k)$ CPU work per record, but its $k$ heads live in memory. External I/O remains sequential over each input run and the output run.

Worked external-sort budget #

Sort a 1 TiB file with 4 GiB available memory and 4 KiB transfer pages. For the transfer calculation, treat these byte capacities as $N$, $M$, and $B$:

All 256 runs fit into one multiway merge pass. The idealized data movement is therefore:

That is $4N/B=2^{30}$ 4-KiB block transfers in the literal model. A real implementation uses larger asynchronous read-ahead/write-behind buffers, reserves memory for records and the heap, and may have much less than 4 GiB available after accounting for its runtime and other processes. Those details reduce the safe fan-in; they do not change why multiway merging saves whole passes.

Sorting failures that the formula does not prevent #

• Insufficient temporary space: run generation and merging need output space while old inputs still exist. Budget peak bytes, not only final bytes.
• Variable-size records: $M$ and $B$ are capacities, so a few huge records can break record-count assumptions. Sort compact keys plus record references when appropriate.
• Expensive comparison/projection: cache normalized keys instead of repeatedly decoding whole records.
• Unstable tie handling: carry an original sequence number when stable order is part of the contract.
• Partial output after failure: write runs and final output under an atomic publication protocol; a sorted prefix is not a valid replacement for the input.
• Too many open files: fan-in is also limited by descriptors, per-stream metadata, and the storage service's concurrency limits.

B-trees turn one page into a large decision #

A binary search tree spends one child pointer per comparison. If every node occupies its own page, a root-to-leaf search performs $O(\log_2 N)$ random page reads and wastes most bytes in each page. A B-tree packs many sorted separator keys and child pointers into one node, normally sized to one storage page.

One common minimum-degree parameterization uses integer $t\ge2$:

1. every node stores sorted keys;
2. an internal node with $q$ keys has $q+1$ children delimiting key ranges;
3. every non-root node has between $t-1$ and $2t-1$ keys;
4. a non-leaf root has between 1 and $2t-1$ keys;
5. every leaf is at the same depth.

The occupancy bounds keep fanout high; equal leaf depth supplies balance. A height-$h$ tree has at least $2t^h-1$ keys for $h\ge1$, so

$$h\le \log_t\frac{N+1}{2}.$$

If a page can choose among roughly 256 children, four child selections distinguish up to $256^4=2^{32}$ ranges before accounting for the many records held in leaves. Real fanout depends on key width, prefix compression, page headers, child-pointer width, fill policy, and payload placement.

Search follows separators page by page #

Within one resident node, binary search or a cache-aware linear/SIMD search locates the first separator not less than the target. If the key is not found in the current node, that position identifies exactly one child range. The invariant is:

$$\text{all keys in child }i \text{ lie between separator }i-1\text{ and separator }i.$$

The algorithm reads one node per level. A buffer pool normally keeps the root and popular upper levels resident, so observed storage reads can be fewer than tree height.

Insertion splits; deletion borrows or merges #

Insertion descends to the target leaf. When a node is full, split it around a median and promote a separator to the parent. A root split creates a new root and is the only way height increases. Implementations may split on descent, after detecting overflow, or with concurrency-specific variants; the postcondition is the same: key order, occupancy, and equal leaf depth are restored.

Deletion removes a key, then repairs underfull nodes by borrowing from a sufficiently occupied sibling through the parent or merging siblings with a parent separator. A root left with one child is replaced by that child, reducing height.

B-tree versus B+ tree #

In a classical B-tree, records or record references may appear with keys in internal and leaf nodes. A B+ tree keeps data records/references in leaves and uses internal nodes only as routing separators; leaves are commonly linked for ordered scans. Consequences:

• internal entries are smaller, increasing fanout and reducing height;
• every exact lookup reaches a leaf, giving a uniform path;
• after one boundary search, a range scan walks adjacent leaves at $O(1+Z/B)$ I/Os;
• separator keys may be duplicated above their leaf entries.

Production formats choose their own variant. SQLite, for example, has distinct table and index B-tree page kinds; its file format fixes a database-wide page size, uses page numbers as child pointers, and spills oversized payload to overflow pages. The lesson is not to call every implementation a B+ tree, but to inspect where payload lives and what one page read actually yields.

Page layout and the buffer pool are part of the data structure #

A page is more than a vector of keys. It needs a header, slot or cell directory, free-space accounting, sibling/child references, and often checksums or recovery metadata. Variable-size records are commonly packed from one end while a fixed-size slot array grows from the other; compaction can move bytes within the page without changing logical slot identities.

The buffer pool maps page IDs to resident frames and coordinates reads, dirty writes, pinning, eviction, and recovery. Its state changes the observed path:

Do not count the operating-system page cache and a database buffer pool as two independent full caches without considering double buffering. Conversely, direct I/O removes OS caching services that the application must then supply correctly.

Bulk loading beats repeated random insertion #

When all records are available, sort by key, fill leaves sequentially near the chosen target occupancy, then build parent levels from their first/separator keys. Bulk loading performs scan-like writes and avoids a long sequence of page splits. It also makes the desired free-space reserve explicit: completely full leaves minimize initial size but leave no room for nearby future inserts.

LSM trees defer random writes into sorted runs #

A log-structured merge tree changes the update path:

1. append the mutation to a recovery log according to the durability contract;
2. apply it to an ordered in-memory memtable;
3. when the memtable reaches its limit, freeze and flush it as an immutable sorted run (often an SST file);
4. in the background, merge overlapping runs and discard obsolete versions or tombstones.

The foreground write is sequential log I/O plus memory work. The cost reappears during flush and compaction, which may rewrite the same logical byte several times.

A point read checks mutable and immutable memtables, then candidate runs from newest to oldest. Per-run indexes locate blocks; Bloom filters can avoid reading runs that definitely lack the key. A range read performs a multiway merge across overlapping runs, resolving duplicate versions and deletion tombstones by sequence/version order.

The amplification triangle #

Write amplification

Physical bytes written divided by logical bytes written.

Read amplification

Runs, blocks, or bytes consulted to satisfy one logical read.

Space amplification

Physical live-plus-obsolete storage divided by logical live data.

Compaction policy trades among them:

RocksDB's documentation explicitly describes leveled, universal (tiered), and FIFO compaction and frames the choice in these amplification terms. No style is “the LSM algorithm”; workload, retention, storage endurance, and latency objectives select the policy.

B-tree and LSM trade different foreground costs #

External hashing and partitioning #

Ordered access is not always required. Hash-partition a large input into buckets that each fit in memory, then process buckets independently. External hash joins, duplicate removal, and aggregation use this pattern. Skew is the failure mode: one hot bucket may still exceed $M$, requiring recursive repartitioning or a special heavy-key path.

Dynamic external hash indexes such as extendible hashing use a directory of hash prefixes pointing to bucket pages. A full bucket splits by one more hash bit; the directory doubles only when the new local depth exceeds global depth. Exact lookup can be shallow, but there is no natural ordered range scan. See Hash Tables for collision and adversarial-key concerns that remain relevant outside RAM.

From model to SSD, object storage, and databases #

The block model remains useful because locality and batching still matter, but $B$ is a design granularity, not necessarily the device's physical page:

• SSD random reads avoid mechanical seek but still have command latency, limited queues, internal erase blocks, and garbage-collection/write-amplification effects.
• NVMe rewards parallel independent requests; one synchronous dependency chain can leave the device idle.
• object stores favor large range requests and penalize request count; overwriting a “page” may mean writing a new object.
• compressed blocks trade CPU for fewer bytes and make partial record access block-granular.
• remote storage adds tail latency and retry semantics that a transfer count cannot express.

Benchmark request-size curves, queue depth, cache hit rate, read/write amplification, compaction debt, and p95/p99 latency. Do not substitute the vendor's maximum sequential bandwidth for the workload's measured access pattern.

Crash safety is orthogonal to search correctness #

A perfectly balanced tree can still be unrecoverable after a torn split. Durable structures need a protocol such as write-ahead logging, copy-on-write pages, shadow paging, or another proven ordering of data and metadata writes. “Flush” must be tied to actual persistence semantics, not merely a language buffer. Recovery must be able to distinguish committed state from incomplete background work.

Choosing concretely #

1. One large batch sort: generate maximal in-memory runs and use the widest safely buffered merge; budget temporary space and atomic publication.
2. Read-heavy ordered index with point and range queries: use a page-shaped B+ tree and a buffer pool; bulk-load when data arrives in batches.
3. Sustained write-heavy key-value ingestion: use an LSM design only with an explicit compaction budget and measured read/write/space amplification.
4. Exact lookup without order: consider external hashing; test skew and untrusted keys.
5. Repeated scans/analytics: prefer sorted/columnar runs and large sequential blocks over pointer-rich serialized RAM structures.
6. Data currently fits RAM but may not later: still design file layout and algorithms around bounded memory; swapping an unbounded RAM algorithm is not an external-memory implementation.

Failure diagnostics #

1. Are $N$, $M$, and $B$ measured in the same item units, including record and metadata size?
2. Does every input and output stream have real buffering?
3. Is merge fan-in bounded by memory, descriptors, and service concurrency—not only arithmetic?
4. Are temporary-space and failure-publication requirements budgeted?
5. Does a tree node fit the intended page after headers, slots, and worst-case keys?
6. Are B-tree capacity and minimum occupancy stated directly rather than hidden behind “order”?
7. Are root/upper-level cache hits separated from physical reads?
8. Are LSM tombstones and old versions retained until a safe compaction frontier?
9. Is compaction provisioned so foreground writes cannot outrun it indefinitely?
10. Are read, write, and space amplification measured together?
11. Does the benchmark reproduce request sizes, queue depth, cache state, and durability settings?
12. Can the structure recover every interrupted split, flush, or compaction without publishing partial state?

Exercises #

1. A 6 TiB input is sorted with 2 GiB of memory. How many initial runs are produced, and what minimum fan-in permits a single merge pass?
2. Prove the B-tree lower bound $N\ge2t^h-1$ for a nonempty height-$h$ tree under the stated minimum-degree invariants.
3. A B+ tree has a 200-way effective fanout and its top two levels are cached. How many uncached page reads are needed for a height-4 root-to-leaf path?
4. Explain why a Bloom filter can reduce LSM point-read amplification but cannot by itself accelerate a range scan that must return existing keys.
5. Give an external hash-partition input distribution that defeats uniform bucket sizing and design a bounded-memory recovery path.