Implementing B-Trees

In one sentence

You think this chapter is about "the split and merge algorithm". In fact those two lines of pseudocode are the easiest part of it. The engineering is everywhere else: how you find the parent (breadcrumbs, not parent pointers), how you split less often (borrow from a sibling), how you stop sequential keys from wasting half your space (right-leaning splits), and how you get deleted space back (vacuum). This chapter stitches the tree shape of Chapter 2 to the page bytes of Chapter 3 into something that runs in production for ten years without breaking or bloating — it is the entire distance between the textbook B-Tree and the one inside PostgreSQL or InnoDB.

Glossary

Where it sits

This is Chapter 4 of Part I, "Storage Engines" — and the most engineering-flavoured chapter in that part. It follows Chapters 2 and 3: Chapter 2 argued why the B-Tree is the default answer on disk (high fan-out flattens the tree), and Chapter 3 gave the byte layout of a page (slotted pages, cells, the availability list). It sets up Chapter 5, "Transaction Processing and Recovery", where every split, merge and in-page compaction here needs a WAL behind it before it can claim correctness across a crash. In the real world: PostgreSQL's nbtree, InnoDB's clustered index, SQLite's btree.c — every mechanism in this chapter has an implementation, and a distinct set of trade-offs, in those three codebases.

The problem this chapter attacks

Carry the textbook B-Tree straight into production and you hit four walls.

Wall one: splits propagate upward, but a node has no idea who its parent is. A full leaf splits in two, so the parent must take a new separator key; the parent may be full too, so it continues upward, at worst all the way to the root — and when the root splits, the tree grows a level. But a page holds only keys and child pointers, with no route back to the parent. The naive fix is to store a parent pointer, and the cost shows up immediately: when a node splits, every one of its children needs its parent pointer rewritten — a node with fan-out 500 means 500 extra page updates, all of which must go through the WAL.

Wall two: halving splits make you buy twice the hardware. Split 50/50 on overflow and both new pages are half full; under random inserts steady-state occupancy hovers around 50%–70%. To put a number on it: a 100-million-row orders table, primary-key index at 16 bytes per entry, 8 KiB pages with fan-out about 500, comes to roughly 2 GB packed — and 4 GB at half occupancy. Those extra 2 GB don't just take disk; they crowd the page cache by exactly as much. An index that would have fit in memory no longer does, hit rate drops, and latency follows.

Wall three: sequential keys turn that waste into a dead loss. With an auto-increment or timestamp primary key, every insert lands on the rightmost leaf. Halving is especially foolish there: the left half can never receive another key, so it stays half empty forever. Occupancy is pinned at 50% when it could have been close to 100%.

Wall four: the holes left by deletes and updates don't disappear. A delete is only a mark plus an entry on the availability list (Chapter 3); a variable-length field grown by an UPDATE no longer fits in place, so it moves and leaves a hole behind. Once holes accumulate, a page's live payload may be down to thirty percent while it still occupies 8 KiB of disk, 8 KiB of cache, and a full-page read every time.

Table 1 · The textbook B-Tree vs what a production implementation must add

The core of it

1. A node that identifies itself: page header, rightmost pointer, high key

Beyond what Chapter 3 covered (magic number, cell count, free-space boundaries), a B-Tree page header must record the page's identity within the tree: leaf or internal. That decides how the cells are read — "key + value" in a leaf, "separator key + child page ID" in an internal node.

Then comes a detail that is easy to skip past and yet forces two schools of thought: an internal node has N separator keys but N+1 child pointers. Package "key + pointer" into one cell and the last pointer has no key to pair with — it owns the range above every separator. Two ways out:

• Rightmost pointer: put the odd pointer in the page header on its own. Simple and direct; SQLite does this.
• High key: give the page an upper bound — "no key in this page or its subtree exceeds this" — so the last pointer has a key after all. More importantly, the high key incidentally solves a hard concurrency problem: a reader arrives at a page, finds that the key it wants is above that page's high key, and instantly knows the page split while it was on its way; it steps right along the sibling link, never taking a read lock. This is the central trick of Lehman & Yao's 1981 B^link-tree paper, implemented directly in PostgreSQL's nbtree.

Sibling links are the header's other job: adjacent pages on a level point at each other. The benefit is concrete — a range scan (WHERE id BETWEEN 1000 AND 9000) sweeps along the leaf chain instead of climbing back to the parent after every page. The cost is equally concrete: every split, merge and page deletion must also fix up the neighbours, and under concurrency those pages sit behind different latches, so a careless ordering is a deadlock.

2. Binary search in a page: search the offset array, and return an insertion point

Having found the page, you still have to locate the key inside it. As Chapter 3 showed, in a slotted page the cells lie in arbitrary physical order, but the slot directory (the offset array) is sorted by key — so the binary search runs over that small, contiguous offset array: take the middle slot, follow its offset to read the key, compare, halve the range. An 8 KiB page holding 500 keys is done in log₂500 ≈ 9 steps, all within that one page, with no extra I/O at all.

