Answers · Making it fast enough

Why do databases use B-trees rather than binary search trees for indexes?

In shortBecause a database index pays for disk blocks read, not comparisons made, and a wide shallow tree needs only a few block reads per lookup.

A B-tree wins because a database index is charged for disk blocks fetched, not for comparisons made, and a wide shallow tree fetches far fewer blocks. A binary search tree halves the candidates at every step, but it does so at a different node each time, and on disk each of those steps can be a separate read.

The cost that matters

Storage returns a block, often four kilobytes, whether the caller wanted one byte or the whole block. Reading one small node and reading a full block cost the same, so the honest count for a lookup is the number of blocks touched. Comparisons inside a block already in memory are cheap beside that fetch. This is why a database can make the same promise for a table of a million rows and a table of a thousand million: the number of fetches stays small.

d = \log_b n = \frac{\log_2 n}{\log_2 b}

Here $n$ is the number of items, $b$ is the number of ways out of a node, one more than the keys it holds, and $d$ is the number of levels, which is the number of fetches. For a thousand million items, $\log_2 1{,}000{,}000{,}000 \approx 29.9$ , so a binary tree is about 30 levels deep. With $b=256$ , $\log_2 256=8$ , and $29.9/8 \approx 3.7$ , so four fetches reach the bottom. Widening from two ways to 256 ways divides the depth by eight.

At a million keys the same arithmetic is easy to check by hand. A million keys fit under 256 ways in three levels because $256^2=65{,}536$ is too small and $256^3=16{,}777{,}216$ is enough. A binary tree needs 20 levels because $2^{19}=524{,}288$ is too small and $2^{20}=1{,}048{,}576$ is enough. The wide tree therefore visits three blocks, and inside each block a binary search over at most 256 keys takes at most eight comparisons. The binary tree makes about 20 comparisons, but those comparisons sit on 20 separate node visits. If the nodes are scattered on disk, the binary tree pays 20 fetches and the wide tree pays three.

The natural guess

The natural guess is that the structure with the smallest comparison count wins, so a binary tree should be better. That guess counts the wrong operation. The binary tree's 20 comparisons are 20 node visits, and if each node is a separate disk block, 20 block fetches. The wide tree may make more comparisons in total: three in-node searches of up to eight comparisons each come to at most 24, against the binary tree's 20, and it still wins because all 24 happen after a block has arrived. One fetch brings back hundreds of keys, and the search inside that block uses ordinary comparisons at memory speed. More comparisons and fewer fetches beats fewer comparisons and many fetches.

FIG 1

shape	keys per node	levels	block fetches for one lookup
binary tree, one key per node	1	20	20
wide tree, block sized nodes	255	3	3

Why not make it wider

Widening has diminishing returns because the depth has $\log_2 b$ in the denominator. Going from 2 to 256 divides the depth by 8. Going from 256 to 65,536 divides it by 16, only twice the gain of 256, while each node becomes 256 times larger. Beyond a block, a node either spans several blocks, so a lookup fetches more than one, or it is split, and the tree is back to block sized nodes. The practical width is set by the storage block, not by an abstract desire for maximum branching.

The case weakens when the tree lives in memory rather than on disk. There is no four kilobyte fetch with the same price as one byte, though cache lines still make locality matter. A binary tree with poor locality can still lose to a wide tree, but the margin is smaller and the write costs of splitting and rebalancing a B-tree matter more. A B-tree also pays on every insert and delete to keep its nodes half full and balanced; if writes dominate and lookups are rare, that maintenance can outweigh the saved fetches. Range queries are the other side: the version databases usually use keeps all keys at the bottom and chains the bottom level sideways, so a range is read in sequence, while a binary tree must keep jumping between scattered nodes.

Worth keeping

A database index is charged in blocks fetched, not comparisons made.
A tree with 256 ways out of each node is about four fetches deep for a thousand million items, against about 30 for a binary tree.
Comparisons inside a fetched block are cheap beside the fetch, so a wider tree can do more comparing and less fetching and still win.

Where this goes next

This question is one step of Keeping Things in Order, a course that works through its subject from the beginning. The page that teaches this part of it is Wide Trees and the Disk, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course