BOOK DEEP READ · Database Internals · Chapter 6

B-Tree Variants

Database Internals · Ch 6 · Alex Petrov · 2019

What is this chapter about?

The previous chapters built the database's index: layers of signposts that get you to the right page in a few hops. This one asks a different question — that scheme was invented forty years ago for spinning disks and single-core machines. Does it still fit?

A strange thing first

You probably assume the expensive part is finding. It isn't. The expensive part is changing. Edit an eighty-character record and the disk has to rewrite a whole page — thousands of characters. And so nobody reads a half-rewritten sheet, that page also gets a "work in progress" sign hung on it: everyone who passes has to wait. Finding a record costs three or four page turns. Changing one costs a full re-copy plus a queue of bystanders.

Why the old world is hard

One: change one character, rewrite a whole page. The page is the disk's unit; changing one byte costs about what changing the whole page costs.

Two: the higher the "work in progress" sign hangs, the worse the jam. Everyone passes through the topmost sheet of the index. Put a sign on it and all the machine's cores queue behind it.

Three: overwriting in place is itself risky. Lose power halfway through overwriting a page and you are left with a half-old, half-new mess — most of the ledger from the previous chapter exists to clean up after exactly this.

The core idea: four ways to stop editing the original

1. Re-copy instead of scribbling. To change a page, leave the original alone: copy it onto a fresh sheet and edit the copy, re-copying the signposts along the route from the cover down to it, then point the first line of the index at the new version — flipping that pointer is instantaneous, either old or new, never in between. Anyone reading the old version is entirely unaffected; readers never queue.

2. Stick notes on it, re-copy later. Instead of re-copying a page on every edit, stick a run of notes in the margin saying "this line now reads…", and let readers combine sheet and notes. Once the notes pile up, re-copy the whole thing once into a clean page.

3. File it in tiers. New changes go into the thin folder on top; when it fills, the whole folder is merged into a thicker one below, tier by tier. A finished folder is never edited again, so writing is always one continuous pass — exactly what flash likes, and the opposite of scattered little writes, which it hates.

4. Everyone cites door numbers, not addresses. Every signpost names a door number, and one registry maps "door number → current address". To change a page, write a small "change slip", pin it to the page, and repoint that one registry line at the slip — rewriting one registry line is a single indivisible instant, so nobody hangs a sign and nobody queues.

What it buys, and what it costs

Each trick cures one ailment: re-copying cures power loss and reader queues, margin notes cure "rewrite a page per character", tiered filing cures flash's dislike of scattered writes, door numbers cure queueing. The costs rhyme too: once a new version exists, someone has to sweep up the old one — the writes you save turn into space you occupy and background tidying you now owe.

One line to remember

The classic index tree is expensive to change, not to search. All four variants in this chapter attack the same assumption — does it really have to be edited in place? Stop editing in place and you get re-copying, note-sticking, tiered merging, or a pinned change slip plus a repointed door number. What you buy is power-loss safety, readers who never queue, and a shape flash likes. What you pay is space, and a tidying job that never ends.

Want the mechanisms, the notation and the diagrams? → Switch to the deep read

In one line

This chapter isn't a tour of four new data structures. It takes the bundle that is a B-Tree — page-organized + updated in place + protected by latches — and replaces the parts one at a time. The thesis is a single counterintuitive claim: a B-Tree's cost center moved long ago from "how many disk trips per lookup" to "how many bytes per change, and how many threads have to wait". So almost none of these variants exists to make lookups faster; they exist to write less, wait less, and suit flash better. And their first move is remarkably uniform: stop updating in place.

Glossary

