Information on B-Trees

• 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.

• C program    
• Pascal program    

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.
There have been 6398 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.