Definition: A balanced search tree in which every node has between m/2 and m children, where m>1 is a fixed integer. m is the order. The root may have as few as 2 children. This is a good structure if much of the tree is in slow memory (disk), since the height, and hence the number of accesses, can be kept small, say one or two, by picking a large m.
Also known as balanced multiway tree.
Generalization (I am a kind of ...)
balanced tree, search tree.
Specialization (... is a kind of me.)
2-3-4 tree, B*-tree, 2-3 tree.
See also B+-tree, multiway tree, UB-tree for multidimensional indexing, external memory data structure.
The origin of "B-tree" has never been explained by the authors. ... "balanced," "broad," or "bushy" might apply. Others suggest that the "B" stands for Boeing. [Bayer and McCreight were at Boeing Scientific Research Labs in 1972.] Because of his contributions, however, it seems appropriate to think of B-trees as "Bayer"-trees. - Douglas Comer, The Ubiquitous B-Tree, Computing Surveys, 11(2):123, June 1979.
After [HS83, page 499].
A tutorial on the basics, and variants.
Rudolf Bayer and Edward M. McCreight, Organization and Maintenance of Large Ordered Indices, Acta Informatica, 1:173-189, 1972.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 16 November 2009.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "B-tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 16 November 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/btree.html