Page: the smallest unit a database reads and writes, commonly 4–16 KB; one B-Tree node is usually one page.
In-place update: writing new content over the page's existing disk location — the classic B-Tree default.
Write amplification: bytes actually hitting the device per byte of useful data. Changing 100 bytes but rewriting an 8 KB page is 80×.
Space amplification: space actually occupied per byte of useful data, including in-page slack and old versions not yet reclaimed.
Latch: a mutex over a physical in-memory structure, held for nanoseconds to microseconds — a different animal from a lock, which is held for a whole transaction.
CAS (compare-and-swap): one atomic CPU instruction — "if this slot still holds the old value, install the new one, else tell me it failed". The bedrock of latch-free structures.
Latch-free / lock-free: threads make progress by retrying CAS rather than by excluding each other; a thread descheduled mid-operation stalls nobody else.
Copy-on-write (CoW): don't touch the original page — copy it, edit the copy, then atomically flip the pointer. Also called shadow paging.
Memory mapping (mmap): map the file into the process address space so reading the file is reading memory, with paging left to the OS.
MVCC: keep several versions of the same data; each read takes the version matching its point in time, so reads never block writes.
Delta record: a small record describing only what this change did, prepended to a node without touching the node itself.
Mapping table: a layer of indirection — pointers store logical page ids, and this table translates them to current physical addresses.
Reconciliation: combining "the on-disk page image + the updates accumulated in memory" into one clean, packed page, then writing it out.
Sorted run: a contiguous, key-sorted stretch of data that is never modified once written.
Fractional cascading: storing pointers into the next level inside the current one, so a level-by-level search need not re-search each level.
Erase block: flash cannot be overwritten in place; a whole block (often several MB) must be erased first, so scattered random writes trigger internal relocation.
Cache-oblivious: a layout that hard-codes no cache or page size, yet still achieves near-optimal I/O behavior.

Where it sits

This is Chapter 6 of Part I, "Storage Engines". Chapters 2–4 built the textbook B-Tree (structure, page formats, the engineering of splits and merges); Chapter 5 made it survive crashes and concurrency with a page cache, a write-ahead log and concurrency control. This chapter is the variation on that theme: if the classic B-Tree's pains all descend from updating in place, what grows when you drop that premise? It is also the bridge to what follows — Chapter 7's LSM-Tree pushes "never update in place, batch and write sequentially" to its limit — while the Bw-Tree's sibling pointers come from the B^link-tree mentioned in Chapter 5, and its snapshots share ancestry with Chapter 5's MVCC.

What the chapter is solving

At finding, the classic B-Tree is close to flawless: a billion records with a fan-out in the hundreds is four levels deep, so a point lookup is a handful of I/Os. Every problem is on the changing side, and it splits into three bills.

Bill one: write amplification. Changing a 100-byte record rewrites at least one 8–16 KB page — 80–160× at the page level alone. That's just the start. To stop a half-written page from leaving a torn page behind, engines pay a surcharge: MySQL InnoDB's doublewrite buffer writes each page twice, and PostgreSQL's full_page_writes stuffs an entire page into the WAL the first time it is modified after a checkpoint. Below that, SSDs manage erase blocks of several MB, so scattered random writes provoke internal relocation and stack on another layer. Updating in place is not a free default; it is the source of a stack of tax bills.

Bill two: concurrency. Chapter 5's latch crabbing already shortens how long the root is held, but it cannot dissolve one fact: every lookup and every modification starts at the root, and there is only one root. On today's 64–128-core machines the bottleneck is no longer disk seeks but cache lines bouncing between cores on those hot pages — one core touches the latch in the root and every other core's copy is invalidated. The more memory-resident and the more parallel the workload, the larger latching looms in the bill.

Bill three: fragmentation and space. Nodes typically sit around 70% full, and briefly 50% after a split; after enough inserts and deletes, in-page holes and out-of-order pages accumulate until a sequential scan degrades from "read straight through" to "hop around".

What if you don't fix any of this? Mostly nothing — mainstream databases have lived this way for decades. But in three settings the three bills turn fatal: write-heavy workloads (amplification eats bandwidth and SSD endurance), many-core in-memory databases (latching dominates everything), and embedded systems that must be usable the instant they restart. The variants here take aim at those three.

The core, properly explained

1. Copy-on-write B-Trees: turn "change" into "repoint"

The idea in one line: no page is ever overwritten. To modify a leaf, copy it and edit the copy; the copy lives at a new address, so the parent's pointer must change too — which means copying the parent as well, all the way to the root (this is path copying). Then one pointer, "where the root is", is atomically flipped to the new root. Before the flip the new tree does not exist to anyone; at the flip it exists entirely. There is no in-between state, so there is nothing for a log to clean up.