One small design point deserves naming: "not found" is not a sufficient answer. An insert needs to know where to put the key; a range scan needs to know where to start sweeping. So implementations return the insertion point, commonly folding both results into a single value with a negative encoding such as -(insertion point) - 1: a non-negative result is the index of a hit, a negative one converts to the insertion position. One binary search, three kinds of caller.

3. Propagating splits, and why nobody stores parent pointers

Here is the chapter's first genuine engineering decision. After a leaf splits, the parent takes a new separator key; the parent may be full, so it continues upward; reach the root and the root splits, and the tree grows a level — the only moment a B-Tree ever gets taller, which is why it stays perfectly balanced for free. Only one question remains: how do you find the parent?

The intuitive answer is a parent pointer in every node. Petrov rules it out on two counts. Write amplification: when a node splits, the parent pointer of every child moved into the new node is invalidated, so a node with fan-out 500 means hundreds of extra page updates and hundreds of WAL records. Concurrent inconsistency: those pointers are scattered across hundreds of pages and cannot be made atomic with the split itself.

The real answer is breadcrumbs. A search already walks down from the root, so on the way down you push "which page I visited, which slot I took" onto a stack; when you need to propagate upward, popping the stack gives you the parent. The elegance is that the information is free — you had to walk that path to reach the leaf anyway.

One detail must still be handled: breadcrumbs go stale. Under concurrency, a parent recorded on your stack may itself have split while you were descending, so your separator key no longer belongs to it. Here high keys and sibling links save the day a second time: read the stacked page back, find the key above its high key, and step one page right along the sibling link — no need to restart from the root, and no need to hold locks the whole way down.

4. Splitting less: borrow from a sibling first

The second engineering decision targets occupancy. Since a split is both expensive (three pages plus WAL) and wasteful of space (two half-full pages), the move is to avoid it where you can: when a node fills, look at its siblings first and shift a few boundary keys to whichever one has room, updating the separator key in the parent. This is rebalancing.

That is the B*-tree idea: only when a node and its sibling are both full do you turn 2 nodes into 3. Do the arithmetic: an ordinary B-Tree guarantees each node is at least half full after a split, so minimum occupancy is 50%; splitting 2 into 3 leaves each node at least 2/3 full, raising the minimum to about 66%. For the same data, the index is a quarter smaller and the page cache holds a quarter more of it.

The cost is not subtle: one operation now touches two or three pages (self, sibling, parent), which under concurrency means holding two or three latches — the acquisition order has to be globally consistent or you deadlock — and write amplification goes from "one page" to "three". It is a trade of write-path complexity and latency spikes for space and cache hit rate, and not every engine takes it. The same logic runs in reverse for merges: attractive on paper, but they too touch several pages and can thrash against splits (merge, refill, split again) — which is precisely why PostgreSQL declines to merge half-empty pages at all.

5. Right-only appends and bulk loading: sequential keys deserve their own lane

This is the section closest to daily life. Your primary key is most likely an auto-increment ID, a timestamp or a snowflake ID — all monotonically increasing, so every insert lands on the rightmost leaf. Generic logic loses on every count here, which is why implementations open special lanes.

Lane one: right-leaning splits. When the rightmost leaf fills, don't cut down the middle — keep almost every key where it is and move only the last handful into the new page. The reasoning is airtight: the left half can never receive another key (new keys are only larger), so halving locks half that space away permanently. InnoDB's real occupancy figures bear the bill out — the gap between sequential and random inserts is nearly a factor of two; the official numbers are in the evidence box below.

Lane two: cache the rightmost leaf. If inserts always land on the same page, don't walk from the root every time. PostgreSQL's nbtree caches the leaf the last insert hit, and if it is still the rightmost leaf, still has room, and the new key exceeds the page's first key, it inserts straight into it — a path called the fastpath. It ships with its own brake: every writer then contends for an exclusive lock on that same page, so if the lock isn't available the code falls back to the ordinary path.

Lane three: bulk loading. When the data is already sorted (an import, an index rebuild, the output of an LSM compaction), inserting one row at a time is pure waste. The right move is to build bottom-up: pack the sorted data page by page into a leaf level, take the first key of each leaf to form the level above, and repeat until one root remains. Zero splits, zero searches, pages packed to nearly 100%, and purely sequential writes. MySQL calls this a sorted index build and takes that path by default when creating or rebuilding an index. It is also why the classic advice holds: when loading an empty table, load the data first and build the indexes last.

6. Compression: granularity is the only question

Compression saves disk and I/O at the cost of decompressing on every read. Petrov flattens the choice to one question: at what granularity?

• The whole file: best ratio, but individual pages are no longer addressable — a B-Tree locates page n at n × page size, and compressing the file destroys that premise. Essentially out.
• Per page: the mainstream compromise. Pages stay addressable, and reading one cell means decompressing a whole page — which you had to read whole anyway. The nuisance is that compressed length varies, so you need extra bookkeeping for where each page landed and how big it is.
• Per cell / row: finest granularity and cheapest decompression, worst ratio — there is too little context to find redundancy in a few dozen bytes.

