B-Tree Operations: Search, Insert, and Delete

B-tree deletion is arguably the most complex of the three core operations. While search is straightforward and insertion needs only splitting, deletion must handle underflow through multiple strategies: borrowing from siblings, merging with siblings, and rebalancing separators in ancestors.

Every DELETE FROM statement that affects an indexed column triggers B-tree deletions across all relevant indexes. Understanding this operation is essential for maintaining database performance and ensuring index integrity.

Deletion must preserve all B-tree invariants while removing a key. The challenge arises when removal would leave a node with fewer than the minimum required keys.

Invariants that Deletion Must Maintain:

1. Minimum Occupancy: Every non-root node must have at least ⌈t/2⌉-1 keys (typically t-1 for minimum degree t)
2. Maximum Occupancy: No node exceeds 2t-1 keys
3. Ordering: Keys within nodes and across the tree remain sorted
4. Balance: All leaves remain at the same depth
5. Root Occupancy: Root can have as few as 1 key (or 0 if tree becomes empty)

The Underflow Problem:

When a node has exactly t-1 keys (minimum allowed) and we delete one key:

• The node would have t-2 keys
• This violates the minimum occupancy invariant
• We must rebalance by borrowing from siblings or merging

B-tree deletion breaks down into three fundamental cases based on where the key is located:

Case 1: Key is in a Leaf Node

The simplest case—if removing the key doesn't cause underflow, simply remove it. If underflow occurs, rebalance with siblings.

Case 2: Key is in an Internal Node

We cannot simply remove from an internal node because it serves as a separator. Instead, replace it with its predecessor or successor from a leaf, then delete that replacement from the leaf.

Case 3: Key is Not in Current Node

The key might be in a subtree. Ensure the child we descend into has enough keys to handle a potential deletion (proactive rebalancing), then recurse.

High-Level Algorithm:

BTREE-DELETE(node, key):
    i ← FindKeyIndex(node, key)  // Position where key is or would be
    
    IF key is found at node.keys[i]:  // Key in this node
        IF node.isLeaf:
            CASE 1: Delete from leaf
        ELSE:
            CASE 2: Delete from internal node
    ELSE:  // Key not in this node
        IF node.isLeaf:
            RETURN "Key not found"  // Base case: key doesn't exist
        ELSE:
            CASE 3: Ensure child has enough keys, then recurse

Let's examine each case in detail.

Leaf deletion is the base case—the key and its associated data are directly removed. The complexity arises from maintaining minimum occupancy.

Sub-case 1a: Leaf has spare keys

If the leaf has more than t-1 keys, simply remove the key:

DELETE-FROM-LEAF(leaf, keyIndex):
    // Shift keys and values left to close the gap
    FOR i ← keyIndex TO leaf.numKeys - 2:
        leaf.keys[i] ← leaf.keys[i + 1]
        leaf.values[i] ← leaf.values[i + 1]
    leaf.numKeys ← leaf.numKeys - 1
    DISK-WRITE(leaf)

Example:

Before: [10, 20, 30, 40]  (t=3, min=2 keys, current=4)
Delete 20: [10, 30, 40]  (3 keys ≥ 2, OK)

Sub-case 1b: Leaf will underflow—borrow from sibling

If deleting would cause underflow but a sibling has spare keys, borrow:

BORROW-FROM-LEFT-SIBLING(parent, nodeIndex):
    node ← parent.children[nodeIndex]
    leftSibling ← parent.children[nodeIndex - 1]
    
    // Make room in node by shifting keys right
    FOR i ← node.numKeys - 1 DOWNTO 0:
        node.keys[i + 1] ← node.keys[i]
        node.values[i + 1] ← node.values[i]
    
    // Pull separator from parent into node's first position
    node.keys[0] ← parent.keys[nodeIndex - 1]
    
    // Move sibling's last key up to parent as new separator
    parent.keys[nodeIndex - 1] ← leftSibling.keys[leftSibling.numKeys - 1]
    
    // Transfer sibling's last value to node
    node.values[0] ← leftSibling.values[leftSibling.numKeys - 1]
    
    leftSibling.numKeys ← leftSibling.numKeys - 1
    node.numKeys ← node.numKeys + 1
    
    DISK-WRITE(leftSibling)
    DISK-WRITE(node)
    DISK-WRITE(parent)

