A self-balancing tree that lets each node hold many children and many keys rather than just two, minimizing the number of disk or page reads needed to find a record; the standard structure behind most database indexes and file systems.
Facts
Origin YearRudolf Bayer and Edward McCreight invented the B-tree at Boeing Research Labs to manage index pages for large random-access files. Core PrincipleA self-balancing tree that generalizes the binary search tree by allowing nodes to have more than two children, keeping data sorted and search, insertion and deletion in logarithmic time while reducing tree height for data stored in large blocks such as disk pages. 1 Connections
In Field
Invented
Rudolf Bayer co-invented the B-tree with Edward McCreight while at Boeing Research Labs, described in their 1972 paper.
Sources
1. Wikipedia: B-tree
Wikimedia FoundationHistory section, first paragraph
Bayer and McCreight's paper Organization and maintenance of large ordered indices was first circulated in July 1970 and later published in Acta Informatica.
Lead section, first paragraph
The B-tree generalizes the binary search tree, allowing nodes to have more than two children.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.