B-trees and B+ trees

The balanced tree reimagined for disk. Wide nodes → few levels → few disk reads.

On disk, cost = blocks read

• Each node = one disk block, packed with hundreds of keys
• Fan-out m → height log_m n, not log₂ n
• Order-128 tree over 1M keys: 3 levels, not 20
• Same O(log n) — but log base 128, not base 2

Watch nodes fill and split

Keys accumulate; overflow → split, median rises. Root split → tree grows. All leaves stay at the same depth.

Fan-out crushes the height

500000 keys: 3 levels vs 19 → ~6× fewer disk reads. At ms/seek, that's the whole ballgame.

B+ trees (what databases use)

• Data only in leaves; internal nodes are just guide keys → shorter still
• Leaves chained → range scans walk the leaf list sequentially
• Every SQL index, every filesystem

Takeaway

Match the structure to the memory hierarchy it runs on. In memory? Use a red-black tree. On disk? B-tree. Next: Union-Find.