B-tree

In the 1980s B-trees were applied to database management systems, with an emphasis on how to ensure consistent B-tree access patterns to support concurrency control and data recovery. More recently, B-trees have been applied to disk management, to support efficient I/O and file versioning. For example, ZFS is built on top of an I/O efficient B-tree implementation.

The original B-tree algorithm was designed to support efficient access and maintenance of an index that is too large to hold in main memory. This led to three basic goals for a B-tree.

1. Increase the tree’s node size to minimize seeks, and maximize the amount of data transferred on each read.
2. Reduce search times to a very few seeks, even for large collections.
3. Support efficient local insertion, search, and deletion.

The key insight of B-trees is that the tree should be built bottom-up, and not top-down. We begin by inserting keys into a single leaf node. When this leaf node overflows, we split it into two half-full leaves and promote a single key upwards to form a new root node. Critically, since we defer the promotion until the leaf overflows, we can pick the key that does the best job of partitioning the leaf. This split–promote operation continues throughout the life of the B-tree.

Key Features

• Every tree node can hold up to k-1 keys and k subtree references.
• Every tree node except the root holds at least [k/2-1] (round to upper value) keys
• All leaf nodes occur at the same depth in the tree.
• The keys in a node are stored in ascending order.

Search

Using recursion to do the k-way search. The complexity is O (log_kn)

Insertion

Insertion in B-Tree is also a recursion process.

1. Search to find a leaf to store the new record.
2. Check if it is full, do the split and promote operation.
3. Check if parent node is full, do the split and promotion again and again.

Deletion

If the leaf is underfull after the deletion, we need to borrow one key from its sibilings and rebalance it.

If both siblings have only ⌈ k / 2 − 1 ⌉ keys, we coalesce the leaf with its left sibling and its parent’s split key.

1. Combine the left sibling’s keys, the split key, and the leaf’s keys. This produces a node with k − 1 keys.

2. Remove the parent’s split key and its now empty right subtree.

After coalescing, two checks must be made. First, if the parent node was the tree’s root and if it is now empty, we make the coalesced node the new root node. / Second, if the parent node is an internal node and if it now has fewer than ⌈ k / 2 − 1 ⌉ keys, it must be recursively rebalanced using the same borrow-coalesce strategy.

B* Tree

A B∗ tree is a B-tree with a modified insertion algorithm. B ∗ trees improve the storage utilization of internal nodes from approximately k / 2 to approximately 2k / 3 . This can postpone increasing the height of the tree, resulting in improved search performance.

B+ Tree

A B+ tree is a B-tree that holds all the data in the leaf nodes.

Reference

[1] Disk-Based Algorithms for Big Data By Christopher G. Healey