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: Named for Rudolf Bayer.

After [HS83, page 499].

Author: PEB

Implementation

tutorial of how B-trees work and code (Perl), another 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 E. Black.

Entry modified Fri Dec 17 12:23:21 2004.
HTML page formatted Wed Oct 26 09:47:17 2005.

Cite this as:
Paul E. Black, "B-tree", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.
http://www.nist.gov/dads/HTML/btree.html