Example:

Before:
  Parent: [..., 30, ...]
            /      
   [10, 20, 25]    [40]  ← Need to delete 40, will underflow

Borrow from left sibling:
  Parent: [..., 25, ...]
            /      
   [10, 20]        [30, 40]  
   
Now delete 40:
  Parent: [..., 25, ...]
            /      
   [10, 20]        [30]  ← Valid (≥ min keys)

When no sibling has spare keys to borrow, we must merge the underflowing node with a sibling. This is the inverse of splitting.

Merge Algorithm:

MERGE-NODES(parent, leftIndex):
    // Merge children[leftIndex] and children[leftIndex + 1]
    leftNode ← parent.children[leftIndex]
    rightNode ← parent.children[leftIndex + 1]
    
    // Pull separator key from parent into left node
    leftNode.keys[leftNode.numKeys] ← parent.keys[leftIndex]
    leftNode.numKeys ← leftNode.numKeys + 1
    
    // Copy all keys from right node to left node
    FOR j ← 0 TO rightNode.numKeys - 1:
        leftNode.keys[leftNode.numKeys] ← rightNode.keys[j]
        leftNode.values[leftNode.numKeys] ← rightNode.values[j]
        leftNode.numKeys ← leftNode.numKeys + 1
    
    // If internal nodes, also copy child pointers
    IF NOT leftNode.isLeaf:
        FOR j ← 0 TO rightNode.numKeys:
            leftNode.children[leftNode.numKeys - rightNode.numKeys + j] ← rightNode.children[j]
    
    // Remove separator and right child from parent
    FOR j ← leftIndex TO parent.numKeys - 2:
        parent.keys[j] ← parent.keys[j + 1]
        parent.children[j + 1] ← parent.children[j + 2]
    parent.numKeys ← parent.numKeys - 1
    
    // Free the right node
    FREE-NODE(rightNode)
    
    DISK-WRITE(leftNode)
    DISK-WRITE(parent)

Merge Example (t=3, min keys=2):

Before (need to delete 60 from right leaf):
        Parent: [50]
               /    
        [30, 40]    [60]  ← Will underflow (has minimum)

Both siblings at minimum, cannot borrow.
Merge left + separator + right:

        Parent: []   ← Empty! Might collapse if root
              |
    [30, 40, 50, 60]

Now delete 60:
        Parent: []   
              |
    [30, 40, 50]  ← Valid leaf

Key insight: Merging reduces the parent's key count by 1 (the separator is consumed). If the parent was at minimum, this triggers cascading rebalancing.

B+-Tree Leaf Merge Specifics:

For B+-tree leaves, merging also requires updating the sibling linked list:

MERGE-LEAF-NODES(parent, leftIndex):
    // ... standard merge operations ...
    
    // Update leaf linked list
    leftNode.nextLeaf ← rightNode.nextLeaf
    IF rightNode.nextLeaf ≠ NULL:
        rightNode.nextLeaf.prevLeaf ← leftNode

Forgetting this update breaks range query traversal after the merge point.

Deleting a key from an internal node is more complex because internal keys serve as separators—they define the boundaries between subtrees. We cannot simply remove them without breaking the tree structure.

Strategy: Replace and Delete

Instead of removing the key directly, replace it with its in-order predecessor or in-order successor (both are in leaves), then delete that replacement from the leaf.

    [key to delete: 50]
           /          
    [..., 45]        [55, ...]
           ↑              ↑
    Predecessor    Successor
      (45)           (55)

Predecessor: The rightmost key in the left subtree Successor: The leftmost key in the right subtree

Both are guaranteed to be in leaf nodes, converting Case 2 to Case 1.

Algorithm for Case 2:

