Node Splitting

Node splitting is the defining operation that gives B-trees their self-balancing property. Unlike naive binary search trees that can degenerate into linked lists with skewed insertions, B-trees distribute keys across the tree through splitting, guaranteeing logarithmic height regardless of insertion patterns.

While we introduced splitting conceptually in the insertion algorithm, this page explores the operation in exhaustive detail—examining the mechanics, edge cases, optimizations, and failure modes that production implementations must handle.

When a node exceeds its maximum capacity of 2t-1 keys (for minimum degree t), it must be split into two nodes, each containing an acceptable number of keys. Let's dissect this operation component by component.

Pre-conditions for splitting:

• The node has exactly 2t-1 keys (full state)
• The parent node exists and has fewer than 2t-1 keys (guaranteed by proactive splitting)
• Or, if splitting the root, there is no parent yet

Post-conditions after splitting:

• Original node: contains t-1 keys (indices 0 to t-2)
• New sibling: contains t-1 keys (indices t to 2t-2)
• Parent: gains 1 new key (the median) and 1 new child pointer
• Ordering invariant: preserved

The Mathematics of Even Division:

With 2t-1 keys and a split:

• Keys to stay in left node: t-1 (indices 0 through t-2)
• Key to promote: 1 (index t-1, the median)
• Keys to move to right node: t-1 (indices t through 2t-2)

Verification: (t-1) + 1 + (t-1) = 2t-1 ✓

This perfect division ensures both resulting nodes satisfy the minimum occupancy requirement of t-1 keys.

For child pointers (internal nodes): With 2t children (indices 0 through 2t-1) before split:

• Children to stay: t (indices 0 through t-1)
• Children to move: t (indices t through 2t-1)

Verification: t + t = 2t ✓

Each node retains one more child pointer than keys, maintaining the key-pointer relationship.

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

SPLIT-CHILD(parent, childIndex):
    Input: parent     - the parent node of the node being split
           childIndex - index of the child to split in parent.children[]
    
    // Step 1: Get the full child and allocate new sibling
    fullChild ← parent.children[childIndex]
    newSibling ← AllocateNode()
    newSibling.isLeaf ← fullChild.isLeaf
    newSibling.numKeys ← t - 1
    
    // Step 2: Copy upper half of keys to new sibling
    FOR j ← 0 TO t - 2:
        newSibling.keys[j] ← fullChild.keys[t + j]
        // For B+-tree leaves, also copy values
        IF fullChild.isLeaf:
            newSibling.values[j] ← fullChild.values[t + j]
    
    // Step 3: For internal nodes, copy child pointers
    IF NOT fullChild.isLeaf:
        FOR j ← 0 TO t - 1:
            newSibling.children[j] ← fullChild.children[t + j]
    
    // Step 4: Truncate the full child
    fullChild.numKeys ← t - 1
    
    // Step 5: Make room in parent for new child pointer
    FOR j ← parent.numKeys DOWNTO childIndex + 1:
        parent.children[j + 1] ← parent.children[j]
    parent.children[childIndex + 1] ← newSibling
    
    // Step 6: Make room in parent for median key
    FOR j ← parent.numKeys - 1 DOWNTO childIndex:
        parent.keys[j + 1] ← parent.keys[j]
    
    // Step 7: Moving the median key to parent
    parent.keys[childIndex] ← fullChild.keys[t - 1]
    parent.numKeys ← parent.numKeys + 1
    
    // Step 8: For B+-tree leaves, maintain sibling pointers
    IF fullChild.isLeaf:
        newSibling.nextLeaf ← fullChild.nextLeaf
        IF fullChild.nextLeaf ≠ NULL:
            fullChild.nextLeaf.prevLeaf ← newSibling
        fullChild.nextLeaf ← newSibling
        newSibling.prevLeaf ← fullChild
    
    // Step 9: Write all modified nodes to disk
    DISK-WRITE(fullChild)
    DISK-WRITE(newSibling)
    DISK-WRITE(parent)

Root splitting is unique because it's the only operation that increases the tree's height. When the root is full and needs to split, we create a new root above it.

