B+ tree

From Wikipedia, the free encyclopedia

A simple B+ tree example linking the keys 1-7 to data values d₁-d₇. Note the linked list (red) allowing rapid in-order traversal.

In computer science, a B+ tree is a type of tree data structure. It represents sorted data in a way that allows for efficient insertion and removal of elements. It is a dynamic, multilevel index with maximum and minimum bounds on the number of keys in each node. The NTFS filesystem for Microsoft Windows, ReiserFS filesystem for Linux and XFS filesystem for IRIX use this type of tree.

A B+ tree is a variation on a B-tree. In a B+ tree, in contrast to a B-tree, all data is 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 pointers 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+1, each node (except for the root) must have between (n+1)/2 and n keys. If n is an odd number, the minimum number of keys can be either (n + 1)/2 or (n - 1)/2, but it must be the same in the whole tree.

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 nodes is $n h$
minimum number of keys is $2(n / 2) h - 1 .$

The B+ tree was first described in the paper "Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Informatica 1: 173-189 (1972)".

An extension of a B+ tree is called a B# Trees which use the B+ Tree Structure and adds further restrictions.