-trees were introduced by Bayer (1972) and McCreight. They are a special -ary balanced tree used in databases because their structure allows records to be inserted, deleted, and retrieved with guaranteed worst-case performance. An -node -tree has height , where Lg is the Logarithm to base 2. The Apple Macintosh (Apple Computer, Cupertino, CA) HFS filing system uses -trees to store disk directories (Benedict 1995). A -tree satisfies the following properties:
Every 2-3 Tree is a -tree of order 3. The number of -trees of order 3 with , 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 -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.