Algorithm: SPLIT-ROOT

SPLIT-ROOT(tree):
    Input: tree - the B-tree with a full root
    
    // Step 1: Allocate new root
    oldRoot ← tree.root
    newRoot ← AllocateNode()
    newRoot.isLeaf ← FALSE
    newRoot.numKeys ← 0
    
    // Step 2: Old root becomes first child of new root
    newRoot.children[0] ← oldRoot
    
    // Step 3: Split the old root (now a child of new root)
    SPLIT-CHILD(newRoot, 0)
    
    // Step 4: Update tree's root reference
    tree.root ← newRoot
    DISK-WRITE(newRoot)

Before root split:

  [10 | 20 | 30 | 40 | 50]  ← Full root (5 keys, t=3)

After root split:

        [30]  ← New root (height increased by 1)
       /    
   [10|20]  [40|50]  ← Old root split into two children

Key Insights about Root Splitting:

1. Height Growth is Rare: Tree height only increases through root splits. For a tree with t=100 and starting from 1 key, you need approximately 100, 10,000, 1,000,000, 100,000,000 keys to reach heights 1, 2, 3, 4 respectively. Root splits happen infrequently at scale.

2. Root Exceptions: The root is the only node allowed to have fewer than t-1 keys. After a root split, the new root has exactly 1 key.

3. Height Uniformity: All paths from root to leaves have the same length. Root splitting maintains this because it adds exactly one level above the entire previous tree.

4. Logarithmic Guarantee: Because height increases by 1 only when the number of keys roughly multiplies by t, height remains O(log_t n).

When a node splits, its median key moves to the parent. If the parent was already nearly full, it might exceed capacity and need to split as well. This is cascading or propagating splits.

Example of Cascading Splits (t=2, max 3 keys per node):

Initial state:

             [30 | 50 | 70]  ← Internal node (full)
            /    |    |    
     [10|20] [35|40|45] [55|60] [75|80|85]
                ↑ Full leaf - inserting 42 will cause cascade

Step 1: Insert 42 causes leaf split

             [30 | 50 | 70]  ← Still full, needs split
            /    |    |    
     [10|20] [35|40] [45|50] [55|60] [75|80|85]
               ↑       ↑
          Left keeps  Right takes upper half
          40 goes to parent

But wait—40 needs to go to parent, which is full!

Step 2: Parent (internal node) splits

                   [50]  ← New separator at this level
                  /    
          [30|40]      [70]
         /  |  \        |  
    [10|20] [35] [42|45] [55|60] [75|80|85]

Now the parent of [50] (the root) needs to receive this median. If the root was full too, it would split and grow the tree height.

Proactive Splitting Prevents Cascades:

With proactive splitting, we split any full node encountered during descent, before we need it:

Insert 42:
1. Root [30|50|70] is full → Split it first
   Result: new root [50], children [30] and [70]
   
2. Descend: 42 > 30, 42 < 50 → go to left subtree
   [30|40|45] is the child (after leaf split from previous ops)
   This node has space → proceed
   
3. At leaf [35|40|45]: full → Split during descent
   Result: [35|40] and [45], median 40 goes to parent [30|40]
   
4. Now insert 42 into [45|48...] → space available, done

Proactive splitting ensures that when we need to insert a median into a parent, the parent always has room—because we already split it if it was full.

While the splitting principle is the same, leaf and internal node splits differ in important implementation details, especially for B+-trees.

Leaf Node Splits:

• Contain actual data (key-value pairs)
• For B+-trees: median key is copied up (remains in leaf for data access)
• Sibling pointers must be updated to maintain linked list
• May trigger prefetching of adjacent leaves for range queries

Internal Node Splits:

• Contain only keys and child pointers (separators)
• Median key is moved up (does not remain in the split node)
• No sibling linking required (B-link trees are an exception)
• May affect routing decisions for concurrent operations

Node splitting directly impacts space utilization. Let's analyze how full nodes typically are and techniques to optimize space usage.

Theoretical Analysis:

