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 O(lgn), where lg is the logarithm to base 2. The Apple® Macintosh® (Apple, Inc., 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 tree leaf or has at least two children.

2. Each node (except the root and tree leaves) has between [m/2] and m children, where [x] is the ceiling function.

3. Each path from the root to a tree leaf 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, OEIS A014535). The number of order-4 B-trees with n=1, 2, ... leaves are 1, 1, 1, 2, 2, 4, 5, 9, 15, 28, 45, ... (OEIS A037026).

See also

Red-Black Tree, Tree

Explore with Wolfram|Alpha


Aho, A. V.; Hopcroft, J. E.; and Ullmann, J. D. Data Structures and Algorithms. Reading, MA: Addison-Wesley, pp. 369-374, 1987.Bayer, R. and McCreight, E. "Organization and Maintenance of Large Ordered Indexes." Acta Informatica 1, 173-189, 1972.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.Knuth, D. E. "B-Trees." The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. Reading, MA: Addison-Wesley, pp. 482-485 and 490-491, 1998.Ruskey, F. "Information on B-Trees.", S. S. The Algorithm Design Manual. New York: Springer-Verlag, p. 178, 1997.Sloane, N. J. A. Sequences A014535 and A037026 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha


Cite this as:

Weisstein, Eric W. "B-Tree." From MathWorld--A Wolfram Web Resource.

Subject classifications