Why Disks Break Ordinary Search Trees
A binary search tree answers a lookup in about $\log_2 N$ comparisons when it stays balanced. Each node holds one key and two child pointers, so every comparison throws away half of what's left. In memory, that is fast enough that nobody worries about the shape of the tree. Put the same tree on a disk and the cost changes completely. The comparisons are no longer the expensive part. Getting to the node is.
This matters because most real databases hold far more data than fits in memory. The index that finds a row among a billion rows has to live on disk, and every step of a search may force the storage device to do work. If you design the index as though a step costs a few nanoseconds, you get a structure that looks elegant on paper and crawls in practice. The rest of this chapter explains where the extra cost comes from, and why it pushes database indexes toward a very different shape.
Disks Hand You Blocks, Not Bytes
A disk does not give you the one byte you asked for. It gives you a block, a fixed-size chunk of data that the operating system reads in one operation. On most systems the block is 4 KB, though the exact size varies by device and file system. Asking for a 100-byte node costs the same device operation as asking for the whole 4 KB around it.
Think of a warehouse that ships only pallets. You ordered one sugar packet, and the pallet arrives anyway. The shipping cost is paid per pallet, so the packet's weight does not matter much. The trip is what costs money.
The gap between storage types is also large. Here are rough, order-of-magnitude latencies for one random read:
| Storage | Random read latency (approximate) |
|---|---|
| DRAM (main memory) | 100 ns |
| SSD | 100 µs |
| Spinning hard disk | 5–10 ms |
A spinning disk has to move a physical arm and wait for the platter to rotate under the head. That is why a random read costs milliseconds, while a memory access costs about a tenth of a microsecond. The gap is roughly a factor of 50,000 to 100,000. Any algorithm that pays for each random access will feel that gap immediately.
Counting Block Reads Instead of Comparisons
When the data lives on disk, the number that matters is the number of block reads. Comparisons inside a block are almost free by comparison. Your search tree now has a new cost model: how many distinct blocks must I fetch to find this key?
For a binary tree with one node per block, the answer is the depth of the key. A tree with $N$ keys has depth about $\log_2 N$, so a lookup reads about that many blocks. Take a million keys:
$$\log_2 (10^6) \approx 20$$
Twenty reads sounds modest. On a spinning disk at 10 ms each, the lookup takes about 200 ms. The same twenty steps in memory take about 2 µs. A user waiting for a query notices the first number and ignores the second.
A common wrong intuition is that $O(\log N)$ is $O(\log N)$, whatever the machine. Big-O notation hides the constant, and on disk the constant is the whole story. Two trees with the same asymptotic depth can differ by a factor of ten in real latency, depending on how many keys each read gives you. The question is not only how fast the depth grows, but how many useful decisions each disk read buys.
Why Each Node Lands in Its Own Block
A binary tree is usually built by allocating nodes one at a time. Each node is placed wherever there is free space, and its children may land in completely different parts of the storage. The parent's child pointer then points to a random location, so each step down the tree is a random read.
Random reads are the expensive kind. A sequential scan lets the device stream data in large, predictable runs, and it can prefetch ahead. A pointer chase jumps from location to location, and the device cannot predict the next jump until the current read returns. Every hop waits for the one before it.
The waste is worse than the randomness. A 4 KB block holding one 64-byte node uses about 1.5% of what you paid to read. The other 98.5% is data you will never look at for this search. The operating system's page cache may keep a few hot blocks around, but a binary tree spreads its frequently used top levels across many blocks, so the cache cannot hold them all. Each lookup pays the full cost of dragging in a nearly empty block at every level.
Updates Touch Several Blocks at Once
Lookups are only half the problem. Inserting or deleting a key can change a node's contents and its parent's pointers, and sometimes rebalancing changes several nodes along a path. On a disk, each changed node is a separate write to a separate block.
Writes to disk do not all happen at the same instant. A power cut can land between two of them, leaving the tree with a parent pointing at a child that was never written, or a half-updated node. In memory, a crash throws the whole structure away and you start over. On disk, the broken structure survives the crash and sits there, looking like a valid tree until someone searches it.
Real systems solve this with a logging and recovery scheme that groups related block writes into a unit that either fully happens or fully does not. The mechanics belong to the transaction and recovery material. For now, the lesson is simpler: a disk-resident structure must be designed to be safely changed, not just safely read.
Why a Wider Tree Helps
If each disk read is expensive and mostly wasted, the fix is to make each read do more work. Instead of one key and two children per node, put many keys and many children in one block. A node that branches 100 ways lets you skip 99 of every 100 choices with a single read, and the depth of a million-key tree falls from about 20 to about 3.
This is the core move behind the B-tree. The tree is shallow and wide, and each node fills a whole block. The number of children a node can point to is called its fanout, and a block-sized node is what makes large fanout possible. How nodes are packed into pages, and how a search walks down a wide node, are the subjects of the sibling topics on pages and fanout and on searching. What matters here is the reason. A binary tree is a fine answer to a question about comparisons. A disk asks a different question, about how many blocks you must touch, and a wide tree is the shape that answers it well.
AI-generated study article from SophistAI. Sign up free to study it with an AI tutor.