The classical B-tree updates pages in place, protects them with latches and recovers them with a write-ahead log. Each decision has a cost: in-place updates turn a one-byte change into a full-page random write, latches serialise threads on hot pages, and logging writes every change twice. This chapter surveys five families of variants that remove one or more of those costs by changing where and when writes happen: copy-on-write trees never update in place, lazy trees buffer updates in memory, FD-trees and Bw-trees make disk writes append-only, and cache-oblivious trees change the layout so the structure performs well at every level of the memory hierarchy without knowing the block size.

These are the trees inside systems you deploy: LMDB and bbolt under OpenLDAP and etcd, WiredTiger under MongoDB, the Bw-tree under SQL Server's in-memory engine. Knowing which variant an engine uses tells you how it behaves under concurrent readers, what its write amplification looks like, and why it does or does not need a WAL, a vacuum or a compaction process.

In one minute

• Copy-on-write B-trees never modify a page in place: a write copies the path from leaf to root and atomically swaps the root pointer. Readers need no locks, crashes cannot corrupt the tree, no WAL is needed; the costs are extra space, a path copy per write and a single writer. LMDB and its Go port bbolt are the canonical implementations.
• Lazy B-trees keep the on-disk B-tree but absorb updates in memory and write a merged page later. WiredTiger attaches update lists to materialised pages and reconciles them on eviction or checkpoint; the Lazy-Adaptive Tree attaches update buffers to subtrees and cascades them downward.
• FD-trees combine a small mutable head tree with immutable sorted runs growing by a constant factor; fractional cascading places fence pointers from each run into the next so a lookup reads one page per level.
• Bw-trees are latch-free: nodes are addressed through a mapping table of logical IDs, updates are prepended as delta records installed with one compare-and-swap, chains are consolidated periodically, and splits and merges are multi-step structural modification operations any thread can complete.
• Cache-oblivious B-trees use the van Emde Boas layout over a packed memory array so lookups are block-optimal for every block size at once; the idea matters more for CPU caches and Bε-trees than for disk pages.
• The common theme is trading read cost and space for cheaper or more concurrent writes, the RUM trade-off Chapter 7 formalises.

Copy-on-write B-trees

Why avoid in-place updates

In-place updates have two awkward properties. A crash in the middle of a page write can leave a half-written page, so the engine needs a log (and often double-write buffers, as InnoDB has) to guarantee atomicity. And a writer modifying a page must exclude readers of that page, so readers and writers block each other and the engine needs the latching machinery of Chapter 5.

How it works

A copy-on-write (CoW) B-tree never overwrites a page a reader might see. To modify a leaf, the writer copies it, applies the change to the copy and writes it to a new location. The parent must now point at the new leaf, so the parent is copied too, and so on to the root. The new root shares most subtrees with the old; only the modified path is new. The write commits when the pointer to the current root, kept in a well-known header page, is updated with a single atomic write.

The consequences follow directly. Readers need no synchronisation: a reader holding root v1 sees a consistent, immutable tree while writers publish v2 and v3. Writers are never blocked by readers. Crash safety needs no log: if the system dies before the root swap, the old root still describes a complete tree and the half-written pages are unreferenced garbage, so there is no torn page to repair. Snapshots are free: an old root is a snapshot.

The costs are equally direct. Every write rewrites a root-to-leaf path of h pages, so write amplification is high and the writer spends CPU copying. Old versions consume space until no reader needs them, and reclaiming it requires knowing when the last reader of a version has finished. And because the root swap is the commit, concurrent writers would race on it, so CoW trees usually permit one writer at a time.

LMDB

LMDB (Lightning Memory-Mapped Database), written by Howard Chu for OpenLDAP, memory-maps the whole file and uses the OS page cache instead of its own, so a read is a pointer dereference with no copying. Writers are serialised by a mutex; readers run lock-free and register the tree version they use in a shared reader table.

LMDB keeps two meta pages at the start of the file and alternates between them: a commit writes the new root into the meta page not currently in use and then makes it current, so the committed tree and the one before it are always both intact. Freed pages go on a freelist but can be reused only once every reader that might see them (readers older than the commit that freed them) has finished, which the reader table makes checkable. There is no compaction, vacuum or background thread. The design suits read-heavy, operationally simple deployments: OpenLDAP, Monero, and through bbolt (a Go reimplementation) etcd and Consul. Its limits follow from the design: a single writer caps write throughput, large values cost large copies, long-running readers make the file grow, and the file does not shrink without an offline copy.

Abstracting node updates