Fig 1 · A copy-on-write B-Tree: only pages on the modified path (purple) are newly written; the rest is shared with the old tree, whose root still describes a consistent snapshot.

It throws in three things for free. First, crash safety: the root pointer is either old or new, so what is on disk is always a consistent tree — no redo, no undo, usable straight after restart. Second, MVCC by construction: a read transaction grabs the root as of its start, and nothing a writer does can reach it, with not a single latch on the read path. Third, reads can go straight through a memory map: LMDB maps the whole database into the address space and returns data directly from mapped memory, with no malloc and no memcpy.

The costs land in three places, none of them light. One, single-write amplification is worse: in a four-level tree one changed record writes four new pages, so 100 bytes costs 32–64 KB. Two, there can be only one writer: path copying plus a root flip is inherently serial — writers can never deadlock, but write throughput is pinned to one thread. Three, reclaiming old pages: superseded pages go on a free list awaiting reuse, and as long as one old reader still pins the old root, not one of those pages can be reused — a read-only transaction running for half an hour visibly bloats the file, the same disease as a long transaction holding back PostgreSQL's vacuum.

2. Abstracting node updates and lazy B-Trees: split the in-memory form from the on-disk form

Copy-on-write fixed atomicity and read concurrency but not write amplification — one changed byte still rewrites a page. The lazy route comes at it differently: if rewriting a page is expensive, don't do it every time; accumulate updates in memory and compute a new page once enough have piled up.

The enabling insight is that a page's in-memory form need not equal its on-disk form. On disk it should be packed and scannable; in memory it can use pointers and skip lists, which suit the CPU. WiredTiger, MongoDB's default storage engine, works this way: once read in, the page image stays read-only, while new inserts and updates hang off that page in an update chain, and a read is the image plus the chain. Only when the page is evicted or checkpointed does reconciliation run, folding both into one clean page written out.

Fig 2 · The lazy move: updates land in an in-memory chain and are reconciled into a fresh page image only on eviction or checkpoint.

The arithmetic shows where the win is: if a page is modified 50 times between checkpoints, the classic engine flushes it many times, the lazy engine writes it once at reconciliation — amplification is amortized over the chain length. You pay with a heavier read path (two sources to merge) and updates sitting in memory unflushed, recoverable only via the write-ahead log. A relative on the same route is the Lazy-Adaptive Tree, which attaches buffers to subtrees rather than single pages and cascades updates down a level at a time when a buffer fills — already close to the flavor of the next chapter.

3. FD-Trees: a shape rearranged for flash

The first two moves stayed inside one tree. The FD-Tree changes the shape, for a very concrete reason: random writes are far costlier than sequential ones on flash, which cannot overwrite in place and must erase whole blocks, so small scattered writes provoke internal relocation. So: make every write sequential.

The structure has two parts: a small B-Tree on top (the head tree) holding the newest data, and beneath it several levels of immutable sorted runs whose capacity grows by a fixed ratio per level. New data enters the head tree; when it fills, it is merged with the next level into a new sorted run — and a merge is one pass written front to back, exactly what flash wants. There is no random write left on the write path.

Tiering brings a new problem: a lookup must visit every level, and a binary search per level is a random read per level. Fractional cascading is the elegant fix: the upper run stores pointers (the book calls them fences) into the matching position in the level below. Having searched level 1 you already hold "start here on level 2", with no second search. The original paper's result: updates cost O(logB n) sequential I/Os while searches cost O(logB n) random ones (B is the flash page size) — in plain words, lookups stay in the same league as a plain B-Tree while writes drop to the level of a write-optimized structure.

Fig 3 · The FD-Tree trades random writes for tiered sequential merges, then uses fence pointers to pull the cost of a multi-level search back down near single-level.

4. Bw-Trees: delete latching entirely

The Bw-Tree (Microsoft Research, 2013) goes after bill two. Its goal is extreme: not one latch anywhere in the tree, with all progress made by CAS. Three parts, none optional.

Part one: delta records. To modify a page, leave it alone and write a small record saying only what changed, pointing at the page — forming a delta chain. A read walks the chain from its head, applying changes onto the base page. A write drops from "rewrite a page" to "append tens of bytes".

