B+ Tree Operations: Insertion and Deletion

Introduction

In our last lesson, we established why the B+ Tree is the go-to index structure for disk-based databases. We learned that its short, wide structure, high fanout, and linked-list leaf nodes are all designed to minimize costly disk I/O, especially when compared to a traditional binary search tree.

A key property we discussed is that a B+ Tree is always balanced. This means the path from the root to any leaf is the same length. Additionally, every node (except possibly the root) must be at least half-full. Today's learning outcome is to implement insertion and deletion operations in a B+ tree, handling node splits and merges. We will explore the algorithms that ensure these critical properties are maintained as the tree grows and shrinks. This lesson is all about the dynamic nature of the B+ tree.

1. B+ Tree Insertion

The insertion algorithm always starts the same way: traverse the tree from the root to find the appropriate leaf node where the new key should be placed. Once you've found the target leaf, there are two possibilities.

The Simple Case: Space is Available

If the leaf node is not full (i.e., it contains fewer than max_size - 1 keys), the process is simple:

1. Insert the new key-value pair into the leaf node.
2. Keep the keys in the leaf node sorted.
3. You're done! No other nodes in the tree are affected.

The Complex Case: Node Splitting

The more interesting case occurs when the target leaf node is already full. You cannot simply add another key, as this would violate the node's size constraint. This is where node splitting comes in.

The core idea is to split the full node into two, distributing the keys between them, and then updating the parent to reflect this change. This process can propagate up the tree.

Let's watch a detailed walkthrough of the insertion algorithm, focusing on how splits are handled.

To solidify this concept, here is a summary of the algorithm when a node (let's call it N) overflows:

1. Create a new node, N'.
2. Distribute keys: Take all the keys that were in N, plus the new key you're trying to insert. Move the second half of these sorted keys into the new node N'. N now contains the first half.
3. Promote the middle key: Take the first key from N' (which was the middle key of the combined set) and insert it into the parent node. This key now serves as the separator, with a pointer to N'.
4. Handle the parent recursively: If the parent node is now full after receiving the promoted key, repeat the split process on the parent. This can continue all the way to the root. If the root itself splits, you create a new root, and the tree's height increases by one.

This image provides a static, step-by-step view of an insertion that causes a leaf, and subsequently the root, to split.

2. B+ Tree Deletion

Deletion is the reverse process of insertion. It starts by finding the key in the correct leaf node and removing it. The complexity arises when this removal causes the node to become less than half-full, violating one of the B+ Tree's core invariants.

The Simple Case: Node Remains Half-Full

If you delete a key from a leaf node and the node still has at least ceil(max_size / 2) entries, you are done. The B+ tree properties are maintained.

The Complex Case: Node Underflow

If deleting the key causes the node to underflow, you must rebalance the tree. You have two options, which should be attempted in this order:

1. Redistribution (Borrowing): Look at an immediate sibling (a node next to it with the same parent). If the sibling has more than the minimum number of keys, you can "borrow" a key from it. The key moves from the sibling, through the parent, into your under-full node. The separator key in the parent must be updated to reflect the new boundary. This is generally preferred as it is a less disruptive local operation.

2. Merging: If the sibling is also at the minimum fill level and cannot spare a key, you must merge your under-full node with the sibling. This involves combining all keys from both nodes into a single node and deleting the separator key from the parent that used to sit between them.

This merge operation might cause the parent node to underflow, in which case the rebalancing logic is applied recursively up the tree. If the root's last two children are merged, the root itself is removed, and the tree's height decreases by one.

Let's watch the deletion process in detail.

This image shows a static example of deletion followed by redistribution.

3. An Implementation Perspective

You have an applied/engineering goal, so let's connect this theory to practice. In a real C++ implementation, like the one in CMU's Bustub project, you would model these concepts with specific classes.

The key takeaway is that the abstract algorithms for Insert and Remove are translated into concrete methods on Page objects. Your code would fetch a page from the buffer pool, cast it to the correct type (Leaf or Internal), and then call methods like Insert, Split, Merge, etc., on that page object.

4. Handling Duplicate Keys

One final practical consideration is how to handle duplicate keys, as non-unique indexes are very common. If you simply try to insert the same key multiple times, your B+ Tree's logic might fail. There are two common solutions:

1. Append Record ID: The most common approach is to make every key unique by appending the record's unique identifier (e.g., its RID, composed of page ID and slot number). So, if you insert key 100, the actual entry in the tree might be (100, <RID_1>), (100, <RID_2>), etc. Since each RID is unique, the composite key is always unique.
2. Overflow Pages: An alternative is to allow duplicate keys in a leaf node and, if there are too many to fit, create special "overflow" pages that are linked from the main leaf node. This essentially creates a linked list of records for a given key. This approach is less common because it complicates the tree logic and can degrade performance if these chains become long.

For most systems, the first approach (appending a unique ID) is preferred because it keeps the core B+ Tree logic unchanged and guarantees logarithmic performance.

Conclusion

Today, we went deep into the dynamic operations that keep a B+ Tree balanced and efficient. While the logic for splits and merges can be intricate to implement, the underlying algorithms are systematic and designed to preserve the tree's crucial invariants at all times.

Key Takeaways:

• Insertion: When a node is full, it splits into two. The middle key is promoted to the parent to act as a separator. This can propagate up to the root, increasing the tree's height.
• Deletion: When a node becomes less than half-full, it must be rebalanced by either redistributing (borrowing) a key from a full-enough sibling or merging with a sibling if it's also at minimum capacity.
• Recursive Nature: Both splits and merges can propagate up the tree, ensuring that the half-full and balance properties are maintained at every level.
• Implementation: These algorithms translate into methods on InternalPage and LeafPage objects, which are fetched from and written back to the buffer pool.

Preview of the Next Lesson:

Now that we have a fully functional, dynamic B+ Tree, we can finally put it to use! In our next lesson, we will focus on performing point and range queries using the index. We will analyze the I/O cost of these operations and see exactly how the B+ Tree provides rapid data access.