Why a library doesn't shelve one book per floor

A library shelf holds more than one book

Imagine a library that insisted on one book per floor, sorted, so finding a book meant walking up one floor at a time comparing titles. No library works that way — each shelf holds dozens of books in sorted order, and you scan a few titles once you reach the right shelf. Fewer floors to climb, more books per stop.

A binary search tree is the one-book-per-floor library. Every node holds exactly one key and forces a single comparison before moving on — fine when a node lives in fast memory, expensive when a node lives on a slow disk, because Lesson 4 of Unit II measured cost in comparisons, and this lesson measures it in disk reads instead.

One disk read, many comparisons

Reading anything from a disk — even a fast one — costs vastly more time than comparing two numbers already sitting in memory. A tree stored on disk therefore wants to minimize the number of nodes visited, even if each visit does more work once the data has arrived. A node that holds one hundred sorted keys costs one disk read and about seven comparisons within memory to search — still far cheaper than one hundred separate disk reads.

A multi-way search tree generalizes Lesson 4's rule: instead of one key splitting a node into two children, m - 1 sorted keys split a node into m children, called the order of the tree. Search within a node scans its handful of keys to find which of the m gaps the target falls into, then makes one more disk read to follow that child.

/* A tiny 3-key node splits into 4 children */

   [ 20 | 45 | 70 ]
   /     |    |    \
 <20   20-45 45-70  >70

Fewer floors to climb

A binary tree of a million keys needs about twenty levels. A tree of the same million keys with a hundred keys per node needs only about three levels — three disk reads to find anything, instead of twenty. That is the entire motivation for the rest of this unit: pack more into each stop, and the number of stops collapses.