Every database index you have ever created is, in most engines, a B-tree. PostgreSQL, MySQL (InnoDB), SQLite, MongoDB — same family, same reason. The reason has nothing to do with computer science trivia and everything to do with the physics of reading from disk.
The constraint that shapes everything
Memory reads cost ~100 nanoseconds. Disk reads cost ~10,000,000 nanoseconds. That is a factor of 100,000, and it does not change by writing "better code" — it changes by reading less often.
An index's whole job is to answer "where is the row for this key?" with the fewest possible disk reads. The number of reads an index needs is called its height: a B-tree with height 3 touches exactly 3 pages to find any key. The question becomes: how do you pack so many keys into a tree that 3 levels cover a billion rows?
The trick: nodes as wide as a page
A B-tree node is literally sized to a disk page — in InnoDB, 16 KB, in PostgreSQL, 8 KB. The node is the unit of transfer: one physical read brings the whole node into memory, and the tree's fan-out (children per node) is therefore enormous.
Take a PostgreSQL page of 8 KB, with entries of roughly 200 bytes each after padding: a node can hold dozens of keys and child pointers. The math works out roughly like this:
height rows covered (fan-out ~40, 8 KB pages)
1 40
2 1,600
3 64,000
4 2,560,000
5 102,400,000Five disk reads to find any key out of 100 million. And here's the crucial part: the higher levels are almost always cached in memory, because they're small. The root page of a 100 MB tree fits in a few hundred bytes of RAM and probably never leaves it. In practice, a point lookup is one physical disk read at most — and usually zero.
A hash table, by contrast, can answer in exactly one probe. Why don't databases use that?
Why a hash index can't replace the B-tree
A hash index maps a key directly to a bucket — O(1) reads. Three reasons it can't win:
1. Ordering. A hash table can answer "give me the row for key 42", but it cannot answer
"give me all rows between 40 and 60" or "the first 10 rows smaller than 100". Both of those
queries walk the hash table in linear time. A B-tree's keys are sorted, so range scans and
prefix matches are just a walk along the leaf chain. The most common queries in real
applications — WHERE status = 'open', ORDER BY created_at LIMIT 10, WHERE name LIKE 'prefix%' — are range semantics wearing a disguise.
2. Inserts and deletes. A primitive hash index inserts in O(1), but the stored rows must live somewhere, and that somewhere has to preserve clustering so range and sequential access don't degenerate. Hash clustering costs you the sortedness you just gave up.
3. The leaf chain that does the real streaming. In a B-tree, all the data rows are reachable from the leaves, which are linked in sorted order. A full table scan on a B-tree index is an ordered sequential read — the fastest thing disks can do.
What the shape of the tree tells you
A B-tree's shape is a fingerprint of your workload, and it explains the most expensive queries in your system before your profiler does:
shallow, fat tree.........a point-lookup workload (everything hits an index)
tree with cache-missing
upper levels..............a table that's growing faster than memory
leaf pages half-empty.....an index on a volatile key (lots of updates/deletes)That last one is worth understanding. B-tree pages use a split (one page becomes two when
full) and merge (two become one when empty) discipline. A key that toggles back and forth
(status changing frequently, updated_at oscillating) causes pages to split and merge
repeatedly — fragmentation, measured as pages that are half-full, which means your index now
uses double the pages (and reads) it needs.
LSM trees: the other side of the trade
The B-tree's only serious rival is the LSM tree, used by RocksDB, Cassandra, and LevelDB. An LSM starts with in-memory tables, flushes them to disk as immutable sorted files, and merges them in the background. Its strengths are precisely the B-tree's weaknesses: writes never cause random I/O and never touch existing files, so write throughput is enormous.
Its costs are exactly where the B-tree wins: reads may have to check several immutable files (plus filters) before finding a key, and range reads must merge across files. A B-tree gives you predictable reads at the price of write amplification; an LSM gives you predictable writes at the price of read amplification and background compaction.
The takeaway
Indexes are not "like hash maps" and they are not "like sorted arrays" — they are data structures shaped by the cost of one physical read. A page, an 8 KB transfer unit, a tree wide enough to be 3 or 4 levels deep, leaves in sorted order: that combination is the answer engineers converged on in the 1970s and have never had cause to abandon.
Once you see the physics, a lot of database advice stops being folklore:
- "Keep your indexes in rows worth querying" — each index is another tree to maintain, per insert.
- "Use integer primary keys" — every secondary index stores a copy of the key; fat keys make fat trees.
- "Don't index columns you rarely query" — you're paying split/merge costs and page cache pressure forever.