-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, Inc., Cupertino, CA) HFS filing
system uses -trees
to store disk directories (Benedict 1995). A -tree satisfies the following properties:

3. Each path from the root to a tree
leaf has the same length.

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, OEIS A014535). The
number of order-4 -trees
with , 2, ... leaves are 1, 1, 1, 2, 2,
4, 5, 9, 15, 28, 45, ... (OEIS A037026).