CoW and lazy trees both raise a question the in-place tree could ignore: what does a node look like while being modified in memory? Direct manipulation of the cached page bytes (LMDB, SQLite, InnoDB) avoids copying but means every operation is written against the raw on-disk format. Materialising the node into a language-native structure (WiredTiger) makes modification easy at the cost of serialising on write and more memory. A wrapper object holding a reference to the raw bytes and lazily materialising fields is the usual compromise in managed-memory languages.

Lazy B-trees

Why buffer updates

Even with a good replacement policy, a B-tree that modifies pages in place writes one dirty page per modified leaf, and under random updates each page accumulates only a few changes before being flushed. A lazy B-tree decouples the logical update from the physical page write: buffer updates in an update-friendly in-memory structure and apply them later in batches, so each page write carries many changes.

WiredTiger

WiredTiger, MongoDB's default engine since 3.2, keeps different in-memory and on-disk representations. When a page is read, its on-disk image is retained and an in-memory index over it is built. Updates do not modify the image: each modified key gets an update list (a chain of versions, newest first, which also provides WiredTiger's MVCC), and inserts between existing keys go into per-page insert skiplists. A read consults the update structures first and falls back to the image.

Pages are written back by reconciliation, which runs when a dirty page is evicted or a checkpoint is taken: walk the image plus updates, produce a new on-disk image containing the versions that should persist, and write it to a new location (WiredTiger never overwrites in place, so it also has CoW's crash-safety, with checkpoints as published roots). An oversized page is split into several on-disk pages during reconciliation, and large in-memory pages can be split in memory without writing. Because updates live in skiplists, concurrent inserts into one page proceed with atomic pointer operations rather than page latches. The trade-offs: reads on heavily updated pages walk update chains until reconciliation catches up, memory holds both image and updates, and eviction becomes more expensive than a plain page write.

Lazy-Adaptive Tree

The Lazy-Adaptive Tree (LA-tree, Agrawal et al., 2009) targets flash, where small random writes are costly. It groups the tree into subtrees and attaches an update buffer to the root of each. An insert or delete is appended to the top buffer and returns. When a buffer fills, its operations are sorted and pushed to the buffers of the child subtrees that own their keys, recursively, until they reach leaves and are applied in bulk. Lookups must check the buffers on their path as well as the leaf. The "adaptive" part tunes buffer sizes at runtime: lookup-heavy subtrees get smaller buffers, update-heavy ones larger. It is a precursor of the Bε-tree family, in which buffered messages flow down the tree in batches.

FD-trees

Why confine random writes

SSDs read randomly well but write randomly badly: scattered small writes trigger erase-block garbage collection inside the drive (Chapter 7). A B-tree updated in place generates exactly those writes. The FD-tree (Flash Disk tree, Li, He et al., 2010) confines random writes to a small region and makes everything else sequential.

Head tree and logarithmic runs

An FD-tree has a small mutable head tree (a B+-tree small enough to stay in memory) and immutable sorted runs L1, L2, ..., Ln on disk, each a factor k larger than the one above. Inserts go to the head tree. When it fills, its contents merge with L1 into a new L1 written sequentially; when L1 exceeds capacity it merges into L2, and so on. Deletes insert filter entries (tombstones) that cancel matching records during a merge. Each level is rewritten whole, so writes are sequential and each record is rewritten about once per level, giving write amplification logarithmic in the data size. A lookup searches the head tree and then each level in turn, newest version winning. Without help, that means a binary search per level.

Fractional cascading

Fractional cascading is a general technique for searching one key in a cascade of sorted arrays without a full binary search in each: copy a sample of each array's elements (every other one, say) into the array above, each with a pointer to its position below. A search in the top array lands within a bounded distance of the right position in the next, and after the first binary search each level costs a constant number of steps.

The FD-tree applies this with fences: level Li contains, besides its own records, a fence entry for the first key of every page in Li+1, pointing at that page. A search in Li ends at a fence that names the exact page of Li+1 to read, so a lookup costs about one page read per level plus the head tree. Fences are regenerated during merges, when both levels are being rewritten anyway.

Aspect	FD-tree	Leveled LSM tree (Chapter 7)
Mutable component	Head tree (B+-tree)	Memtable (skiplist)
Immutable components	Sorted runs growing by factor k	SSTables per level growing by factor k
Cross-level lookup	Fences (fractional cascading)	Bloom filters plus per-table index blocks
Deletes	Filter entries	Tombstones

Both are instances of "buffer, then merge sequentially"; the FD-tree's contribution is using fractional cascading rather than filters to keep reads cheap.

Bw-trees

Why go latch-free

The Bw-tree ("buzzword tree", Levandoski, Lomet and Sengupta, Microsoft Research, 2013) attacks three problems. In-place updates cause write amplification. Latches limit multicore scalability: on a many-core machine with data in memory, latch contention and cache-line bouncing dominate index operation cost. And latch-based B-tree concurrency is complex to get right. The Bw-tree is latch-free: every update is one atomic compare-and-swap and no thread ever waits for another.

Mapping table and delta chains

The enabling idea is indirection. Nodes refer to each other by logical page IDs (PIDs), and a central mapping table translates each PID to its current physical address. Changing a slot with one compare-and-swap (CAS) atomically changes what every parent and sibling link to that PID means, without touching those neighbours.

An update does not modify the node. It allocates a delta record describing the change (insert K=V, delete K, or a structural delta), points it at the node's current address, and CASes the mapping table slot from that address to the delta. If the CAS fails, another thread got there first; the thread re-reads and retries. A node is therefore a delta chain ending in a base page. A reader follows the chain, applying deltas until it finds the key or reaches the base page. Reads cost more as chains grow; writes cost one allocation and one CAS, with no page copy and no latch.

Consolidation

When a chain passes a length threshold, a thread performs consolidation: build a fresh base page incorporating every delta and CAS the slot from the chain head to the new page. If a new delta arrived meanwhile the CAS fails and consolidation is retried later. Consolidation is the Bw-tree's equivalent of WiredTiger's reconciliation and an LSM tree's compaction: where the cost deferred by cheap writes is paid, and the knob that trades read latency against write throughput.

Structural modification operations

Splits and merges touch several nodes and cannot be one CAS, so the Bw-tree decomposes them into structural modification operations (SMOs): sequences of atomic steps whose intermediate states are valid, in the spirit of the Blink-tree. A split of node P: (1) create a new node Q with the upper half of P's keys and install it in the mapping table under a fresh PID; (2) prepend a split delta to P recording the separator and Q's PID, which makes Q reachable through P (the half-split state); (3) prepend an index-entry delta to the parent adding the separator and Q's PID. A merge of R into its left sibling L: (1) prepend a remove-node delta to R; (2) prepend a merge delta to L pointing at R's contents; (3) prepend an index-term-delete delta to the parent.

Any thread that arrives at a half-finished SMO helps along: it completes the pending step before continuing its own work, so no thread blocks waiting for the originator, which is what keeps the structure latch-free during structural changes.

Garbage collection with epochs

A consolidated chain or removed node cannot be freed immediately because a slow reader may still be traversing it. The Bw-tree uses epoch-based reclamation: a thread joins the current epoch when it starts an operation and leaves when done; memory unlinked during epoch e is freed only when every thread that joined epoch e or earlier has exited. Later threads cannot have seen the memory because they read the mapping table after the CAS that removed it.

Where it is used and what it costs

The Bw-tree is the range index of Microsoft's Hekaton (SQL Server In-Memory OLTP); with the LLAMA storage layer (Chapter 7) it also writes deltas to flash in a log-structured way. The costs are real. The Open Bw-tree study (Wang et al., SIGMOD 2018) reimplemented it carefully and found that delta-chain traversal, mapping-table indirection, CAS failures under contention and consolidation often made it slower than a well-engineered B+-tree with optimistic lock coupling, with its advantages largest when writes dominate and per-node contention is low. Latch-free trades blocking for pointer chasing and retry work; it is not a synonym for fast.

Cache-oblivious B-trees

Why ignore the block size

A B-tree is tuned to one boundary in the memory hierarchy: its page size matches disk blocks (the two-level external memory model, with memory of size M and transfers in blocks of size B). A modern machine has several boundaries (L1, L2, L3, DRAM, SSD) with different block sizes. Cache-oblivious algorithms (Frigo, Leiserson, Prokop and Ramachandran, 1999) are designed without knowing B or M yet achieve asymptotically optimal transfers at every level simultaneously. The cache-oblivious B-tree (Bender, Demaine and Farach-Colton, 2000) applies this to search trees.

van Emde Boas layout

The static piece is the van Emde Boas layout, which stores a complete binary search tree in an array so that any root-to-leaf path touches few memory blocks for any block size. Cut the tree at half its height: the top subtree has about square-root-of-N nodes and there are about square-root-of-N bottom subtrees of the same size. Lay out the top subtree contiguously, then each bottom subtree contiguously, and recurse inside each. For any B there is a recursion level at which subtrees fit in one or two blocks, and a search passes through O(log N / log B) of them, the same O(log_B N) a B-tree with page size B achieves, with B appearing nowhere in the layout.

Packed memory array

The dynamic piece is the packed memory array: keys in sorted order in an array with gaps, with density kept within bounds in every aligned window. When an insert makes a window too dense (or a delete too sparse), the smallest enclosing window whose density is acceptable is redistributed evenly. Amortised, each insert moves O(log² N / B) blocks, and a static vEB-laid-out tree over the array's cells serves as the search structure, rebuilt when the array is redistributed.

Why it matters in practice

Disk engines know their block size, so a tuned B-tree is already optimal there and the cache-oblivious version adds complexity for little gain. The idea pays where the hierarchy is deep and uncertain: CPU cache behaviour of in-memory indexes, and especially the Bε-tree (streaming B-tree) family derived from the same work, which buffers updates in internal nodes and was commercialised as the fractal tree in TokuDB and PerconaFT. As byte-addressable non-volatile memory blurs the line between memory and storage, such layouts become more attractive.

Design trade-offs

Variant	Writes	Reads	Space	Concurrency	Recovery	Systems
Classic in-place B+-tree	Random page writes	One page per level	Compact	Latches, crabbing	WAL	InnoDB, PostgreSQL, SQLite
Copy-on-write	Path copy per write	Same as classic	Old versions until readers finish	Lock-free readers, single writer	None (root swap)	LMDB, bbolt/etcd, Btrfs, ZFS
Lazy (WiredTiger)	Coalesced on reconciliation	Image plus update chains	Image and updates in memory	Skiplists, few latches	Checkpoints plus journal	WiredTiger/MongoDB
FD-tree	Sequential run merges	One page per level via fences	Duplicates across levels	Simple	Runs immutable	Research; close to leveled LSM
Bw-tree	One CAS and a delta	Delta chain then base page	Deltas and garbage until epoch frees	Latch-free CAS, help-along SMOs	Log-structured via LLAMA	Hekaton range index
Cache-oblivious	Packed array redistributions	Block-optimal for every B	Gaps in the array	Not the focus	Not the focus	In-memory indexes; ancestor of Bε-trees

When to pick what: read-mostly with many readers, copy-on-write (LMDB/bbolt), accepting a single writer; mixed workloads with many writers, a lazy tree or a classic tree with MVCC; write-heavy on flash with range queries, an FD-tree or in practice an LSM tree (Chapter 7); an in-memory index on a many-core machine, a Bw-tree-style design or a B+-tree with optimistic lock coupling.

Interview angle

• How does a copy-on-write B-tree achieve crash safety without a write-ahead log? Every write produces new pages for the modified path and leaves the old ones untouched; the only in-place write is the atomic root pointer swap. If the crash happens before the swap, the old root still describes a complete tree and the orphaned pages are garbage, so there is no torn page to repair and no redo or undo log.

• Why does LMDB allow only one writer, and how do its readers avoid locks? The commit is one root-pointer swap, so concurrent writers would have to merge their path copies; LMDB serialises them with a mutex instead. Readers record their tree version in a shared reader table and dereference the memory-mapped file directly; nothing they can see is ever modified, and the table tells the writer which freed pages are still in use.

• What does "lazy" mean in a lazy B-tree, and what is the cost? Updates are absorbed in memory (WiredTiger's update lists and insert skiplists, the LA-tree's subtree buffers) and applied to on-disk pages later in batches, so each page write carries many changes. The cost is read-side merging of image and buffered updates, plus memory for both.

• Explain fractional cascading and why the FD-tree uses it. It seeds each sorted array with pointers (fences) from a sample of the next, so after the first binary search every subsequent level is located in constant steps. The FD-tree has one sorted run per level; without fences a lookup would binary search each run, with fences it reads one page per level.

• Walk through a Bw-tree insert and explain why no latch is needed. Traverse from the root, resolving logical page IDs through the mapping table and following delta chains to the target leaf. Allocate a delta record pointing at the leaf's chain head, then CAS the leaf's mapping table slot from the old head to the delta. The CAS succeeds atomically or fails because another thread changed the slot, in which case re-read and retry. No thread holds a resource another must wait for.

• How does a Bw-tree split work if a thread can only CAS one word? As a sequence of atomic steps that each leave the tree valid: install the new sibling in the mapping table, prepend a split delta to the splitting node (half-split, as in a Blink-tree), then prepend an index-entry delta to the parent. Any thread encountering an incomplete split completes it before proceeding.

• When is a latch-free index not faster than a latched one? When delta chains get long (reads chase pointers), when many threads contend on one node (CAS failures and retries), and when mapping-table indirection and consolidation outweigh the latch acquisitions they replace. The Open Bw-tree evaluation found optimistic lock coupling on a B+-tree competitive or better on many workloads.

• What does cache-oblivious mean, and would you use such a B-tree on disk? A layout that achieves optimal block transfers for every block size without being told the size; the van Emde Boas layout does this for search trees. On disk the block size is known and a tuned B-tree is already optimal, so the benefit is small; it matters for in-memory indexes spanning several cache levels and as the theory behind Bε-trees.

Pitfalls and misconceptions

• "Copy-on-write means the whole tree is copied." Only the root-to-leaf path of the modified leaf (h pages) is copied; everything else is shared between versions.
• "LMDB has no write amplification because it has no log." It avoids double-writing through a log but pays path copying on every commit, and space is reclaimed only when old readers finish, so long read transactions make the file grow.
• "WiredTiger is an LSM engine." It is a B-tree with in-memory update buffering and no-overwrite page writes. The LSM-like part is that reconciliation batches updates, not that it keeps sorted runs on disk.
• "The Bw-tree has no synchronisation." It has no latches, but every update is a CAS that can fail, consolidation and SMOs retry, and epoch-based reclamation is a synchronisation protocol. Latch-free guarantees progress for some thread, not the absence of coordination.
• "FD-trees and LSM trees are unrelated." Both buffer writes in a small mutable structure and merge into exponentially larger immutable sorted runs; the FD-tree's distinctive piece is fractional cascading where LSM engines use Bloom filters and indexes.

Key terms

Term	Meaning
Copy-on-write (CoW)	Never modify a page in place; copy the path to the root and swap the root pointer atomically
Meta page	LMDB's header page holding the current root; two alternate so the previous version stays valid
Reader table	LMDB's shared record of which tree version each reader uses, needed to reclaim freed pages safely
Lazy B-tree	B-tree that buffers updates in memory and applies them to pages later in batches
Reconciliation	WiredTiger's merge of a page's in-memory updates into a new on-disk image
Lazy-Adaptive Tree	Tree with per-subtree update buffers that cascade downward and adapt in size to the workload
FD-tree	Flash-oriented index with a small mutable head tree and logarithmically growing immutable sorted runs
Fractional cascading	Seeding each sorted array with pointers from a sample of the next so cascaded searches cost constant steps per level
Bw-tree	Latch-free B-tree using a mapping table, delta records and compare-and-swap
Mapping table	Table from logical page ID to physical address; the single point updated by CAS
Delta record	Immutable record of one update prepended to a node's chain
Consolidation	Rewriting a delta chain into a new base page
Structural modification operation	Multi-step split or merge whose intermediate states are valid and completable by any thread
Epoch-based reclamation	Freeing unlinked memory only after every thread active at unlink time has finished
van Emde Boas layout	Recursive square-root decomposition of a static tree into contiguous subtrees
Packed memory array	Sorted array with controlled gaps supporting inserts by local redistribution

Further reading

• Database Internals, Chapter 6 ("B-Tree Variants"); Chapter 5 for the latch-based concurrency it replaces and Chapter 7 for log-structured storage and LLAMA.
• Howard Chu, LMDB design documents and the original OpenLDAP presentation: https://www.symas.com/lmdb
• WiredTiger architecture guide (pages, reconciliation, eviction): https://source.wiredtiger.com/
• Justin J. Levandoski, David B. Lomet and Sudipta Sengupta, "The Bw-Tree: A B-tree for New Hardware Platforms", ICDE 2013.
• Ziqi Wang et al., "Building a Bw-Tree Takes More Than Just Buzz Words", SIGMOD 2018: https://www.cs.cmu.edu/~huanche1/publications/open_bwtree.pdf
• Yinan Li, Bingsheng He et al., "Tree Indexing on Solid State Drives", VLDB 2010 (the FD-tree).
• Devesh Agrawal et al., "Lazy-Adaptive Tree: An Optimized Index Structure for Flash Devices", VLDB 2009.
• Michael A. Bender, Erik D. Demaine and Martin Farach-Colton, "Cache-Oblivious B-Trees", FOCS 2000.
• Michael A. Bender et al., "An Introduction to Bε-trees and Write-Optimization", ;login: (USENIX), 2015.