Data structures · 9 of 111 / 3
B-trees
The conceptHow a database finds one row in a billion with about four disk reads
A B-tree is a balanced search tree whose nodes are disk pages of 4–16 KB, each holding hundreds of sorted keys and child pointers. With hundreds of children per node instead of two, the tree is wide and only a few levels deep.
To find key 4,217, the database reads the root page, binary-searches its keys for the gap where 4,217 fits, say 4,000–4,500, and follows that pointer down. It repeats until it reaches a leaf, the bottom page holding the key.
What it’s forEstimates how many levels, and so how many page reads, a B-tree needs to reach any key.
h ≈ log_m(N)
- h
- height: the number of levels, so the number of page reads per lookup
- m
- fan-out: children per node, often a few hundred
- N
- the number of keys stored
What it givesA height that grows very slowly: multiplying the data by m adds just one level.
- m = 100, N = 1,000,000
- 100 × 100 × 100 = 1,000,000, so h = 3 reads
- A binary tree needs log₂(1,000,000) ≈ 20 levels