Delete with Redistribution

Of all B+-tree operations, deletion is the most intricate. While insertion adds nodes and grows the tree upward, deletion removes keys and may shrink the tree—potentially all the way back to a single root. The complexity arises from maintaining the minimum occupancy invariant: every non-root node must be at least half full.

When deletion causes a node to fall below minimum occupancy, the tree must respond with either redistribution (borrowing from a sibling) or merging (combining with a sibling). These operations can cascade upward through the tree, potentially decreasing tree height. Understanding deletion deeply is essential for predicting update performance, analyzing concurrency behavior, and implementing custom index structures.

B+-tree deletion follows this high-level process:

Step 1: Find the Key Search for the key to delete. It must be in a leaf node (since all data is stored in leaves).

Step 2: Delete from Leaf Remove the key and its record pointer from the leaf.

Step 3: Check for Underflow If the leaf still meets minimum occupancy requirements, we're done. Otherwise, we must fix the underflow.

Step 4: Handle Underflow Two strategies, in order of preference:

• Redistribution: Borrow a key from a sibling with more than minimum keys
• Merging: If no sibling can donate, merge with a sibling

Step 5: Update Parent After redistribution or merging, update the separator key(s) in the parent. Merging removes a separator, which may cause parent underflow.

Step 6: Propagate Upward If parent underflows, apply the same redistribution/merge logic. Continue to root if needed.

The simplest case occurs when removing a key leaves the leaf with at least the minimum number of keys. No restructuring is needed.

Process:

1. Locate the key in the leaf
2. Remove the key and its record pointer
3. Shift remaining entries to fill the gap
4. Decrement the key count

If the deleted key was the first key in the leaf and it appears as a separator in an ancestor, the separator may or may not need updating. In many implementations, stale separators are tolerated because they still route correctly (any key that would have matched the old separator will match the new first key).

Example: Delete Key = 22 from Leaf [20, 22, 28, 35]

Leaf has minimum occupancy of 2 keys (for order 5):

1. Find position: 22 is at index 1
2. Shift left: Move 28 and 35 to fill gap
3. Decrement count: 4 → 3
4. Result: [20, 28, 35]

With 3 keys remaining (≥ minimum of 2), no underflow occurs. Done!

When deletion causes a leaf to fall below minimum occupancy, we have an underflow. The B+-tree responds with one of two strategies:

Strategy 1: Redistribution (Preferred) Borrow one or more keys from an adjacent sibling that has more than the minimum. This is preferred because it doesn't change the tree structure—only key positions change.

Strategy 2: Merging (Fallback) If both adjacent siblings are at minimum occupancy (can't donate), merge the underflowing node with one sibling. This removes a node from the tree and may cascade upward.

Finding Siblings:

To find siblings, we need the parent node and the position of the underflowing node within the parent:

• Left sibling: parent.children[position - 1] (if position > 0)
• Right sibling: parent.children[position + 1] (if position < parent.childCount - 1)
• Separating keys: parent.keys[position - 1] (between left sibling and node), parent.keys[position] (between node and right sibling)

This is why the deletion algorithm tracks the path from root to leaf—we need parent information for underflow handling.

Redistribution transfers keys between sibling nodes to resolve underflow without changing the tree structure. The process differs depending on whether we borrow from the left or right sibling.

Borrowing from Left Sibling (Leaf Nodes):

1. Take the largest key from the left sibling
2. Insert it at the beginning of the underflowing node
3. Update the separator key in the parent to reflect the new boundary

Borrowing from Right Sibling (Leaf Nodes):

1. Take the smallest key from the right sibling
2. Insert it at the end of the underflowing node
3. Update the separator key in the parent

Let's trace a complete redistribution scenario.

Setup:

• B+-tree with order 4 (min 1 key per leaf, max 3 keys per leaf)
• Delete key = 20 from the following structure:

Before Deletion:

           [25]
          /    
    [12,18,20]  [25,30,35]

Step 1: Delete 20 from left leaf

           [25]
          /    
    [12,18]    [25,30,35]

Left leaf has 2 keys, minimum is 1. No underflow! Done.

Now let's try a case that causes underflow:

Delete key = 18:

           [25]
          /    
    [12]       [25,30,35]

Left leaf has 1 key, which equals the minimum. No underflow yet.

Delete key = 12:

           [25]
          /    
    []         [25,30,35]   ← UNDERFLOW! Left leaf is empty

Step 2: Check siblings

• Right sibling [25,30,35] has 3 keys (> minimum of 1)
• Can borrow!

Step 3: Borrow from right sibling

1. Borrow smallest key from right sibling: 25
2. Insert at end of underflowing (left) node
3. Update separator in parent

After Redistribution:

           [30]           ← separator updated from 25 to 30
          /    
    [25]       [30,35]    ← 25 moved to left, right sibling shrinks

Both leaves now have at least 1 key. Tree is balanced!

When all siblings are at minimum occupancy, neither can donate a key. The only option is to merge the underflowing node with one of its siblings.

Merging Process (Leaf Nodes):

1. Choose a sibling to merge with (left or right)
2. Move all keys from the underflowing node to the sibling
3. Deallocate the now-empty underflowing node
4. Update sibling pointers to skip the deleted node
5. Remove the separator key from the parent
6. Check if parent now underflows (may cascade!)

Internal Node Merging:

Merging internal nodes is similar but includes an additional step: the separator key from the parent is pulled down into the merged node.

Merge Process for Internal Nodes:
1. Pull down the separator key from parent
2. Append all keys and children from right node to left node
3. The pulled-down separator becomes a key in the merged node
4. Remove right node and its parent entry

This is the reverse of internal node splitting, where a key was pushed up to create the separator.

Let's trace a merge that cascades to the parent.

Setup:

• B+-tree with order 3 (min 1 key per leaf, max 2 keys per leaf)
• Internal nodes: min 1 key (2 children), max 2 keys (3 children)

Initial Structure:

              [30]
             /    
         [15]      [45]
        /    \    /    
     [10]  [20] [35]  [50]

Step 1: Delete 10

              [30]
             /    
         [15]      [45]
        /    \    /    
     []    [20] [35]  [50]    ← Leftmost leaf is EMPTY (underflow)

Step 2: Check siblings for redistribution

• Right sibling [20] has 1 key = minimum
• Cannot redistribute → must merge

Step 3: Merge leaves

              [30]
             /    
         []        [45]      ← Internal node now has 0 keys (underflow!)
        /         /    
     [20]      [35]  [50]    ← Merged leaf contains [20]

Wait—the left internal node now has only 1 child and 0 keys. That's an underflow!

Step 4: Handle internal node underflow

• Check siblings: right internal sibling [45] has 1 key (minimum)
• Cannot redistribute → must merge internal nodes

Step 5: Merge internal nodes

• Pull down separator (30) from root
• Combine children: [20] + [35] + [50]
• Result:

            [30, 45]         ← New root is the merged internal node
           /   |   
        [20] [35] [50]

The root now has only one child, which means we should shrink:

Step 6: Shrink tree (root has single child)

            [30, 45]
           /   |   
        [20] [35] [50]  ← This internal node becomes the new root

Tree height decreased from 3 to 2!