DELETE-FROM-INTERNAL(node, keyIndex):
    key ← node.keys[keyIndex]
    
    // Case 2a: Left child has enough keys
    IF node.children[keyIndex].numKeys >= t:
        predecessor ← GET-PREDECESSOR(node.children[keyIndex])
        node.keys[keyIndex] ← predecessor.key
        BTREE-DELETE(node.children[keyIndex], predecessor.key)
    
    // Case 2b: Right child has enough keys
    ELSE IF node.children[keyIndex + 1].numKeys >= t:
        successor ← GET-SUCCESSOR(node.children[keyIndex + 1])
        node.keys[keyIndex] ← successor.key
        BTREE-DELETE(node.children[keyIndex + 1], successor.key)
    
    // Case 2c: Both children have minimum keys—merge, then delete
    ELSE:
        MERGE-NODES(node, keyIndex)  // Merges children[keyIndex] and [keyIndex+1]
        BTREE-DELETE(node.children[keyIndex], key)  // Key now in merged node

GET-PREDECESSOR(node):
    // Navigate to rightmost leaf, return rightmost key
    WHILE NOT node.isLeaf:
        node ← node.children[node.numKeys]
    RETURN node.keys[node.numKeys - 1]

GET-SUCCESSOR(node):
    // Navigate to leftmost leaf, return leftmost key
    WHILE NOT node.isLeaf:
        node ← node.children[0]
    RETURN node.keys[0]

When the key to delete is not in the current node, we must descend to a child. But what if that child has exactly t-1 keys? Deleting from it would cause underflow.

Proactive Rebalancing: Before descending, ensure the target child has at least t keys. This guarantees that deletion can proceed without upward propagation.

CASE-3-ENSURE-CHILD-HAS-ENOUGH(node, childIndex):
    child ← node.children[childIndex]
    
    IF child.numKeys >= t:
        RETURN  // Already has enough keys
    
    // Child has exactly t-1 keys; need to add one
    leftSibling ← childIndex > 0 ? node.children[childIndex - 1] : NULL
    rightSibling ← childIndex < node.numKeys ? node.children[childIndex + 1] : NULL
    
    // Case 3a: Borrow from left sibling
    IF leftSibling ≠ NULL AND leftSibling.numKeys >= t:
        BORROW-FROM-LEFT(node, childIndex)
    
    // Case 3b: Borrow from right sibling
    ELSE IF rightSibling ≠ NULL AND rightSibling.numKeys >= t:
        BORROW-FROM-RIGHT(node, childIndex)
    
    // Case 3c: Can't borrow; merge with a sibling
    ELSE:
        IF leftSibling ≠ NULL:
            MERGE-NODES(node, childIndex - 1)  // Merge child with left sibling
            childIndex ← childIndex - 1        // Merged node is at original left sibling's position
        ELSE:
            MERGE-NODES(node, childIndex)      // Merge child with right sibling
    
    // Now descend into the child (which now has enough keys)
    RETURN node.children[childIndex]

Borrowing in Detail:

BORROW-FROM-LEFT(parent, childIndex):
    child ← parent.children[childIndex]
    leftSibling ← parent.children[childIndex - 1]
    
    // Shift child's keys/children right to make room
    FOR i ← child.numKeys DOWNTO 0:
        child.keys[i + 1] ← child.keys[i]
    IF NOT child.isLeaf:
        FOR i ← child.numKeys + 1 DOWNTO 0:
            child.children[i + 1] ← child.children[i]
    
    // Parent's separator moves down to child
    child.keys[0] ← parent.keys[childIndex - 1]
    
    // Sibling's rightmost key moves up to parent
    parent.keys[childIndex - 1] ← leftSibling.keys[leftSibling.numKeys - 1]
    
    // If internal, also transfer sibling's rightmost child
    IF NOT child.isLeaf:
        child.children[0] ← leftSibling.children[leftSibling.numKeys]
    
    leftSibling.numKeys ← leftSibling.numKeys - 1
    child.numKeys ← child.numKeys + 1

The rotation brings the separator down and the sibling's key up, maintaining order.

When deletion causes the root to become empty (0 keys), the tree height must decrease. This is the inverse of root splitting.

