B-Tree

$B$-trees were introduced by Bayer (1972) and McCreight. They are a special $m$-ary balanced tree used in databases because their structure allows records to be inserted, deleted, and retrieved with guaranteed worst-case performance. An $n$-node $B$-tree has height ${\mathcal O}(\lg 2)$, where Lg is the Logarithm to base 2. The Apple ${}^{\scriptstyle\circledRsymbol}$ Macintosh ${}^{\scriptstyle\circledRsymbol}$ (Apple Computer, Cupertino, CA) HFS filing system uses $B$-trees to store disk directories (Benedict 1995). A $B$-tree satisfies the following properties:

1. The Root is either a Leaf (Tree) or has at least two Children.

2. Each node (except the Root and Leaves) has between $\left\lceil{m/2}\right\rceil$ and $m$ Children, where $\left\lceil{x}\right\rceil$ is the Ceiling Function.

3. Each path from the Root to a Leaf (Tree) has the same length.

Every 2-3 Tree is a $B$-tree of order 3. The number of $B$-trees of order 3 with $n=1$, 2, ... leaves are 1, 1, 1, 1, 2, 2, 3, 4, 5, 8, 14, 23, 32, 43, 63, ... (Ruskey, Sloane's A014535).

See also Red-Black Tree

References

Aho, A. V.; Hopcroft, J. E.; and Ullmann, J. D. Data Structures and Algorithms. Reading, MA: Addison-Wesley, pp. 369-374, 1987.

Benedict, B. Using Norton Utilities for the Macintosh. Indianapolis, IN: Que, pp. B-17-B-33, 1995.

Beyer, R. ``Symmetric Binary $B$-Trees: Data Structures and Maintenance Algorithms.'' Acta Informat. 1, 290-306, 1972.

Ruskey, F. ``Information on B-Trees.'' http://sue.csc.uvic.ca/~cos/inf/tree/BTrees.html.

Sloane, N. J. A. Sequence A014535 in ``The On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.