A B+ tree is a dynamic, multilevel index with maximum and minimum bounds on the number of keys in each node.

B+ tree is a variety of B tree. But, unlike B tree, all data are saved in the leaves. Internal nodes contain only keys and tree pointers. All leaves are at the same lowest level. Leaf nodes are also linked together as a linked list to make range queries easy.

The maximum number of keys in a record is called the order of the B+ tree.

The minimum number of keys per record is 1/2 of the maximum number of keys. For example, if the order of a B+ tree is n, each node (except for the root) must have between n/2 and n keys.

The number of keys that may be indexed using a B+ tree is a function of the order of the tree and its height.

For a n-order B+ tree with a height of h:

• maximum number of keys is n^h
• minimum number of keys is 2(n / 2)^{(h - 1)}.

External links

• http://www.seanster.com/BplusTree/BplusTree.html