B-tree: a short, fat, always-balanced tree, priced in page reads

What it is for. A table holds hundreds of millions of rows on disk, stored in fixed-size pages. Finding one row must cost a handful of page reads: a full scan is unaffordable, and the index itself is far too big to keep in memory.

Three structural properties (of the B+ tree, the variant databases actually use).

Sorted — globally, not approximately. Keys are sorted inside every node, and internal separator keys partition the whole key space into ranges: everything in a left subtree is smaller than the separator, everything in a right subtree larger. An in-order traversal yields the fully sorted key sequence, and every key has exactly one place it can live. Sortedness is what makes location possible at all.

Leaves linked. Every leaf page carries prev/next pointers, so the leaves form a doubly linked list in key order — logical order, which need not match physical placement on disk. A range scan descends once to the starting leaf, then walks sideways page by page instead of re-descending per key. This chain is also what InnoDB's gap locks and next-key locks take a segment of (see isolation-levels). Its wear pattern is fragmentation: over time, logically adjacent leaves drift physically apart, and sequential range reads decay; rebuilding the index is the cure.

Always balanced. Invariants: all leaves sit at exactly the same depth, and every non-root node stays between half-full and full (under random inserts the average fill settles near 69%). Balance is not restored by periodic rebalancing — there are no rotations like an AVL tree's. It falls out of the growth rule in the insertion algorithm below: the tree may only grow taller at the root, so no branch can ever outgrow another.

Size arithmetic — where "four levels" comes from. Fanout ≈ page size / (key + pointer) ≈ 500 for an 8KB page. Capacity by depth: 1 level, 500 keys; 2 levels, 250 thousand; 3 levels, 125 million; 4 levels, 62.5 billion. No rule anywhere caps the depth at four — nothing stops a fifth level. Four is simply what falls out of realistic table sizes, and since the top levels live permanently in the buffer cache, a "4-level" lookup is usually one real disk read. What the engine actually fixes is the page size (8KB PostgreSQL, 16KB InnoDB); the depth is its shadow.

The insertion algorithm. Three causal rules decide everything; every step below is a combination of them. (1) Routing: separators are signposts — smaller goes left, larger goes right — so the landing leaf is unique. (2) Capacity: a node is one disk page; a page has a fixed size, so a maximum key count is physics, not policy. Full (= max) is legal; asking the node to hold max+1 keys is not — such a node cannot exist as one page and must split. (3) The boundary: when a node splits in two, the parent needs a new separator distinguishing the halves — smaller-than-me to the left, larger to the right. The key that rises is the one standing between the halves. The rise propagates upward and stops at the first ancestor with room; if it reaches a full root, the root splits and a brand-new root is created — the only way the tree ever gains a level, which is exactly why all leaves remain equidistant.

Worked example (toy version: max 3 keys per node; real fanout is hundreds, rules identical). Insert 1, 2, 3 → root [1,2,3]: full, and full is legal — nothing happens. Insert 4 → the root would hold 4 keys: overflow. It splits into [1,2] and [4], and boundary key 3 rises into a new root [3]. Height becomes 2 — through the root, as the rule demands. Insert 5, 6 → route right of separator 3, land in [4], now [4,5,6]. Insert 7 → that leaf would hold [4,5,6,7]: split into [4,5] and [7]; boundary 6 rises into the root, which had room (1 → 2 keys) — so the cascade stops there: root [3,6], leaves [1,2] [4,5] [7], leaf pointers re-stitched. Insert 8, 9 → route right of 6, leaf becomes [7,8,9] (full, legal). Insert 10 → overflow again: split [7,8] and [10], boundary 9 rises → root [3,6,9]. Ten inserts, exactly three structural events

Deletion mirrors insertion. A node that drops below half-full first borrows a key from a sibling through the parent; if the sibling has none to spare, the two merge and the parent's separator comes down; if the root empties, it is removed and the tree shrinks a level — again, height changes only through the root.

The bill. Lookups are uniformly cheap: worst case ≈ average case, 3–4 page reads, and no input order can degrade the structure (sorted insertion merely splits at the right edge repeatedly). The price is paid on writes: they land in the middle of the structure — random I/O, page splits, fragmentation. That bill is what wal-style thinking, and ultimately LSM trees, exist to refinance: convert random structural writes into sequential appends. See also io-block-size-and-iops for why random page reads are the currency here.

Postscript — the letter B. What "B" stands for was never defined by its inventors, Bayer and McCreight (1970). Candidates: Balanced, Bayer, Boeing (their lab), Broad. The honest answer — "officially undefined; usually taken as Balanced or Bayer" — is the interview-safe one.