The encyclopedia · Engineering & Operations · Technical decision · 1970–1972
B-trees made a database index fit a disk instead of RAM
In 1972 Bayer and McCreight widened each tree node to a whole disk block, so lookups need almost no seeks.
Boeing Scientific Research Laboratories
the move
Any large ordered index will be too big to fit in main memory, so parts of it live on disk, and a disk seek is far more expensive than any computation. A binary search tree, the natural choice, is tall, so finding one key means descending a level per seek, which is ruinous at scale.
Bayer and McCreight's B-tree flips that. A node is sized to a whole disk block and holds many keys and many children, so descend once and you make progress through a large range. All leaves sit at the same depth and nodes are kept between a minimum and maximum fill, so the tree stays balanced with only occasional splits.
The effect is that a lookup touches a small, nearly constant number of blocks no matter how large the index grows. That is exactly what makes a database or file system usable once its index outgrows memory.
why it works
- Sizing each node to a disk block means one seek retrieves many keys at once.
- Keeping the tree shallow and all leaves at the same depth avoids the many-seek cost of a tall binary tree.
- Allowing a range of children per node means the tree needs rebalancing far less often.
what transfers
When the expensive resource is access, not computation, redesign the structure around it: make one wide node per disk block so a single seek buys a lot of work and the cost per lookup stays small.
what came after
The B-tree became the canonical index structure for databases and file systems, used by almost every relational database and by file systems and key-value stores, and its balance and block-sized nodes remain why lookups on gigabytes of data still take only a handful of disk reads.
references
spotted an error? The archive wants to know.