TAOCP Vol 3: Sorting and Searching · Week 89
TAOCP 5.4.9 Disks and Drums: reading guide
External sorting on random-access devices like disks: how seek time, rotational delay and block sizes change the best strategy compared with tapes.
Time About 5 hours this week
Why it matters
Much more relevant than the tape sections: disk-based thinking (minimize seeks, read large sequential blocks) still matters for databases, even on SSDs.
Before you start
- 5.4.1 Multiway Merging
- 5.4.6 Practical Considerations
How to approach it
Read with modern storage in mind. Ask at each point: what changes for an SSD? What stays the same?
Exercises
This is a light section. Skim the exercises, do the ones rated 10 or under in your head, and spend the spare time catching up on earlier exercises you skipped.
Traps
- Taking 1970s timing numbers literally.