B+ Tree

B+ Tree #

B plus tree basic concept and operations.

Introduction #

A B+-Tree(“bee plus tree”) is a self balanced tree data structure that keeps data sorted and allows searches, sequential access, insertion, and deletions in O(log(n)). It is optimized for disk-oriented DBMSs that read/write large blocks of data.

Almost every modern DBMS that supports order-preserving indexes uses a B+-Tree. There is a specific data structure called a B-Tree, but people also use the term to generally refer to a class of data structures. Modern B+-Tree implementations combine features from other B-Tree variants, such as the sibling pointers used in the Blink-Tree.

Formally, a B+-Tree is an M-way search tree with the following properties:

  1. Every inner node other than the root is at least half full, i.e.,
    • ⎡M/2⎤ <= num of children <= M
    • ⎡M/2⎤ − 1 <= num of keys <= M − 1
  2. Every leaf node is at the same depth(i.e., It is perfectly balanced)
  3. Every inner node with k keys has k+1 non-null children.
  4. Root node can have minimum 2 children(i.e, at least one key).

Every node in a B+-Tree contains an array of key/value pairs:

  1. Arrays at every node are (almost) sorted by the keys.
  2. The value array for inner nodes will contain pointers to other nodes.
  3. Two approaches for leaf node values
    1. Record IDs: A pointer to the location of the tuple
    2. Tuple Data: The actual contents of the tuple is stored in the leaf node

B-Tree FAMILY #

There is a specific data structure called a B-Tree, people also use the term to generally refer to a class of balanced tree data structures:

  • B-Tree(1971)
  • B+-Tree(1973)
  • B*-Tree(1977?)
  • Blink-Tree (1981)

Implementation #

https://github.com/maxnilz/tree/tree/main/bplustree

Visualization #

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

Degree & Order #

Degree represents the Lower bound on the number of children a node in the B Tree can have (except for the root). i.e the minimum number of children possible. Whereas the Order represents the Upper bound on the number of children. ie. the maximum number possible.

Assume the Order of a B tree is U and Degree is L, then L = ⎡U/2⎤.

More specifically, the ceil can be interpreted as, If U-1(max number of keys) is odd, then U is even and U=2L, otherwise U is odd and U=2L-1.

Insertion #

All insertions start at a leaf node. To insert a new element, search the tree to find the leaf node where the new element should be added. Insert the new element into that node with the following steps:

  1. Perform a search to determine what bucket the new record should go into.
  2. If the bucket is not full (at most U-1 entries after the insertion), add the record.
  3. Otherwise, before inserting the new record
    • split the bucket.
      • original node has ⎡(U+1)/2⎤ items
      • new node has ⎣(U+1)/2⎦ items
    • Copy ⎡(U+1)/2⎤-th key to the parent, and insert the new node to the parent.
    • Repeat until a parent is found that need not split.
    • Insert the new record into the new node.
  4. If the root splits, treat it as if it has an empty parent and split as outline above.

Bulk-loading #

Given a collection of data records, we want to create a B+-Tree index on some key field. One approach is to insert each record into an empty tree. However, it is quite expensive, because each entry requires us to start from the root and go down to the appropriate leaf page. An efficient alternative is to use bulk-loading.

  1. The first step is to sort the data entries according to a search key in ascending order.
  2. We allocate an empty page to serve as the root, and insert a pointer to the first page of entries into it.
  3. When the root is full, we split the root, and create a new root page.
  4. Keep inserting entries to the right most index page just above the leaf level, until all entries are indexed.

Note :

  • when the right-most index page above the leaf level fills up, it is split;
  • this action may, in turn, cause a split of the right-most index page one step closer to the root;
  • splits only occur on the right-most path from the root to the leaf level.

Deletion #

The purpose of the delete algorithm is to remove the desired entry node from the tree structure. We recursively call the delete algorithm on the appropriate node until no node is found. For each function call, we traverse along, using the index to navigate until we find the node, remove it, and then work back up to the root.

At entry L that we wish to remove:

  • If L is at least half-full, done
  • If L has only L = ⎡U/2⎤ entries, try to re-distribute, borrowing from sibling (adjacent node with same parent as L). After the re-distribution of two sibling nodes happens, the parent node must be updated to reflect this change. The index key that points to the second sibling must take the smallest value of that node to be the index key.
  • If re-distribute fails, merge L and sibling. After merging, the parent node is updated by deleting the index key that point to the deleted entry. In other words, if merge occurred, must delete entry (pointing to L or sibling) from parent of L.

Note: merge could propagate to root, which means decreasing height.

We are looking for a value k in the B+-Tree. This means that starting from the root, we are looking for the leaf which may contain the value k. At each node, we figure out which internal node we should follow. An internal B+-Tree node has at most m ≤ b children, where every one of them represents a different sub-interval. We select the corresponding child via a linear search of the m entries, then when we finally get to a leaf, we do a linear search of its n elements for the desired key. Because we only traverse one branch of all the children at each rung of the tree, we achieve O(log N) runtime, where N is the total number of keys stored in the leaves of the B+-Tree.

Reference #