Build a Database from Zero (Part 8): The B+ Tree — The Index Real Databases Use

• Solve the dilemma from Part 7 — "find fast, insert fast" — with a tree;
• Build the index real databases run on: a B+ tree, one concept at a time;
• See why it's the default: it keeps data sorted (so ranges work) and stays busy and shallow (so both find and insert stay cheap).

• Know Part 7: a sorted array finds in O(log n) but inserts are O(n) — the exact pain a tree fixes;
• Understand "divide and conquer" (binary search) — a tree is just a persistent, insertable version of that idea.

A sorted array is fast to find but slow to insert, because inserting shifts a huge contiguous run. The fix is to break the contiguity: instead of one big sorted line, split it into segments, and keep a small "index" that says roughly where each segment sits.

Let's build it in two steps: first a binary search tree (BST) to get the "insert without shifting" idea, then upgrade to a B+ tree — the thing databases really use.

A BST is a set of nodes. Each node holds a value and has at most two children: left = smaller, right = bigger. To insert 40 into [10, 20, 50], you don't shift anything — you compare and hang a new node:

Search follows the same forks: at each node, go left if smaller, right if bigger. No shifting, ever. Insert and find are both O(height). If the tree stays balanced, height is O(log n).

But a bare BST has a fatal flaw: insert ordered data and it degenerates into a tall skinny line:

That's the "insert fast, find slow" failure all over again. So we need the tree to stay balanced. That's the "B" part.

A B-tree's trick is: each node can hold many keys (not just one) and have many children (not just two). More keys per node → fewer levels → shallower tree → fewer steps to find.

Two rules keep it both ordered and compact:

1. Every node is at least half full (that's roughly the "balanced" guarantee);
2. All leaves are at the same depth (so every lookup takes the same number of steps).

The "B" is famously said to stand for the man who invented it (Bayer) — but the mnemonic "busy and shallow" is what actually matters.

A B+ tree is a B-tree with one crucial difference: all the data lives in the leaves, and the internal nodes hold only keys to steer (no data). And the leaves are linked left-to-right.

Why does that matter? Three things fall out:

1. Range queries are free: head to the leftmost relevant leaf, then walk right along the sibling links. Sweeping "50 to 100" just means walking the leaf chain — no backtracking up the tree.
2. The tree is shallow and fat: each leaf holds many keys, so even a billion rows need only a few levels to reach any leaf.
3. The internal nodes are small (just steering keys), so an entire level fits in tiny space — perfect for caching.

The whole point of a B+ tree over a plain sorted array: you get sorted-range sweeping and cheap inserts, because the sorted data is broken into a chain of leaves, and inserts only touch one leaf (occasionally splitting it) instead of shifting the whole array.

Let's implement a simplified B+ tree — a leaf can hold up to MAX keys; when it overflows we split it. Search is the part that matters most for now.

You can see the shape of the whole thing even in this skeleton: you descend by comparing against a few keys per node, until you land on a leaf, then you just check the leaf.

Real insertion needs to split a full leaf (and propagate a key upward when a split happens). But the search — the thing that makes an index fast — is already visible: it's "binary search down the levels, then one scan of a leaf." That's O(log n) with a small constant.

Now connect it back to everything you've built:

• Part 4: scanning a whole table is O(n) — that's Seq Scan.
• Part 6: a hash table finds one key in O(1) — but can't do ranges.
• Part 7: a sorted array does ranges — but inserts are O(n).
• Part 8 (B+ tree): both find and range are cheap; inserts graft at a leaf. This is why nearly every database's primary index is a B+ tree, not a hash and not a plain array.

And here's the payoff you've been climbing toward: if there's a B+ tree index on books.id, then SELECT * FROM books WHERE id = 42 doesn't scan — it walks the tree in a few steps. In EXPLAIN output you saw that as Seq Scan turning into Index Scan. You just built the thing that makes that happen.

1. Trace a search: insert 10,20,30,40,50 into a small tree and hand-trace contains(40) — how many nodes did you visit?
2. Reason about the leaf chain: with leaves linked left-to-right, describe how you'd answer 30 <= price < 70 using the chain.
3. Compare heights: roughly how many levels deep is a leaf with 100 keys per node, holding 1 million rows? (Hint: it's a few, not thousands.)

• A tree fixes "insert without shifting"; a balanced tree stays shallow and fast;
• A B+ tree puts all data in leaves, keys only in internal nodes, and links leaves left-to-right;
• This gives you range queries for free (walk the leaf chain) and cheap inserts (split one leaf) — solving the Part 7 dilemma;
• That's why the primary index in nearly every database is a B+ tree — turning Seq Scan into Index Scan.

Keywords: B+ tree、balanced tree、leaf、internal node、range query、leaf-linked、O(log n)、Index Scan

You've built the structure that makes a query fast. But stepping back: a B+ tree index contains keys and pointers — and it's separate from the rows themselves. So what would you store in it to point at a row? And what if the rows are stored sorted, versus sitting in a heap?

That's Part 9 — where you'll discover that an index stores addresses (not the data), and that "address" is exactly the TID we keep circling. You're about to see the other half of the story.