Week 95 of 125
TAOCP 6.2.4 Multiway Trees
Sign up or sign in to tick these off and give this week a due date.
-
B-trees and their variants: nodes with many keys sized to a disk page, insertion by splitting, and analysis of their height and space usage.
Time About 8 hours this week
Why it matters
B-trees are the index structure inside nearly every database and filesystem (SQLite, Postgres, NTFS, APFS).
Before you start
- 6.2.3 Balanced Trees
- 5.4.9 Disks and Drums
How to approach it
Implement an in-memory B-tree with insertion and search. Then read how SQLite lays out its B-tree pages to connect it to the real world.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Off-by-one on the minimum and maximum keys per node when splitting.