Node Merging

Node merging is the symmetric counterpart to node splitting. Where splitting handles overflow during insertion, merging handles underflow during deletion. Together, these operations form the complete balancing mechanism that keeps B-trees efficient regardless of the operation mix.

While we introduced merging conceptually in the deletion algorithm, this page explores the operation in exhaustive detail—examining the mechanics, cascading effects, edge cases, and optimizations that production implementations must handle.

Merging combines two sibling nodes and their parent's separator into a single node. This operation is triggered when deletion would cause underflow and no sibling has keys to spare.

Pre-conditions for merging:

1. A node has t-1 keys (minimum) and deletion would reduce it to t-2 (underflow)
2. The node's sibling also has exactly t-1 keys (cannot lend)
3. The parent exists and has at least one separator to contribute

Post-conditions after merging:

1. Merged node contains: (t-1) + 1 + (t-1) = 2t-1 keys (exactly full)
2. Parent loses one key (the separator) and one child pointer
3. One node is freed (returned to storage pool)
4. All invariants preserved

Why 2t-1 keys result:

• Left sibling: t-1 keys
• Separator from parent: 1 key
• Right sibling: t-1 keys
• Total: t-1 + 1 + t-1 = 2t-1 = maximum capacity

This is exactly the inverse of splitting, where a 2t-1-key node becomes two (t-1)-key nodes plus one promoted separator.

Here is the complete, production-quality merge algorithm with all necessary operations:

MERGE-NODES(parent, separatorIndex):
    Input: parent         - the parent of the nodes being merged
           separatorIndex - index of the separator key in parent.keys[]
                            (also index of left child in parent.children[])
    
    // Step 1: Identify the nodes to merge
    leftNode ← parent.children[separatorIndex]
    rightNode ← parent.children[separatorIndex + 1]
    
    // Step 2: Pull separator from parent into left node
    leftNode.keys[leftNode.numKeys] ← parent.keys[separatorIndex]
    leftNode.numKeys ← leftNode.numKeys + 1
    
    // Step 3: Copy all keys and values from right node to left node
    FOR j ← 0 TO rightNode.numKeys - 1:
        leftNode.keys[leftNode.numKeys + j] ← rightNode.keys[j]
        IF leftNode.isLeaf:
            leftNode.values[leftNode.numKeys + j] ← rightNode.values[j]
    
    // Step 4: For internal nodes, copy child pointers
    IF NOT leftNode.isLeaf:
        FOR j ← 0 TO rightNode.numKeys:  // Note: one more child than keys
            leftNode.children[leftNode.numKeys + j] ← rightNode.children[j]
    
    // Step 5: Update left node's key count
    leftNode.numKeys ← leftNode.numKeys + rightNode.numKeys
    
    // Step 6: Remove separator and right child pointer from parent
    FOR j ← separatorIndex TO parent.numKeys - 2:
        parent.keys[j] ← parent.keys[j + 1]
    FOR j ← separatorIndex + 1 TO parent.numKeys - 1:
        parent.children[j] ← parent.children[j + 1]
    parent.numKeys ← parent.numKeys - 1
    
    // Step 7: For B+-tree leaves, update sibling pointers
    IF leftNode.isLeaf:
        leftNode.nextLeaf ← rightNode.nextLeaf
        IF rightNode.nextLeaf ≠ NULL:
            rightNode.nextLeaf.prevLeaf ← leftNode
    
    // Step 8: Free the right node and persist changes
    FREE-NODE(rightNode)
    DISK-WRITE(leftNode)
    DISK-WRITE(parent)

When a merge consumes a separator from the parent, the parent's key count decreases. If the parent was already at minimum occupancy (t-1 keys), it now underflows (t-2 keys), potentially triggering another merge at the parent level.

Example of Cascading Merges (t=3, min keys=2):

Initial state:

                    [50]                ← Root with 1 key
                   /    
            [20, 30]    [70, 80]        ← Internal nodes at minimum
           /   |   \    /   |   
        [...] [...] [...]  [...]  [...]
                     ↑
              Deleting from here will cascade

Step 1: Delete causes leaf underflow → merge leaves Merging leaves consumes separator from [70, 80], which becomes [70]. But [70] now has only 1 key (below minimum of 2)!

