PFun / B+ Tree

What's a B+ Tree?

A B+ tree is an n-ary tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more children.

Similarity to B-Tree

A B+ tree can be viewed as a B-tree in which each node contains only keys (not key-value pairs), and to which an additional level is added at the bottom with linked leaves.

Compatibility

The NTFS, ReiserFS, NSS, XFS, JFS, and ReFS filesystems all use this type of tree for metadata indexing. Relational database management systems such as IBM DB2, Informix, Microsoft SQL Server, Oracle 8, Sybase ASE, and SQLite support this type of tree for table indices. Key-value database management systems such as CouchDB and Tokyo Cabinet support this type of tree for data access.

Algorithms

Search

The root of a B+ Tree represents the whole range of values in the tree, where every internal node is a subinterval.

We are looking for a value k in the B+ Tree. Starting from the root, we are looking for the leaf which may contain the value k. At each node, we figure out which internal pointer we should follow. An internal B+ Tree node has at most d ≤ b children, where every one of them represents a different sub-interval. We select the corresponding node by searching on the key values of the node.

Insertion

Perform a search to determine what bucket the new record should go into.

• If the bucket is not full (at most b - 1 entries after the insertion), add the record.
• Otherwise, split the bucket.
• Allocate new leaf and move half the bucket's elements to the new bucket.
• Insert the new leaf's smallest key and address into the parent.
• If the parent is full, split it too.
• Add the middle key to the parent node.
• Repeat until a parent is found that need not split.
• If the root splits, create a new root which has one key and two pointers. (That is, the value that gets pushed to the new root gets removed from the original node)

B-trees grow at the root and not at the leaves.

Deletion

• Start at root, find leaf L where entry belongs.
• Remove the entry.
• If L is at least half-full, done!
• If L has fewer entries than it should,
• Try to re-distribute, borrowing from sibling (adjacent node with same parent as L).
• If re-distribution fails, merge L and sibling.
• If merge occurred, must delete entry (pointing to L or sibling) from parent of L.
• Merge could propagate to root, decreasing height.

Source: Wikipedia