B-Tree

What is a B-Tree?

A B-Tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. B-Trees are optimized for systems that read and write large blocks of data, making them ideal for databases and filesystems where accessing disk blocks is slow compared to memory access.

Key Properties:

• Order / Minimum Degree (t): Each B-Tree has a minimum degree `t`. This defines the node size limits:
  • Max Keys per node: 2t - 1
  • Max Children per node: 2t
  • Min Keys per node (except root): t - 1
  • Min Children per node (except root): t
  (This visualization uses Max Keys `m = 2t - 1` as input for simplicity).
• Balanced: All leaf nodes are at the same depth (height).
• Sorted Keys: Keys within each node are stored in sorted order.
• Child Ranges: An internal node with `k` keys has `k+1` children. The keys act as separation values between the subtrees pointed to by the children (e.g., keys in child `i` are less than `key[i]`, keys in child `i+1` are greater than `key[i]`).

Insertion Algorithm

1. Find Leaf: Start at the root and traverse down the tree, following the appropriate child pointers (based on comparing the new key with keys in the current node) until a leaf node is reached where the key should belong.
2. Insert in Leaf: Insert the new key into the leaf node, maintaining sorted order.
3. Handle Overflow (Splitting):
   • If inserting the key causes the leaf node to exceed its maximum key limit (`2t - 1` keys):
     1. Split the overflowing node into two separate nodes at its median key.
     2. The left node gets keys less than the median, the right node gets keys greater than the median.
     3. Promote the median key up to the parent node.
     4. The parent node inserts the promoted key and adds a pointer to the newly created right node.
   • If inserting the promoted key into the parent node causes *it* to overflow, repeat the split process recursively up the tree.
   • Root Split: If the split propagates all the way up to the root node and the root overflows, split the root, promote its median key into a new root node, and make the two split halves the children of the new root. This is how the tree height increases.

This splitting mechanism ensures the tree remains balanced.

Search Algorithm

1. Start at the root node.
2. Within the current node, find the smallest key `k` greater than or equal to the search key.
3. If the search key equals `k`, the key is found. Done.
4. If the current node is a leaf and the key wasn't found, the key is not in the tree. Done.
5. If the current node is internal, follow the child pointer *before* key `k` (or the last pointer if the search key is greater than all keys in the node).
6. Repeat steps 2-5 with the child node as the current node.