Step 2: Internal node underflow → try to borrow from [20, 30] [20, 30] has 2 keys = minimum, cannot lend.

Step 3: Merge internal nodes [20, 30] and [70]

                    []                  ← Root now empty!
                    |
            [20, 30, 50, 70]           ← Merged internal node
           /   |    |    |
        [...] [...][...][...]

Step 4: Root collapse

            [20, 30, 50, 70]           ← This is now the root
           /    |    |    
        [...] [...][...][...]

Tree height reduced from 3 to 2!

Cascade Probability Analysis:

Cascading merges require a chain of nodes all at minimum occupancy. With random deletions:

• Probability of a node being at minimum: ~50% (since nodes range from 50% to 100% full)
• Probability of 2 consecutive nodes at minimum: ~25%
• Probability of 3 consecutive nodes at minimum: ~12.5%
• Probability of cascade to root (h levels): ~(0.5)^h

For h=4 (typical tree height), full cascade probability ≈ 6%. Cascades are uncommon but must be handled correctly.

Proactive Rebalancing Prevents Cascades:

Just as proactive splitting prevents cascading splits during insertion, proactive rebalancing during deletion ensures we never need to cascade:

Before descending to child[i]:
    IF child[i].numKeys = t-1:  // At minimum
        IF sibling has spare keys:
            Borrow (redistribute)
        ELSE:
            Merge with sibling now

This guarantees the child we descend into has ≥t keys, so even after deleting one, it still has ≥t-1 (valid).

Like splitting, merging differs between leaf and internal nodes, particularly for B+-trees.

Leaf Node Merges:

