B-tree

(data structure)

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.

Note:

	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].

Author: PEB

Implementation

tutorial of how B-trees work and code (Perl), Bro. David Carlson's tutorial and code (C++). data structure definition (C and Pascal), insert (C and Pascal) using auxiliary functions (C and Pascal), search (C and Pascal), (Pick Basic?).

More information

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.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 16 November 2009.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "B-tree", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 16 November 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/btree.html