4.13.3 — B-Trees & B+ Trees: When the Tree Does Not Fit in Memory

A balanced binary tree holding 10 million rows has a height of about 24. Twenty-four comparisons is nothing — a few nanoseconds.

Now put that tree on a disk. Each node is a separate allocation somewhere in a file, so following a child pointer means a disk read. On a spinning disk a random read costs about 10 milliseconds; on a solid-state drive, about 100 microseconds. Twenty-four of them is 240 ms on spinning rust and 2.4 ms on flash — for a single row lookup, on a database that needs to serve thousands per second.

The tree was never the problem. The problem is that the cost model changed. In memory, the expensive thing is a comparison. On disk, comparisons are free and the expensive thing is fetching a node at all. When the cost model changes, the optimal structure changes with it, and the answer is the B-tree.

1. The insight: make the nodes enormous

Disks do not read bytes. They read blocks — a fixed unit, historically 512 bytes, now typically 4 KB, and databases usually work in 8 KB or 16 KB pages (Chapter 2.6 covers blocks, Chapter 7.3 covers database pages). Reading 1 byte and reading 8,192 bytes from the same page cost exactly the same, because the cost is the seek and the transfer of one whole block.

So a binary node holding one key wastes 8,190 bytes of a page it already paid for. The fix is to fill the page:

Make each node hold as many keys as fit in one disk page. Then the number of disk reads is the height of the tree, and the height collapses because the branching factor is huge.

A binary tree branches 2 ways per level. A B-tree node in an 8 KB page holding, say, 200 keys branches 201 ways. The height needed for n items goes from \log_2 n to \log_{201} n:

Rows	Binary tree height	B-tree height (fanout 201)
1,000	10	2
1,000,000	20	3
1,000,000,000	30	4

A billion rows in four disk reads. That single line is why every relational database index in the world is a B+ tree. And in practice it is better than four, because the top two levels are small enough to stay permanently in memory — so a billion-row lookup is often one or two actual disk reads.

The mathematics is just the change of base: \log_{201} n = \log_2 n / \log_2 201 \approx \log_2 n / 7.65. Complexity theory says \log_{201} n and \log_2 n are the same thing, because the base is a constant factor. This is a case where the constant factor is the entire point, and it is the clearest example in the book of Chapter 4.1's warning that big-O is silent about the multiplier.

2. What a B-tree node actually contains

A B-tree node with three keys and four children. The keys partition the value space into four ranges, and each child holds one range. Once the page is in memory, finding which range a target falls into is a binary search over an array of keys — a handful of comparisons that cost nothing next to the read that fetched the page.

A node with k keys has k+1 children, because k dividing lines cut a line into k+1 pieces. The keys inside a node are stored sorted, so searching within a node is a binary search over an in-memory array.

A B-tree of order m obeys:

1. Every node has at most m children.
2. Every node except the root has at least \lceil m/2 \rceil children — so nodes are always at least half full.
3. All leaves are at the same depth.

Rule 2 is the density guarantee: it stops the tree from degenerating into something skinny and wasteful, and it is what bounds the height. Rule 3 is why every lookup costs the same number of reads — there is no lucky path and no unlucky path.

3. Growing at the top: split and promote

A binary tree grows downward, adding leaves. A B-tree cannot, because rule 3 says all leaves must stay at the same depth. So it grows a different way, and the mechanism is worth walking through because it is what keeps the tree perfectly balanced with no rotations at all.

Insert. Walk down to the correct leaf and insert the key into its sorted array. If the leaf still has room, you are done — this is the common case, and it touches exactly one page.

Split. If the leaf is now over capacity, split it in half. The median key moves up into the parent, and the two halves become two children of that parent.

Take a node of order 4 (so at most 3 keys) already holding [10, 20, 30], and insert 25:

overfull: [10, 20, 25, 30]
              ↑ median is 25 (or 20 — implementations differ on which side)

split into:   [10, 20]     [30]
promote 25 into the parent, sitting between them

Cascade. If the parent is now overfull, it splits too, promoting its median one level higher. If this reaches the root and the root splits, a new root is created, and the tree gets one level taller.

That is the only way a B-tree ever gets taller: from the top, by the root splitting. Every leaf gains a level at the same instant, so rule 3 can never be violated. This is a genuinely elegant answer to a hard constraint, and it is the thing to say when someone asks how a B-tree stays balanced without rotations.

Delete is the mirror. Removing a key can leave a node below half full, which violates rule 2. The repair is to borrow a key from a sibling that has spare, or if no sibling has spare, to merge with a sibling and pull the separating key down from the parent. A merge can leave the parent under-full, cascading upward, and if the root ends up with no keys the tree loses a level.

In practice, many production B-tree implementations do not rebalance aggressively on delete at all. They mark space free within the page and let it be reused, because a strict merge on every delete generates enormous write traffic. PostgreSQL, for example, only reclaims a page when it becomes completely empty. This is the sort of gap between the textbook algorithm and the shipped one that is worth knowing about.

4. B+ trees: the variant databases actually use

A B+ tree makes two changes, and both are driven by the same workload observation.

Change one: all values live in the leaves. Internal nodes hold only keys, used purely as signposts.

In a plain B-tree, a key found in an internal node has its row data attached right there. In a B+ tree, an internal node holds nothing but keys and child pointers.

