B-Tree Basics

In one sentence

The claim of this chapter: a B-Tree is not "a faster search tree" — it is "a search tree rewritten for block devices." What it optimizes is not comparisons but round trips to disk. Blow one node up to a full page, push the fanout from 2 to several hundred, and the height collapses from dozens of levels to three or four; then let it grow upward from the leaves, and it comes out perfectly balanced with no rotations at all. That is why it has been the default disk index for fifty years.

Glossary

Where it sits

Chapter 2 of Part I, "Storage Engines." It follows Ch1's three dials — a B-Tree is the classic occupant of the "buffered + updated in place + key-ordered" corner — and it sets up Ch3 (how bytes are laid out inside a page), Ch4 (splits, merges and concurrency in practice), Ch6 (variants) and Ch7 (its opposite number, the LSM-Tree). In the real world it maps onto the default index of essentially every disk-based OLTP database.

The problem the chapter attacks

Anchor it in something concrete: a 2-billion-row orders table, point lookups by order number at a p99 (the 99th slowest request in a hundred) under 10 ms, holding 50k QPS. A full scan is out. Keeping it all in memory is out too — at 200 bytes a row that is 400 GB. So the index has to live on disk, and disk does not bill you per comparison; it bills you per random I/O: roughly 10 ms on a spinning disk (about 100 IOPS per drive), 50–100 µs on an NVMe SSD.

What happens if you just move a textbook balanced binary tree onto that disk? Two billion rows means about log₂(2×10⁹) ≈ 31 levels — up to 31 random I/Os: 0.3 seconds on a spinning disk, still 2–3 milliseconds on SSD, and one query eating thirty IOPS of budget. So the task is: convert an in-memory search structure into one that is billed in page reads.

The core content, properly

1. Why an in-memory binary tree dies on disk

Petrov's reasons are blunt, and there are four:

• Fanout too low, so the tree is too tall. Two ways out per node gives height log₂ N — and the unit of height is not "levels," it is "trips to disk."
• Node granularity does not match page granularity. A binary node is a few dozen bytes; the disk hauls a whole page regardless. Fetching 32 bytes by moving 8 KB puts useful payload under 0.4%.
• Poor locality. Nodes are allocated wherever; a parent and child landing next to each other on disk is pure coincidence. Every "left or right?" is likely another random I/O.
• Rebalancing is expensive. AVL and red-black trees keep their shape with rotations — local pointer surgery that is nearly free in memory, but on disk means rewriting several pages every time.

Hence the hook of the chapter: you think a search structure competes on how many questions it asks; on disk it competes on how many trips it makes.

2. The rules changed: block devices bill per trip

Disks do not sell single bytes. Spinning disks read and write in sectors (512 bytes or 4 KB), the filesystem in pages (usually 4 KB), and the database layers its own page on top (4–16 KB). Reading one byte and reading a whole page cost about the same — the bill is the trip. SSDs go further: they cannot overwrite in place, their smallest erase unit is a block larger than a page, and an internal FTL (flash translation layer, mapping logical addresses onto real flash locations) shuffles things around.

One conclusion follows, and it dictates the whole chapter: the objective function changes from "fewest comparisons" to "fewest page reads." So a node should be exactly one page — if the trip is unavoidable, make everything it carries back useful. To size it: PostgreSQL's page is 8 KB, and at roughly "16-byte key + 8-byte pointer + 8 bytes of slot overhead ≈ 32 bytes" per index entry, one page holds about 250 signposts. Three levels then cover 15.6 million entries and four levels cover 3.9 billion — those 2 billion rows fit in four.

3. Anatomy: separator keys, fanout, occupancy

B-Trees came from Bayer and McCreight in 1972; Comer's 1979 survey The Ubiquitous B-Tree made them the textbook standard. A B-Tree generalizes the binary search tree: a node no longer holds one key and forks two ways — it holds a sorted run of keys and forks many ways. Three roles: the root (the single entry point), internal nodes (signposts only) and leaf nodes (the data, or pointers to it).

The structural fact worth memorizing: an internal node with n separator keys has n+1 pointers — n signposts carve the key space into n+1 ranges. Keys 50 | 90 carve out "<50", "50–90" and "≥90": three children. A lookup then starts at the root, binary-searches those few hundred separator keys inside the page (pure memory work, essentially free), picks a range, follows the pointer to the next page, and repeats down to a leaf. Total cost is log_k N page reads, where k is the fanout and N the entry count. Do not let the notation intimidate: it says one thing only — bigger fanout, shorter tree, fewer trips.

One more quantity people skip: occupancy. B-Tree pages are deliberately not full; the slack lets future inserts land in place instead of forcing an immediate split, and the classic invariant "every node but the root is at least half full" is exactly what keeps the height from degenerating. The price is space for time: an index is inherently puffier than the data it points at.

4. B+-Trees: what "B-Tree" almost always means in practice

A strict, original B-Tree happily stores data inside internal nodes. Nearly every real database uses the B+-Tree variant instead, with two changes:

