# 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 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