• Contain actual data (key-value pairs)
• For B+-trees: separator from parent IS NOT copied down (it's just dropped)
• Why? Because separator was a COPY of a leaf key that's already in the merged node
• Sibling pointers must be updated

Internal Node Merges:

• Contain only separators and child pointers
• Separator from parent IS copied down (becomes a key in merged node)
• This separator originally came from a split; now it returns
• No sibling pointer maintenance (except B-link trees)

Before merging, we should first attempt redistribution (borrowing). Redistribution keeps the node count stable and often results in better balance.

Decision Algorithm:

FIX-UNDERFLOW(parent, childIndex):
    child ← parent.children[childIndex]
    
    IF child.numKeys >= t:
        RETURN  // No underflow
    
    leftSibling ← childIndex > 0 ? parent.children[childIndex - 1] : NULL
    rightSibling ← childIndex < parent.numKeys ? parent.children[childIndex + 1] : NULL
    
    // Preference 1: Borrow from left sibling
    IF leftSibling ≠ NULL AND leftSibling.numKeys > t - 1:
        REDISTRIBUTE-FROM-LEFT(parent, childIndex)
        RETURN
    
    // Preference 2: Borrow from right sibling
    IF rightSibling ≠ NULL AND rightSibling.numKeys > t - 1:
        REDISTRIBUTE-FROM-RIGHT(parent, childIndex)
        RETURN
    
    // Preference 3: Merge with left sibling (if exists)
    IF leftSibling ≠ NULL:
        MERGE-NODES(parent, childIndex - 1)  // Merge into left
        RETURN
    
    // Preference 4: Merge with right sibling
    MERGE-NODES(parent, childIndex)  // Merge right into child

Why Prefer Redistribution?

When Merge is Inevitable:

Merge is necessary when both siblings are at minimum occupancy. After merge, the resulting node is full (2t-1 keys). If we then need to delete from it, we can safely do so (resulting in 2t-2 ≥ t-1 for t ≥ 2).

Redistribution moves keys between siblings through the parent, avoiding merge. Let's examine both directions in detail.

Redistribute from Left Sibling:

REDISTRIBUTE-FROM-LEFT(parent, childIndex):
    child ← parent.children[childIndex]
    leftSibling ← parent.children[childIndex - 1]
    
    // Make room in child: shift everything right
    FOR i ← child.numKeys - 1 DOWNTO 0:
        child.keys[i + 1] ← child.keys[i]
        IF child.isLeaf:
            child.values[i + 1] ← child.values[i]
    IF NOT child.isLeaf:
        FOR i ← child.numKeys DOWNTO 0:
            child.children[i + 1] ← child.children[i]
    
    // Separator from parent moves down to child's first position
    child.keys[0] ← parent.keys[childIndex - 1]
    child.numKeys ← child.numKeys + 1
    
    // Left sibling's last key moves up to parent
    parent.keys[childIndex - 1] ← leftSibling.keys[leftSibling.numKeys - 1]
    
    // For internal nodes, also transfer child pointer
    IF NOT child.isLeaf:
        child.children[0] ← leftSibling.children[leftSibling.numKeys]
    ELSE:
        child.values[0] ← leftSibling.values[leftSibling.numKeys - 1]
    
    leftSibling.numKeys ← leftSibling.numKeys - 1
    
    DISK-WRITE(child)
    DISK-WRITE(leftSibling)
    DISK-WRITE(parent)

Redistribute from Right Sibling:

REDISTRIBUTE-FROM-RIGHT(parent, childIndex):
    child ← parent.children[childIndex]
    rightSibling ← parent.children[childIndex + 1]
    
    // Separator from parent moves down to child's last position
    child.keys[child.numKeys] ← parent.keys[childIndex]
    child.numKeys ← child.numKeys + 1
    
    // Right sibling's first key moves up to parent
    parent.keys[childIndex] ← rightSibling.keys[0]
    
    // For internal nodes, also transfer child pointer
    IF NOT child.isLeaf:
        child.children[child.numKeys] ← rightSibling.children[0]
    ELSE:
        child.values[child.numKeys - 1] ← rightSibling.values[0]
    
    // Shift right sibling's contents left
    FOR i ← 0 TO rightSibling.numKeys - 2:
        rightSibling.keys[i] ← rightSibling.keys[i + 1]
        IF rightSibling.isLeaf:
            rightSibling.values[i] ← rightSibling.values[i + 1]
    IF NOT rightSibling.isLeaf:
        FOR i ← 0 TO rightSibling.numKeys - 1:
            rightSibling.children[i] ← rightSibling.children[i + 1]
    
    rightSibling.numKeys ← rightSibling.numKeys - 1
    
    DISK-WRITE(child)
    DISK-WRITE(rightSibling)
    DISK-WRITE(parent)

Like splitting, merging modifies multiple nodes atomically. Crashes mid-operation can corrupt the tree. Production systems use similar techniques to ensure merge atomicity.

Possible Crash States:

WAL-Based Merge:

MERGE-WITH-WAL(parent, separatorIndex):
    // Step 1: Log the merge intent with full state
    logRecord ← CreateLogRecord(
        type: MERGE,
        parentPageId: parent.pageId,
        leftPageId: leftNode.pageId,
        rightPageId: rightNode.pageId,
        separatorIndex: separatorIndex,
        leftKeys: leftNode.keys,
        rightKeys: rightNode.keys,
        separator: parent.keys[separatorIndex]
    )
    WRITE-TO-WAL(logRecord)
    FLUSH-WAL()  // Ensure log is durable
    
    // Step 2: Perform the actual merge
    MERGE-NODES(parent, separatorIndex)
    
    // Step 3: Log completion
    WRITE-TO-WAL(CreateCommitRecord(logRecord.id))

Recovery Algorithm:

RECOVER-MERGE(log):
    FOR each uncommitted MERGE record in log:
        parent ← ReadPage(log.parentPageId)
        left ← ReadPage(log.leftPageId)
        right ← ReadPage(log.rightPageId)
        
        // Determine current state
        IF left contains merged content AND parent still has separator:
            // Merge was interrupted after left write
            // Redo: update parent and free right
            UpdateParent(parent, log.separatorIndex)
            FreeNode(right)
        ELSE IF parent doesn't have separator:
            // Parent was updated but right may not be freed
            IF right still allocated:
                FreeNode(right)
        ELSE:
            // Merge didn't start or completed; log can be discarded
            CONTINUE
        
        WriteCommitRecord(log.id)

Alternative: Undo Logging

Instead of logging the merge intent, log how to undo it:

1. Before modifying, write: "To undo merge: restore left to [keys], restore separator [sep] at index [i], reallocate right at [pageId] with [keys]"
2. Perform merge
3. Write commit

During recovery, uncommitted undo records trigger rollback to pre-merge state.