• Data only in the leaves, internal nodes purely signposts. Each internal entry is therefore smaller → bigger fanout, shorter tree, and the whole internal level is small enough to stay resident in memory.
• Sibling pointers between leaves, chaining them in order. So a range scan becomes a linear walk — "the 1000 orders after March 1st" locates one starting point and follows the chain instead of climbing back to the root repeatedly.

Petrov says as much outright: since the differences are largely implementation detail, "B-Tree" in industry usage generally means this family. Being able to say "data in the leaves, leaves chained" is worth more in an interview than reciting the definition.

5. Inserts and deletes: a tree that grows from the leaves up

Insert: walk down to the target leaf exactly as a lookup would and slot the new entry into key order. If it fits, the whole insert is one page rewrite. If it does not (overflow), the page splits: it is cut in half and the middle key is promoted to the parent as a new separator. If the parent is now full too, it splits and promotes in turn. Only when the root itself cannot cope does the root split into a new root — and in that instant the whole tree gains a level.

That is the elegant part: it only ever grows taller at the root, yet the force driving that growth comes from the leaves. Because growth is a whole-tree event, every leaf stays exactly as far from the root as every other — perfectly balanced by construction, with no rotations whatsoever. The red-black trick of rebalancing locally simply does not exist here, and that is the second reason it suits disks.

Delete: walk to the leaf and remove the entry. If occupancy drops below the threshold (underflow), the page either borrows entries from a sibling (redistribution) or merges with one — the latter costs the parent a separator key and can cascade upward; when the root is left with a single child, the tree loses a level. One footnote from reality, though: many real engines defer or skip merging altogether (it locks several pages at once and is expensive under concurrency, while the payoff is only some space), preferring to let pages sit sparse and reclaim them with background maintenance. "The textbook says at least half full" and "your production index actually is half full" are two different statements.

The trade-offs that matter

Table 1 · The same data, two structures, billed on disk (2 billion rows, 8 KB pages)

Table 2 · B-Tree vs B+-Tree: why industry went one way

Table 3 · Choosing a page size, anchored on real defaults

The split point is a trade-off too, and a counterintuitive one: it should not always be down the middle. If the primary key is an auto-increment or a timestamp, every insert lands on the rightmost page; splitting 50/50 there leaves the left half stuck at 50% forever, with nobody left to fill it — the index puffs up to twice its necessary size. PostgreSQL's answer is to split the rightmost page lopsidedly, leaving the left page fillfactor full (90 by default for B-Trees). Conversely, a random key like a UUID spreads inserts evenly across every page, so splits happen everywhere and pages settle near half full — that is the mechanism behind "don't use a UUID as your clustered primary key."

When should you not pick a B-Tree? When writes far outnumber reads, keys are random, and space matters — updating in place means "change one row, write back a whole page," and random keys leave pages half empty. That is the home turf of log-structured storage (LSM-Trees, Ch7): it batches random writes into sequential ones, at the cost of searching several levels on read and compacting in the background.

Why it matters / in real systems

The roll call alone shows how universal it is: PostgreSQL's nbtree, InnoDB's clustered index (the primary key is a B+-Tree, and secondary index leaves store primary key values), SQLite, Oracle, SQL Server, MongoDB's WiredTiger, and bbolt underneath etcd — all B-Trees or B+-Trees. Understanding this chapter hands you a general-purpose wrench: why indexes aren't hash tables (hash point lookups are fast too, but hashes have no order, so range scans and ORDER BY are out); why an index scan costs so little in EXPLAIN (three or four levels, upper ones all in the buffer pool); and why DBAs keep insisting your primary key be monotonically increasing.

Common mistakes and open questions

• The "B" is not for binary. Comer's 1979 survey already notes that the original authors never explained what it stands for — balanced, bushy, Bayer and Boeing have all been guessed. Reading a B-Tree as a binary tree is the first trap, since it is precisely anti-binary.
• Conflating B-Trees and B+-Trees. What you run is almost certainly a B+-Tree: data in the leaves, leaves chained. Also, rotations belong to AVL and red-black trees; B-Trees have none.
• Assuming O(log N) means fast. The real cost is page reads and cache hits, not comparisons. A four-level tree with three levels resident in the buffer pool usually costs one physical I/O per point lookup — and that "one in practice" is the actual selling point.
• Assuming pages are always at least half full. That is the textbook invariant; real engines routinely defer or skip merges, so a delete-heavy table can sit sparse for a long time and needs a rebuild or reorganization to reclaim the space.
• Where the book shows its age. Written in 2019, it describes the classic disk-era form. Three developments have since pulled at its premises: multi-core concurrency produced latch-free variants (Bw-Tree); NVMe and persistent memory dropped the price of random I/O by two or three orders of magnitude, so "save a round trip" pays less absolutely; and write-heavy workloads have been widely displaced by LSM storage. But as long as random point lookups, range scans and block-billed storage coexist, the B-Tree remains the default answer.

Key takeaways