Deletion from a B+ Tree

---

A B+ Tree is an efficient self-balancing data structure widely used in databases and file systems to manage large datasets. It extends the B-tree and stores all actual data in the leaf nodes, while the internal nodes only store keys used for navigation.

Deletion in a B+ Tree is more involved than insertion because it requires ensuring that the tree remains balanced after removing a key. This involves potentially redistributing or merging nodes if they underflow (i.e., have fewer keys than the minimum required). The deletion process also involves updating parent nodes to ensure that the tree structure remains valid.

---

What is a B+ Tree?

Before diving into the deletion process, let’s quickly review the basic structure of a B+ Tree:

• Internal Nodes: Contain only keys for navigation.
• Leaf Nodes: Store actual data and are connected in a doubly linked list for efficient sequential access.
• Balanced Structure: All leaf nodes are at the same level, ensuring that searching, insertion, and deletion operations remain efficient.
• Order of the Tree: The minimum degree (t) defines the maximum number of children a node can have. Internal nodes can store up to 2*t - 1 keys, and leaf nodes can hold 2*t - 1 keys.

---

Deletion Process in a B+ Tree

Steps for Deletion in a B+ Tree

1. Search for the Key:
   • Start from the root and navigate down to find the leaf node containing the key to be deleted.
2. Delete the Key:
   • Once the key is found in the leaf node, remove it from the node.
3. Check Node Underflow:
   • After deletion, if the number of keys in the node is less than the minimum allowed (i.e., fewer than t-1 keys), the node is underfull.
4. Fix Underflow by Borrowing or Merging:
   • If a node is underfull, there are two ways to fix it:
     • Borrowing: Borrow a key from a neighboring sibling (left or right) if they have more than the minimum required number of keys.
     • Merging: If borrowing is not possible, merge the underfull node with a sibling and move a key down from the parent node to maintain balance.
5. Repeat the Process:
   • If the parent node becomes underfull after a deletion or merge, repeat the borrowing or merging process recursively until the tree is balanced.
6. Update the Root:
   • If the root node becomes underfull after a deletion, and if it has only one child, make that child the new root.

---

Python Code Example: Deletion from a B+ Tree

Below is a Python implementation that demonstrates how to perform deletion in a B+ Tree. The code includes functions for searching, deleting, and rebalancing the tree by borrowing or merging nodes.

class BPlusTreeNode:
    def __init__(self, t, leaf=False):
        self.t = t  # Minimum degree (defines range for the number of keys)
        self.leaf = leaf  # True if the node is a leaf node
        self.keys = []  # List of keys in the node
        self.children = []  # List of children nodes
        self.next = None  # For linking leaf nodes in a linked list

class BPlusTree:
    def __init__(self, t):
        self.t = t  # Minimum degree
        self.root = BPlusTreeNode(t, True)  # Root node is initially a leaf node

    def delete(self, key):
        # Call delete on the root and adjust the tree if needed
        self.delete_from_node(self.root, key)
        if len(self.root.keys) == 0:
            # If the root has no keys, set the root to its only child
            if not self.root.leaf:
                self.root = self.root.children[0]

    def delete_from_node(self, node, key):
        if node.leaf:
            # If the key is in the leaf node, delete it directly
            if key in node.keys:
                node.keys.remove(key)
            return

        # If the key is not in the leaf, navigate through the internal node
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1

        child = node.children[i]
        if len(child.keys) < self.t - 1:
            # If the child is underfull, try to fix it by borrowing or merging
            self.fix_underflow(node, i)

        self.delete_from_node(node.children[i], key)

    def fix_underflow(self, parent, index):
        # Fix underflow in the child node by borrowing or merging
        child = parent.children[index]
        if index > 0 and len(parent.children[index - 1].keys) > self.t - 1:
            # Borrow a key from the left sibling
            left_sibling = parent.children[index - 1]
            self.borrow_from_left(parent, index, left_sibling, child)
        elif index < len(parent.children) - 1 and len(parent.children[index + 1].keys) > self.t - 1:
            # Borrow a key from the right sibling
            right_sibling = parent.children[index + 1]
            self.borrow_from_right(parent, index, child, right_sibling)
        else:
            # Merge the node with a sibling
            if index < len(parent.children) - 1:
                # Merge with the right sibling
                self.merge(parent, index, child, parent.children[index + 1])
            else:
                # Merge with the left sibling
                self.merge(parent, index - 1, parent.children[index - 1], child)

    def borrow_from_left(self, parent, index, left_sibling, child):
        # Move a key from the left sibling to the parent, and move a key from the parent to the child
        parent.keys[index - 1] = left_sibling.keys[-1]
        child.keys.insert(0, parent.keys[index - 1])
        left_sibling.keys.pop()

    def borrow_from_right(self, parent, index, child, right_sibling):
        # Move a key from the right sibling to the parent, and move a key from the parent to the child
        parent.keys[index] = right_sibling.keys[0]
        child.keys.append(parent.keys[index])
        right_sibling.keys.pop(0)

    def merge(self, parent, index, left_child, right_child):
        # Merge left_child and right_child, and update the parent
        left_child.keys.append(parent.keys[index])
        left_child.keys.extend(right_child.keys)
        parent.keys.pop(index)
        parent.children.pop(index + 1)

    def inorder_traversal(self):
        # Perform an in-order traversal to print keys in sorted order
        self.inorder_traversal_helper(self.root)

    def inorder_traversal_helper(self, node):
        if node:
            i = 0
            while i < len(node.keys):
                if not node.leaf:
                    self.inorder_traversal_helper(node.children[i])
                print(node.keys[i], end=" ")
                i += 1
            if not node.leaf:
                self.inorder_traversal_helper(node.children[i])

# Example Usage
btree = BPlusTree(3)  # Create a B+ tree with minimum degree 3
keys = [10, 20, 5, 6, 12, 30, 7, 17]

# Insert keys into the B+ Tree
for key in keys:
    btree.insert(key)

# In-order Traversal (prints keys in sorted order)
print("In-order Traversal of B+ Tree before deletion:")
btree.inorder_traversal()

# Deleting a key from the B+ Tree
key_to_delete = 12
print(f"\nDeleting key {key_to_delete} from B+ Tree...")
btree.delete(key_to_delete)

# In-order Traversal after deletion (prints keys in sorted order)
print("In-order Traversal of B+ Tree after deletion:")
btree.inorder_traversal()

---

Explanation of the Code

1. BPlusTreeNode Class:

   • Represents a node in the B+ Tree, containing keys and pointers to children nodes.
   • The next pointer is used for linking leaf nodes in a doubly linked list.

2. BPlusTree Class:

   • Manages the B+ Tree operations, including insertion, deletion, and rebalancing.
   • The delete method removes the key from the B+ Tree, calling helper methods like delete_from_node to recursively navigate the tree and perform necessary operations.
   • fix_underflow handles the situation where a node becomes underfull after deletion. It either borrows a key from a sibling or merges nodes to maintain balance.
   • borrow_from_left and borrow_from_right move keys between siblings to rebalance the tree.
   • merge combines two nodes into one when they are underfull and cannot borrow keys from siblings.

---

---