## Information on B-Trees

A *B-tree* of order *m* is an ordered tree which satisfies
the following
properties:

- Every node has at most
*m* children.

- Every node, except the root, has at least
*m/2* children.

- The root has at least 2 children.
- All leaves occur on the same level.

B-trees were introduced by Bayer and McCreight in 1972
(they did not explain their choice of name).
They are balanced search trees designed to work well on magnetic disks
or other direct-access secondary storage devices.
B-trees are similar to red-black
trees in that every *n*-node B-tree has height O(lg *n*),
although the height of a B-tree can be considerably less than that
of a red-black tree because its branching factor
can be much larger.
Therefore, B-trees can also be used to implement many dynamic-set operations
in time O(lg *n*).

The standard representation adopted here is a sequence of number of children
of each internal node, where the nodes are traversed bottom-up level-by-level
and from right-to-left within a level.
See the following figure for an example:

This is a B-tree of order 4 and has the encoding
3 2 2 2 3 2 4 2 3 2 3 .

For B-tree of order 3 with *n* = 1,2,..,17 leaves,
the number of trees are: 0, 1, 1, 1, 2, 2, 3, 4, 5, 8, 14, 23, 32, 43,
63, 97, 149.
This is sequence
**A014535**(M0564) in
Neil J. Sloane's
database
of integer sequences.

The algorithm used is based on one by
Pierre Kelsen and is presented in the book *Combinatorial Generation*.

Programs available:
IMPORTANT NOTE: These programs only generate the sequence of encodings
of B-trees.
They do not implement any of the data structure operations on B-trees!

**Questions??** Email
The wizard of COS.

(Please note that the suffix XXXX must be removed from the preceeding
email address.)

It was last updated Tuesday, 24-May-2011 10:55:35 PDT.

[Error Opening Counter File -- Click for more info]

©Frank Ruskey, 1995-2003.