Organization and Maintenance of Large Ordered…

The original B-tree paper asks how an index can keep searches and updates cheap when it is too large for memory and every disk access is expensive. Read it to see why one page should hold many sorted separators, how a full page splits around its median, and how equal leaf depth keeps a changing index shallow.

Reading focus: Why matching one tree node to one disk-transfer page turns many in-page comparisons into a single expensive storage access. How sorted separators route a search and how promoting the median of a full page creates two siblings without breaking order or balance. Which occupancy, height, device-cost, workload, concurrency, and recovery limits separate the 1972 result from a complete modern database index.

Acta Informatica 1972. Rudolf Bayer and Edward M. McCreight. 30 min read, easy difficulty.