Why B+ Trees: Fanout, Not Big-O

Every balanced search structure is O(log n) per lookup: AVL, red-black, treap, skip list, B-tree, B+ tree. If asymptotic complexity were the criterion, any of them would do and the simplest would win. Databases uniformly choose the most complicated one — pages with split and merge rules, separators duplicated in internal levels, sibling chains — and they do it because the constant hidden by Big-O is not a constant. It is the number of page reads, and a page read is between 10⁴ and 10⁵ times slower than anything the CPU does.

The lookup cost that matters is the height, in pages. Height is log_b(n), where the base b is the number of children a node has. A binary node has b = 2. A page-sized node has b = however many (key, child) pairs fit in a page. Everything else follows from that one difference.

A binary node holds one key and answers one question: left or right. To ask the next question you follow a pointer to wherever the next node lives — with a general-purpose allocator, a different page almost every time. Reading 8 KB to consume 20 bytes is 0.2% efficiency, and the disk does not care that you only wanted the 20.

A B+ tree page holds ~500 separators, sorted. One read brings in a whole subtree's worth of decisions; the in-page binary search costs 9 comparisons at nanoseconds each. The page is read once and used fully. The same locality is why range scans are cheap: leaves are neighbours in the file, and 500 sequential entries come out of one read. A binary tree's in-order traversal touches one page per key.

The principle scales down. CPU caches move 64-byte lines; a node sized to a cache line beats a binary node in RAM for the same reason. It scales up: a 16 KB InnoDB page has twice the fanout of an 8 KB PostgreSQL page and is a level shorter for the same key count.

None of this argument applies when there are no pages. In memory, a cache miss costs ~100 ns and a hit ~1 ns; 24 pointer chases are at most a few microseconds. Red-black and AVL trees are simpler to write and to update — no split or merge, no half-full pages, a rebalance touches a handful of nodes — and their O(log n) is perfectly good. Language runtimes use them for ordered maps because they are the right tool for RAM.

Skip lists are the other in-memory favourite: probabilistically balanced, no rotations, trivially lock-free for readers. Redis sorted sets (ZADD, ZRANGEBYSCORE) are a skip list plus a hash table, and the original in-memory row store of MemSQL/SingleStore used lock-free skip lists. Neither would make sense on disk — a skip list's towers are exactly the scattered pointer chase the B+ tree exists to avoid — and both make complete sense once the data is guaranteed resident.

Fanout is page size divided by entry size, and both are choices. Wider keys are the common way to lose: a 200-byte text key gives ~40 keys per 8 KB page and a tree two levels deeper than an 8-byte integer key. This is a concrete reason to index a surrogate integer key or a hash of a long string rather than the string itself, and why PostgreSQL rejects index entries above about a third of a page. Page size is the other lever, fixed per engine at build time: 8 KB in PostgreSQL, 16 KB in InnoDB by default.

Occupancy also matters: pages average ~70% full after random inserts, which lowers the effective fanout by the same factor. Bulk-loading sorted data can pack pages full (PostgreSQL fillfactor, InnoDB sorted index build) and shave a level off a large index.

The planner does not know the theory; it has random_page_cost and the index height from the metapage. Its estimate for an index lookup is roughly height × random_page_cost plus one random read per matching row, and it compares that with pages × seq_page_cost for the scan. That is why a B+ tree of height 3 wins for one row and loses for 30% of the rows: the tree is cheap, the random heap fetches it leads to are not. Cost-Based Optimization shows the arithmetic; Should I Add an Index? shows the consequences.