Rudolf Bayer, Edward McCreight, and the B-Tree: Indexing Data at Disk Scale
Rudolf Bayer and Edward McCreight designed the B-tree to keep large ordered indexes balanced on page-oriented storage, making logarithmic search and dynamic updates practical on disks.
Disk storage changed what a search tree needed to optimize
A binary search tree is elegant when node access is cheap, but secondary storage changes the cost model. Reading a disk page is far more expensive than comparing keys already in memory, so an index structure should do more useful work per I/O.
Bayer and McCreight’s original work considered dynamic ordered indexes kept on devices such as disks or drums and organized keys into page-sized nodes rather than one-key nodes.[1]
The B-tree made every node wide
A B-tree node can hold many keys and many child pointers. High fan-out reduces the number of levels needed to index a large collection, which in turn reduces the number of page reads needed to reach a key.[1]
The structure was designed around the physical reality of block storage while still presenting a clean ordered-search abstraction.
High fan-out turned height into an I/O advantage
If each page can direct the search toward dozens or hundreds of children, enormous indexes can remain only a few levels deep. The tree’s branching factor is therefore part of its storage-engine performance.
Balance kept worst-case access predictable
B-trees maintain all leaves at the same depth. Insertions and deletions may split, merge or redistribute pages so that the tree remains balanced instead of degrading into a long chain.[1]
This gives search, insertion and deletion logarithmic behavior in the size of the index while keeping storage utilization bounded.
Updates repair structure locally
The tree does not require periodic global rebuilding after each change. Structural adjustments occur around the affected path, which made the design well suited to continuously updated files.
The name came from a deliberately ambiguous B
Edward McCreight later recalled that the name was chosen to be short and memorable. He associated the B with several possibilities, including Boeing, Balance and Bayer, and explicitly resisted claiming a single official expansion.[3]
That recollection is a useful historical caution: popular explanations often retrofit a single meaning onto a name whose creators remembered more playfully.
The invention grew from Boeing research
The original technical report was produced at Boeing Scientific Research Laboratories, where Bayer and McCreight were working when they developed the structure.[1]
The database community quickly absorbed the structure
ACM SIGMOD’s 2001 award citation credits Rudolf Bayer, with Edward McCreight, for inventing the B-tree and notes its extensive use in commercial database products.[2]
The design fit database workloads unusually well because databases need ordered lookup, range scans and continuous updates over data sets much larger than memory.
Modern B-tree indexes still expose the original page-oriented idea
PostgreSQL describes its standard B-tree index as a multi-way balanced tree whose pages are internal or leaf pages, with page splits occurring when an incoming tuple no longer fits.[4]
SQLite likewise organizes both table and index storage around B-tree pages with interior and leaf structures, showing how deeply page-oriented trees remain embedded in database file formats.[5]
An old structure survives because the storage problem survives
Storage devices have changed from drums and spinning disks to SSDs and persistent cloud volumes, but systems still benefit from locality, bounded depth and ordered traversal.
B-trees support more than exact lookup
Because keys are ordered, B-tree indexes naturally support range conditions, ordered scans and predecessor or successor navigation in addition to equality search. PostgreSQL’s documentation notes that B-tree indexes are candidates for equality and ordered comparisons on sortable data.[4]
This combination of dynamic updates and order awareness distinguishes them from simpler hash indexes that target exact-key access.
Why the B-tree belongs in coding history
Bayer and McCreight solved a systems problem by designing a data structure around the real unit of expensive access: the storage page. Their result connected algorithmic balance with device economics.[1][2]
The B-tree’s longevity is a lesson in abstraction. A structure can outlive generations of hardware when it captures a durable relationship between logical operations and physical costs.
Works Cited
- 01
- 02
- 03
- 04PostgreSQL Documentation — B-Tree Indexes postgresql.org
- 05
CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.
Submit a research lead