The Index, Derived from First Principles

The scan wastes work because it cannot rule anything out before looking at it. Sorting rules things out: if the entries are in key order, one comparison against the middle entry discards half of them. So keep a separate array of (email, page, slot), sorted by email, and search it by halving. For 16 entries that is 4 comparisons; for 10 million, 24.

The array is *metadata about the table*, not the table. The rows stay where they are in the heap file; the index only knows where each one is. That separation is what allows many indexes on one table and is why the leaf entry of every real index ends in a row locator.

One entry per row, 16 bytes each: 10 million rows is 160 MB, a billion is 16 GB. As long as it fits in RAM, binary search is 24 comparisons and no I/O. Once it does not, the array lives in the file, and binary search becomes the worst possible access pattern for a disk: the first probe is at the middle of the file, the second a quarter away, the third an eighth — every probe a different page, none of them predictable by read-ahead.

24 random page reads at ~100 µs is 2.4 ms per lookup on an SSD, and 240 ms on a spinning disk. That is faster than the scan, but it is 24 reads to make 24 comparisons: one page fetched per useful comparison. The page holds 512 entries and we used one of them.

The waste is obvious once stated: a page delivers 512 entries at once, so binary search *within* a page is free after the fetch; the expensive part is choosing which page. So arrange the sorted array in page-sized chunks and keep a directory with the first key of each chunk. Reading the directory tells you the one leaf page that can hold the key; reading that page finishes the search.

Two page reads, both chosen deliberately, instead of 24 scattered ones. The directory for 10 million entries is 20,000 keys — which is 40 pages, and already too big to read at once. The next stage handles that.

The separator page is a sorted array of (key → page) with the same problem the original array had, so it gets the same solution: cut it into pages and give it a separator page of its own. Repeat until a single page is left. That page is the root; every level below it is a directory; the bottom level is the original sorted entries. A lookup reads one page per level.

The fanout does the work. With ~512 entries per 8 KB page, one level of separators covers 512 leaves, two levels 262,144, three levels 134 million leaf pages — or 68 billion entries. Nothing you will ever index needs more than five levels, and the root plus the next level are a few hundred pages that never leave the buffer pool. A lookup that reads three pages typically performs one real disk read.

Each part of the B+ tree corresponds to a stage: leaves are stage 1 cut into pages, separators are stage 3, internal levels are stage 4. Two facts forced the shape — storage is read in pages, and the index is larger than memory — and neither has anything to do with Big-O. Why B+ Trees: Fanout, Not Big-O makes that argument quantitative.

It also explains what the structure cannot do: it is sorted on one key (or one composite key), so it answers equality, ranges, prefixes and ordering on that key and nothing else; see Composite Indexes and the Leftmost-Prefix Rule for the leftmost-prefix consequence. And it explains the cost: every insert lands in a specific leaf and must keep the page sorted and within capacity, which is where B+ Tree Internals: Pages, Splits, Merges picks up.