• After a split, both nodes are exactly 50% full (t-1 keys out of 2t-1 capacity)
• As insertions continue, nodes fill from 50% toward 100%
• Average fill factor with random insertions: approximately ln(2) ≈ 69%

This 69% figure comes from a classic analysis: if we model node contents as a random variable between t-1 and 2t-1 with uniform splitting, the expected value converges to about 69% of capacity.

Space Utilization Formula:

$$\text{Average fill} = \frac{\text{Average keys per node}}{\text{Maximum keys per node}} = \frac{\ln(2) \cdot (2t-1)}{2t-1} \approx 69%$$

Techniques to Improve Fill Factor:

1. Delayed Splitting (Redistribution First): When a node is full, try to redistribute keys with a sibling before splitting.

   IF sibling has room:
       Transfer some keys from full node to sibling
       Update parent separator
       No split needed
   ELSE:
       Proceed with split
   

   This can push fill factor to ~75-80%.

2. B-Trees (2/3 Full Minimum):*

   • Before splitting, redistribute keys with both siblings
   • Split three full nodes into four 2/3-full nodes
   • Minimum occupancy: 2t/3 instead of t/2
   • Fill factor: approximately 81%

3. Bulk Loading:

   • Pack nodes to near-100% capacity initially
   • Subsequent insertions may cause splits, but overall density remains high

4. Index Rebuilding:

   • Periodically rebuild indexes to restore optimal packing
   • Common in data warehouse batch processing

A split modifies three nodes: the original (now left), the new sibling (right), and the parent. If a system crash occurs mid-operation, the tree could be left in an inconsistent state. Production systems employ several strategies to ensure atomicity.

Failure Scenarios:

1. Crash after writing left node only:

   • Left node truncated but no right sibling exists
   • Keys in upper half are lost
   • Tree internally consistent but data lost

2. Crash after writing left and right nodes:

   • Both child nodes exist but parent doesn't reference right sibling
   • Right sibling is orphaned (unreachable)
   • Tree internally consistent but right sibling is a space leak

3. Crash after writing all but updating tree metadata:

   • All nodes written but root pointer unchanged (for root split)
   • New root exists but isn't reachable

Solution 1: Write-Ahead Logging (WAL)

The standard approach in databases:

SPLIT-WITH-WAL(parent, childIndex):
    // Step 1: Log the intent
    logRecord ← CreateLogRecord(
        type: SPLIT,
        parentPageId: parent.pageId,
        childIndex: childIndex,
        originalKeys: fullChild.keys,
        timestamp: now()
    )
    WRITE-TO-WAL(logRecord)
    FLUSH-WAL()  // Ensure log is on stable storage
    
    // Step 2: Perform the actual split
    SPLIT-CHILD(parent, childIndex)
    
    // Step 3: Commit
    commitRecord ← CreateLogRecord(type: COMMIT, splitLogId: logRecord.id)
    WRITE-TO-WAL(commitRecord)

Recovery process:

• Scan log for uncommitted split operations
• For each uncommitted split: either redo completely or undo completely based on state
• Guarantee: tree is always in a valid state after recovery

Solution 2: Shadow Paging

Create new versions of modified pages without overwriting originals:

SPLIT-WITH-SHADOW-PAGES(parent, childIndex):
    // Allocate new pages for all modifications
    newParent ← CopyPage(parent)
    newLeft ← CopyPage(fullChild)  // Will be truncated
    newRight ← AllocatePage()       // New sibling
    
    // Perform split on new copies
    PerformSplit(newParent, newLeft, newRight)
    
    // Atomic update: change one pointer to swap trees
    parentOfParent.children[idx] ← newParent  // Single atomic write
    
    // Mark old pages as free (after ensuring durability)
    DeferredFree(parent, fullChild)

Shadow paging avoids in-place updates but can fragment storage.

Solution 3: B-Link Tree Approach

B-link trees add high-key markers and sibling pointers that make splits visible even if the parent hasn't been updated:

• Each node stores its "high key" (maximum key that belongs in this subtree)
• Each node has a pointer to its right sibling
• A search that encounters a key > high key follows the sibling pointer
• Splits can be non-atomic because readers can "fix up" their path