Part two: the mapping table. This is the trick worth stealing. Every pointer in the tree holds a logical page id, not a physical address, and a mapping table translates ids to current addresses. Replacing a page therefore degenerates into changing one slot in that table — one CAS, atomic. Not a byte of the parent moves, which is precisely why latch-freedom is possible: modifying a page never requires holding its parent. A failed CAS just means someone else won; re-read and retry.

Fig 4 · The Bw-Tree's three parts: delta chains make writes cheap, the mapping table makes "replace a page" one atomic instruction, and consolidation plus deferred reclamation clean up after both.

Part three: consolidation and reclamation. Longer chains mean slower reads (the paper's own curves show throughput falling as the chain grows), so past a threshold the page is consolidated: base plus chain are folded into a new page and CAS'd into the table. The superseded page and deltas cannot be freed immediately — threads may still be reading them, and in a latch-free structure nobody announces they are done. The answer is epoch-based reclamation: park doomed objects in the current epoch and free them once every thread that entered it has left.

And splits? That is the hard part: a split changes two nodes, the node and its parent, while a CAS is atomic over only one location. So it is broken into two individually atomic steps. Step one installs a split delta on the node carrying a side link to the new sibling (the B^link-tree idea) — the structure is already usable, and threads arriving here follow the side link even though the parent knows nothing yet. Step two installs an index-entry delta at the parent. A thread that stumbles onto a half-finished split does not wait: it finishes step two on the other thread's behalf and moves on.

5. Cache-oblivious B-Trees: delete the page-size parameter too

The last route comes from algorithms — beautiful, rarely engineered. A classic B-Tree needs one tuning decision: how big a node must be to match the page size. But the storage hierarchy has many levels — L1/L2/L3, memory, SSD — each with its own block, and one node size cannot please them all. The cache-oblivious B-Tree flattens the tree using a recursive van Emde Boas layout: split the tree at half its height, store the top half and each bottom half contiguously, repeat. Now whatever block size the layer above reads with, the stretch it reads contains a contiguous slice of a root-to-leaf path, so near-optimal I/O falls out without knowing the block size. The cost is that maintaining the layout under updates is expensive — this is an idea to borrow from, not a production option.

Trade-offs and how to choose

Table 1 · Four routes: what each cures, and what it charges

	Copy-on-write	Lazy / buffered	FD-Tree	Bw-Tree
Treats	crash safety + read concurrency	write amplification	random writes on flash	latching cost on many cores
Key move	path copying + atomic root flip	updates into a memory chain, reconcile on eviction	tiered immutable runs + fence pointers	delta chains + CAS on a mapping table
Free upside	no WAL and no recovery path needed; readers get snapshots	n updates amortized into 1 page rewrite	the write path is entirely sequential	threads never block; a descheduled one stalls nobody
Main cost	per-write amplification ≈ tree height; one writer only; long readers pin old pages	reads merge two sources; unflushed updates need the log	read amplification across levels + merge writes	complex; pointer chasing hurts CPU caches; needs epoch reclamation
In the wild	LMDB (OpenLDAP)	WiredTiger (MongoDB), LA-Tree	research implementation; the idea lives on in LSM	nonclustered indexes on SQL Server memory-optimized tables

Table 2 · In-place vs not: one decision, a chain of consequences

	In-place (classic B-Tree)	Never in place (this chapter)
After a crash	pages may be torn, so a WAL must redo/undo, plus doublewrite or full-page WAL images	old versions are untouched and the switch is atomic — the lightest designs need no recovery at all
Readers vs writers	readers latch; they wait while a writer edits the page	the old version stays readable — snapshots / MVCC for free
Shape of writes	random, wherever the tree says	biased toward sequential (merges, appends) — friendly to flash
Space	compact; slack comes from in-page holes	room must be kept for old versions, so reclamation is mandatory
Who cleans up	little to clean, but recovery code is intricate	free lists, consolidation, epochs, reconciliation — saved writes become background work

Turning that into selection criteria:

Read-heavy, barely written, embedded in the process, must be usable the instant it restarts (config stores, directory services, local caches) → copy-on-write: no latches and no copies on the read path, no recovery procedure, provided you can live with one writer.
General OLTP with real write volume, compression and multi-core writers → the lazy/buffered route; this is exactly WiredTiger's position.
Writes far outnumber reads, on flash → the tiered-merge shape (the FD-Tree expresses it in B-Tree terms; industry's answer is the next chapter's LSM-Tree). Choose it only when you are willing to buy write amplification with read amplification.
Fully in memory, many cores, latch contention is the top bottleneck → the latch-free route. But read the controversy below before you commit.

Why it matters / in real systems

The value here isn't that you will go implement a Bw-Tree; it is a transferable map of trade-offs: immutability + indirection + buffering + deferred reclamation. ZFS and Btrfs share copy-on-write ancestry with LMDB; container image layers and Git's object store are also "never edit the old, only add new, then swap one reference". Any system that replaces in-place modification with "write a new copy, flip a pointer atomically" gains snapshots and crash safety, and simultaneously takes on a garbage-collection debt. In interviews, "why does LMDB need no WAL", "is latch-free always faster", and "why do write-optimized stores all look like tiered merges" are all this chapter.

EVIDENCE FROM INDUSTRY · not the book's claims, but what these companies published themselves

LMDB (OpenLDAP) states the payoff of copy-on-write as a definition in its official header: "Data pages use a copy-on-write strategy so no active data pages are ever overwritten, which also provides resistance to corruption and eliminates the need of any special recovery procedures after a system crash." The same passage adds: "Writes are fully serialized; only one write transaction may be active at a time, which guarantees that writers can never deadlock," and "The database structure is multi-versioned so readers run with no locks; writers cannot block readers, and readers don't block writers." A direct confirmation that an atomic root flip buys crash safety and snapshots for free.LMDB official source, lmdb.h (OpenLDAP repository mirror) ↗
WiredTiger (MongoDB's default engine) documents the lazy route in its architecture guide: "New key/value pairs are inserted into row-store leaf pages using a WT_INSERT structure. Existing entries on leaf pages can be updated, modified or deleted through WT_UPDATE structures. As new updates are made, these structures are chained into an update list"; a dirty page evicted from cache "goes through reconciliation".WiredTiger architecture guide · arch-btree ↗
MongoDB turns that machinery into a user-facing promise: "WiredTiger uses MultiVersion Concurrency Control (MVCC). At the start of an operation, WiredTiger provides a point-in-time snapshot of the data to the operation," and "WiredTiger uses a write-ahead log (i.e. journal) in combination with checkpoints to ensure data durability."MongoDB documentation source · WiredTiger Storage Engine ↗
Microsoft shipped the Bw-Tree in SQL Server, and its documentation is blunter than the paper: "Nonclustered indexes on memory-optimized tables are implemented using a data structure called a Bw-tree, originally envisioned and described by Microsoft Research in 2011"; a Bw-tree is "a lock and latch-free variation of a B-tree"; and an update means the engine "creates a delta record that describes the change, and appends it to the previous page. Then it also updates the page map table address for that previous page, to the address of the delta record."Microsoft Learn · SQL Server Index Architecture and Design Guide ↗
Microsoft Research's original paper (ICDE 2013) supplies the positive numbers — and its own boundary, since the evaluation is in-memory only: on a real Xbox LIVE workload (27 million get/set operations, read-to-write about 7.5:1), "the Bw-tree exhibits a throughput of 10.4M operations/second, while BerkeleyDB has a throughput of 555K operations/second, representing a speedup of 18.7x"; the write-heavier deduplication workload keeps an 8.6× speedup and the synthetic one 5.8×. Against a latch-free skip list it is roughly 3.7× (3.83 vs 1.02 M ops/sec).J. Levandoski, D. Lomet, S. Sengupta, "The Bw-Tree", ICDE 2013 ↗
The counter-evidence · CMU et al. (SIGMOD 2018) reimplemented the Bw-Tree and reached the opposite conclusion: "Unfortunately, the Bw-Tree papers from Microsoft are missing important details and the source code has not been released." Their optimized variant is 1.1–2.5× faster than the original proposal, yet the verdict is unambiguous: "despite our improvements, the Bw-Tree still does not perform as well as other concurrent data structures that use locks." The strongest available rebuttal to "latch-free must be faster".Z. Wang, A. Pavlo et al., "Building a Bw-Tree Takes More Than Just Buzz Words", SIGMOD 2018 ↗
The FD-Tree paper (VLDB 2010) describes its own structure and payoff: "an FD-tree consists of the head tree – a small B+-tree on the top, and a few levels of sorted runs of increasing sizes at the bottom", it "performs an update in O(logB n) sequential I/Os and completes a search in O(logB n) random I/Os", and the result is "a similar search performance to the standard B+-tree, and a similar update performance to the write-optimized B+-tree variant" — precisely the both-ends-covered outcome this chapter is after.Y. Li, B. He, R. J. Yang, Q. Luo, K. Yi, "Tree Indexing on Solid State Drives", VLDB 2010 ↗

Traps and controversies

Thinking copy-on-write saves writes. The opposite: per-write amplification is worse, since a whole path is copied. It wins elsewhere — no WAL, no torn-page doublewrite, no recovery path, and a snapshot thrown in. Score it end to end, not per write.
Reading LMDB's "lock-free" as high write concurrency. The lock-freedom is for readers; there is always exactly one writer. Stunning when reads dominate, a hard ceiling when writes do.
Forgetting that immutability bills you later. Someone must reclaim old versions: free lists for copy-on-write, epochs for the Bw-Tree, reconciliation and checkpoints for the lazy route. One long reader pinning old versions is enough to make the file grow without bound.
Equating the Bw-Tree's latch-freedom with speed. This is the chapter's live controversy. The SIGMOD 2018 reimplementation found that pointer chasing along delta chains, the extra hop through the mapping table and epoch reclamation together can outweigh the latches you removed, while optimistic lock coupling — readers validate a version counter instead of taking a lock — reaches comparable scalability far more simply. Latch-freedom is a trade, not free speed.
Mistaking the FD-Tree for an LSM-Tree. The shape rhymes (tiers, merges, sequential writes), but an updatable B-Tree still sits on top, and fence pointers exist specifically to hold down multi-level read amplification. It is a B-Tree borrowing from LSM, not LSM itself.
Period limits. The chapter's cost model rests on "random writes are far dearer than sequential ones" and "the page is the indivisible unit of I/O" — both being loosened by NVMe and byte-addressable persistent memory, while the B-Tree/LSM boundary keeps blurring. More fundamentally: none of these variants is a free lunch. They move cost from the write path to the read path, and from run time to the background.

Takeaways

① A classic B-Tree's cost center is changing, not finding: 100 bytes changed rewrites an 8–16 KB page, and latches must fend off concurrency. Every variant here attacks those two bills.

② The three bills: write amplification (80–160× at the page level, plus doublewrite / full-page WAL / SSD erase blocks), latching cost (cache-line contention on the root across cores), and fragmentation and space.

③ Copy-on-write: path copying plus an atomic root flip. Crash safety (you can drop the WAL entirely) and snapshot isolation come free; you pay per-write amplification ≈ tree height, a single writer, and old pages held hostage by long readers. See LMDB.

④ Lazy / buffered: accept that the in-memory form need not equal the on-disk form; updates hang in a memory chain and are reconciled into one new page at eviction or checkpoint, amortizing n changes into one rewrite. See WiredTiger.

⑤ FD-Tree: a small head B-Tree over tiered immutable sorted runs makes every write sequential, and fence pointers (fractional cascading) cancel the read amplification of searching many levels. It is the bridge to the next chapter's LSM.

⑥ Bw-Tree: delta chains (cheap writes) + a mapping table (replacing a page is one CAS, the parent untouched) + consolidation and epoch reclamation. Splits become two atomic steps held together by a B^link-style side link, and passing threads finish the job for you.

⑦ Cache-oblivious B-Tree: a van Emde Boas layout deletes "how big is a page" from the design. Lovely idea, costly to maintain, rare in practice.

⑧ The through-line: immutability + indirection + buffering + deferred reclamation — the writes you save reappear as space occupied and background work owed. The total does not vanish.

⑨ The counterintuitive conclusion worth keeping: latch-free does not mean faster. The vendor reports 18.7× (in memory, against BerkeleyDB); an independent reimplementation finds it still trails modern lock-based structures. Read whose experiment it is, on which workload, against what.