There is also a saving that doesn't touch the layout at all: deduplication. PostgreSQL 13's B-Tree deduplication is the model — when one key value repeats many times (indexing a low-cardinality status column, say), the duplicates are merged into a single "key + list of row pointers" posting list with the key stored once, saving space and incidentally deferring leaf page splits.

7. Fragmentation, vacuum and page reclamation

Finally, maintenance. Two sources produce dead space continuously: deletes (a mark plus the availability list, Chapter 3) and updates (a variable-length value grown too large to fit in place has to move, leaving a hole). The result is that live payload per page keeps falling while the page count does not — disk, page cache and full-page reads all cost exactly as much as before. The response has two layers: within a page, repack the live cells together (at the cost of rewriting the page); across pages, unlink fully empty pages into a global free-page list for later splits to reuse — note that the latter usually does not shrink the file, it only makes the space reusable.

One real-world divergence is worth knowing. PostgreSQL reclaims only pages that have become completely empty — a page down to its last few keys stays allocated, so a pattern where "most keys in a range are eventually deleted" wastes space indefinitely. InnoDB takes the other road: once occupancy falls below MERGE_THRESHOLD it merges with a neighbouring page, at the cost of thrashing between merge and split when both pages sit near the threshold. One problem, two trade-offs, and both vendors write the cost down honestly in their own documentation (quoted in the evidence box below).

Key trade-offs

Table 2 · How to find the parent node

Table 3 · What to do with a full node: four split strategies

Table 4 · Reserve and reclamation: the real defaults

Why it matters / in real systems

You can justify a primary key choice. "Why is a UUID v4 primary key slow" is not folklore: random keys spread inserts evenly over every leaf, so each one has to be read into the page cache, dirtied and written back, with splits everywhere. Switch to a time-ordered ID (auto-increment, UUID v7, snowflake) and inserts concentrate on the rightmost page, taking the right-leaning split and the fastpath — roughly halving index size and roughly doubling how much of the index fits in cache. That conclusion has vendor documentation behind it.

You load data the right way. A hundred million rows into an empty table: maintaining five indexes as you go means a hundred million rounds of "walk root to leaf, maybe split, write WAL". Load the data first and run CREATE INDEX last and you get sort plus bottom-up build — sequential I/O, zero splits, pages packed nearly full.

You know where to look when debugging. "The table is 3 GB, the index is 12 GB, and VACUUM didn't shrink it at all" is almost always section 7 above; getting the space back means REINDEX. Conversely, periodic write-latency spikes on InnoDB should send you straight to merge-split thrashing around MERGE_THRESHOLD.

Pitfalls and open arguments

• Reading "a B-Tree is at least half full" as good news. It is a lower bound, not a target — real workloads sit at 50%–70% for years, meaning a third to a half of the disk and memory you bought for the index is holding air. Most of this chapter (rebalancing, right-leaning splits, bulk loading, deduplication) is a fight with that number.
• Assuming splits are rare. Under random keys and heavy writes, splits are the norm. One leaf split changes at least 3 pages (old leaf, new leaf, parent) and writes them to the WAL; PostgreSQL additionally writes a full-page image the first time a page is touched after a checkpoint. A logical "insert one row" can be tens of KiB on disk.
• Taking parent pointers for granted. In-memory trees nearly always store them; on-disk B-Trees nearly never do. The difference is one thing: changing a pointer in memory takes nanoseconds, changing a page on disk goes through the WAL, the page cache and eventually the platter. Same data structure, different medium, completely different optimum.
• Expecting deletes to shrink the index. They don't. In-page space goes onto the availability list to await reuse, and page-level reclamation only returns empty pages to a global list — the file size typically does not budge. Actually shrinking it means REINDEX / VACUUM FULL, and the cost is a rebuild.
• Setting fillfactor to 100 across the board. The temptation is real (smallest index, best cache hit rate), but outside a static table this gives back all your headroom, and every subsequent middle insert can trigger a split immediately. PostgreSQL defaults to 90 rather than 100 for exactly this reason.
• Limits of its era, and live arguments. The whole calculus here assumes "block device, update in place, page changes go through the WAL", and three developments are eroding it: LSM-trees (Chapter 7) abandon in-place updates and trade split/fragmentation problems for background compaction; lock-free variants like the Bw-tree (Chapter 6) use delta records and a mapping table to avoid modifying pages in place, which invalidates this chapter's latching and split propagation entirely; and NVMe and persistent memory are loosening the axiom that random I/O is expensive, shifting the optimum for fan-out, page size and split policy. Separately, PostgreSQL's refusal to merge half-empty pages is a space cost paid for concurrency correctness and implementation simplicity, argued over for years and still unchanged; InnoDB chose the other side and documented its thrashing cost just as honestly. No right answer — two different bills.

Takeaways