The payoff is fanout. An internal node's page is 8 KB. If each entry is a key plus a row's worth of data, maybe 30 entries fit. If each entry is a key plus a child pointer — perhaps 8 bytes and 8 bytes — around 500 fit. Higher fanout means a shorter tree means fewer disk reads, and since every query walks the internal nodes, that is where the savings compound.

A consequence: every search goes all the way to a leaf, even when the key appears in an internal node. The B+ tree accepts a slightly longer best case in exchange for a much better typical case. That is the right trade when the tree is 3 levels deep instead of 24.

Change two: the leaves are linked together in a sorted chain.

The B+ tree. Internal nodes are pure signposts, which maximises fanout and minimises height. The linked leaves turn a range query into one descent followed by a sequential walk — and sequential reads are the access pattern disks are fastest at.

This is why SELECT * FROM orders WHERE created_at BETWEEN '2026-01-01' AND '2026-03-31' is fast. Descend once to find January 1st, then walk the leaf chain until you pass March 31st. No tree traversal per row, and the leaves are usually laid out near each other on disk, so the walk is a sequential read rather than a series of random ones. Sequential reads are the one thing disks are genuinely good at — on a spinning disk, sequential throughput can be a hundred times the random-read rate.

A plain B-tree cannot do this. Its values are scattered across internal nodes, so a range scan means an in-order traversal jumping up and down the tree, which is a series of random reads.

This is the answer to "why are database indexes B+ trees and not hash tables". A hash index does exact-match lookups slightly faster and cannot do a range query at all. Chapter 7.3 develops the storage engine in full; Chapter 7.2 covers what that means for writing queries, including why WHERE UPPER(email) = ? cannot use an index on email.

5. Where B-trees show up outside databases

File systems. NTFS's master file table, ext4's directory indexing (HTree), Btrfs (the name is literally "B-tree file system"), XFS and APFS all use B-trees to map file names and block offsets to locations on disk. Chapter 2.6 covered the inode structure; the directory index sitting on top of it is a B-tree, which is why a folder with a million files is still fast to open by name.

Key-value stores. Any embedded storage engine that needs ordered iteration — LMDB, BoltDB, and SQLite's entire storage layer — is a B+ tree.

The alternative worth naming. LSM trees (log-structured merge trees) make the opposite trade: they buffer writes in memory and flush them as sorted files, so writes are sequential and extremely fast, and reads may have to check several files. That is the right choice for write-heavy workloads, and it is what RocksDB, LevelDB, Cassandra and modern time-series databases use. Chapter 7.3 compares the two properly. The short version: B+ trees optimise reads and update in place; LSM trees optimise writes and never update in place.

What the interviewer will push on

"Why do database indexes use B+ trees instead of red-black trees? Both are O(\log n)." The complexity is the same and the cost model is not. The unit of cost on disk is the page read, not the comparison, so you maximise the keys per node to minimise the height. Give the number: fanout 200 puts a billion rows within four reads, where a binary tree needs 30. A candidate who says "B-trees are faster" without naming the page has not understood it.

"Why not a hash index?" It cannot do range queries, ordered iteration, prefix matching or ORDER BY — not slowly, at all. Databases that offer hash indexes (PostgreSQL does) recommend them only for pure equality lookups on large values.

"How does a B-tree stay balanced without rotations?" It grows from the top. A node splits, promoting its median into the parent; if that cascades to the root, a new root is created and every leaf gains a level at the same moment. That is the only way it gets taller, so all leaves are always at equal depth by construction.

"What is the difference between a B-tree and a B+ tree?" Two things, and both need their reason. Data only in the leaves, which raises fanout and lowers height because internal nodes hold more keys per page. Leaves linked in sorted order, which turns a range scan into a sequential walk instead of a tree traversal.

"Your index is on (country, city). Can it answer a query filtering only on city?" No, and this follows straight from the structure: the tree is sorted by country first, so rows for one city are scattered across every country's section. This is the leftmost prefix rule, and it is the single most useful practical consequence of knowing what a B+ tree is. Chapter 7.3 develops composite indexes fully.

One thing to volunteer: mention that the top levels of the tree stay resident in the buffer pool, so a "four disk reads" analysis is usually one or two in practice — and that this is why index size relative to available memory is one of the numbers a database administrator actually watches.

Recall

• On disk the unit of cost is the page read, not the comparison, so a B-tree makes each node one page and holds hundreds of keys in it; fanout 200 puts a billion rows within four reads.
• A node with k keys has k+1 children; every node except the root is at least half full, and all leaves sit at the same depth.
• A B-tree grows upward: an overfull node splits and promotes its median to the parent, and when the root splits a new root appears, so every leaf gains a level at once. No rotations are needed.
• A B+ tree keeps data only in the leaves (higher fanout, shorter tree) and links the leaves in sorted order, which turns a range query into one descent plus a sequential walk.
• This is why database indexes are B+ trees: a hash index cannot do ranges, ordering or prefix matching at all.
• LSM trees make the opposite trade — sequential writes, more work on reads — and win on write-heavy workloads.

Self-test: Why is \log_{200} n versus \log_2 n a real difference here when complexity theory says they are the same? · How does a B-tree keep all leaves at the same depth without rotating? · Name the two changes B+ makes to B, and the reason for each · Why can an index on (country, city) not serve a query that filters only on city? · Which structure would you pick for a write-heavy time-series workload, and why?

Next: 4.13.4 covers the three specialised trees worth knowing by name — the trie for prefix work, and the segment and Fenwick trees for range queries over data that keeps changing.