Condition: Root has 0 keys and 1 child (can only happen after a merge that consumed the root's last separator).

Action: The single child becomes the new root.

COLLAPSE-ROOT-IF-NEEDED(tree):
    IF tree.root.numKeys = 0 AND NOT tree.root.isLeaf:
        oldRoot ← tree.root
        tree.root ← tree.root.children[0]  // Sole child becomes root
        FREE-NODE(oldRoot)
        tree.height ← tree.height - 1

Example:

Before (delete 50, causes merge, root has 1 key consumed):
         [50]           ← Root with 1 key
        /    
    [30]     [70]

After merge of root's children:
         []              ← Root empty!
         |
    [30, 50, 70]         ← Merged child

After collapse:
    [30, 50, 70]         ← This is now the root

Now delete 50:
    [30, 70]             ← Tree height reduced by 1

Edge Case: Deleting the Last Key

When the tree contains a single key in a single-node root:

Tree: [42]  ← Only key in tree

Delete 42:
  - Root becomes empty
  - Root is a leaf (no children)
  - Tree is empty

EMPTY-TREE(tree):
    IF tree.root.numKeys = 0 AND tree.root.isLeaf:
        tree.root ← NULL
        // Or keep empty root for future insertions

Some implementations maintain an empty root node rather than nullifying it, avoiding allocation on the next insert.

Let's consolidate all cases into a complete, production-ready algorithm:

BTREE-DELETE(tree, key):
    // Handle root collapse after deletion
    DELETE-FROM-NODE(tree.root, key)
    
    // Check if root needs collapsing
    IF tree.root.numKeys = 0 AND NOT tree.root.isLeaf:
        tree.root ← tree.root.children[0]
        FREE-NODE(oldRoot)

DELETE-FROM-NODE(node, key):
    i ← FindKeyPosition(node, key)
    
    // Key found in this node
    IF i < node.numKeys AND node.keys[i] = key:
        IF node.isLeaf:
            // Case 1: Simple leaf deletion
            DeleteFromLeaf(node, i)
        ELSE:
            // Case 2: Internal node deletion
            DeleteFromInternal(node, i)
    
    // Key not in this node
    ELSE:
        IF node.isLeaf:
            RETURN  // Key not found in tree
        
        // Ensure child has enough keys before descending
        EnsureChildHasEnoughKeys(node, i)
        
        // Recurse into appropriate child
        DELETE-FROM-NODE(node.children[i], key)

Full deletion (with rebalancing) is expensive. Many production systems use lazy deletion strategies that defer or avoid structural modifications.

Strategy 1: Tombstone Marking

Instead of removing keys, mark them as deleted:

LAZY-DELETE(tree, key):
    node ← FindLeafContaining(tree.root, key)
    i ← FindKeyInNode(node, key)
    
    IF key found:
        node.deleted[i] ← TRUE  // Tombstone marker
        tree.deletedCount ← tree.deletedCount + 1
        DISK-WRITE(node)

Advantages:

• O(log n) deletion with single write
• No structural changes
• Easy to implement concurrent deletion

Disadvantages:

• Wasted space for deleted keys
• Searches must skip tombstones
• Eventually need compaction

Strategy 2: Deferred Compaction

Combine tombstone marking with periodic compaction:

PERIODIC-COMPACTION(tree):
    IF tree.deletedCount / tree.totalKeys > THRESHOLD:
        FOR each node in tree:
            CompactNode(node)  // Remove tombstones, rebalance if needed
        RebuildIfNecessary(tree)
        tree.deletedCount ← 0

This amortizes structural modification cost across many deletions.

Strategy 3: MVCC (Multi-Version Concurrency Control)

Rather than deleting, create a new version of the tree without the key:

• Old version remains for active transactions
• Garbage collection removes unreachable versions
• Common in PostgreSQL, CockroachDB, etc.

Strategy 4: Log-Structured Merge (LSM) Trees

An entirely different approach:

• All writes go to an in-memory buffer
• Deletions are "delete markers" in the buffer
• Periodic merge compacts and applies deletions
• Used by LevelDB, RocksDB, Cassandra

B-tree deletion is the most complex core operation, requiring careful handling of underflow through borrowing and merging. Let's consolidate the essential knowledge: