Chapter 7 · Space and Time Trade-Offs
B-Tree Lab
A B-tree packs many keys into each node so the tree stays very short. On a disk, every node you visit is one page read, so height is the cost that matters. Insert keys, watch full nodes split, and see the tree grow at the root.
key being inserted / searched
node read from disk
key compared
overflowing node
key sent up to the parent
found / placed
Height as keys arrive
height h of your tree
upper bound ⌊log⌈m/2⌉((n+1)/4)⌋ + 1
Disk accesses at real scale
Real B-trees use orders in the hundreds, because one node is sized to one disk page. Pick a file size and an order to see the worst-case height (Levitin inequality 7.7) and the page reads it implies, next to a perfectly balanced binary tree.
How to read this
- Order m
- A node may have at most m children. Every node except the root must have at least ⌈m/2⌉ children, and all leaves sit on the same level. Order 3 is exactly a 2-3 tree.
- Two variants
- Levitin's version keeps every record in the leaves (at most m − 1 per leaf here); the upper nodes only hold signposts: each separator equals the smallest key in the subtree to its right. When a leaf splits, the separator is copied up. When an internal node splits, its middle key moves up. The classic B-tree stores each key exactly once, in any node, and always moves the middle key up.
- Disk reads
- Every blue node on a search path is one page read. A search reads h + 1 nodes. The row labels on the left of the tree count them.
- Growth at the top
- The only way the tree gets taller is a split of the root, which creates a new root one level up. That is why the leaves always stay level.
Try this
- Lesson trace. Build the default keys with m = 4 (Levitin variant). After 35 the root splits: the new root holds 31, its children hold 15, 23 and 42, and the leaves are (4, 8) (15, 16) (23, 27) (31, 35) (42, 50). Search 27: three disk reads.
- Order vs height. Press “Ascending 1..20” with m = 3, then m = 6. Height drops from 3 (m = 3) to 2 (m = 4) to 1 (m = 6). Bigger nodes mean fewer levels.
- Copy vs move. Switch to the classic variant and rebuild the default keys. Count the keys in the whole tree: every key appears once. In the Levitin variant, separators are duplicates of leaf keys.
- Predict splits. Before each insertion, answer the prompt: will this key cause a split? A split happens exactly when the target leaf is already full.
- Scale. In the disk panel set N = 10^8 and try m = 50, 100, 250. The height bound is 6, 5 and 4 (at most 7, 6 and 5 page reads, and in practice the top levels sit in memory), while a perfectly balanced binary tree has 27 levels.