Index Internals

With no index, `WHERE email = ?` is a loop over every page of the table file: fetch page, test each row, fetch the next page. It is linear, it cannot stop early without a uniqueness guarantee, and it is the cheapest I/O per page the storage layer can do — which is exactly why the planner keeps choosing it.

Start from "how can we avoid reading every page?" and you are forced, step by step, into a sorted array of (key → location), then binary search, then — because the array outgrows memory and storage is read in pages — into pages of entries with a page of separators, and finally a tree of pages. Nobody designed the B+ tree; it is what falls out.

A B+ tree is a set of numbered pages: one root, internal pages of separator keys and child page ids, and leaf pages of (key → row locator) entries chained left to right. Lookups read one page per level; inserts split a full page and push a separator up; deletes borrow from or merge with a sibling. Every rule exists to keep pages between half-full and full and all leaves at the same depth.

A balanced binary tree and a B+ tree are both O(log n). One of them is 24 random page reads for 10 million keys and the other is 3. The base of the logarithm is the fanout, the fanout is how many decisions fit in one page, and a page is the unit of I/O — that is the whole argument, and it flips completely in memory.

A hash index skips the tree entirely: hash the key, take a bucket number, read that bucket, find the record reference. One page for equality, no matter the size. The price is that the hash destroys order — no ranges, no prefixes, no ORDER BY — and that buckets fill up: collisions chain into overflow pages and growth means rehashing.