Insert Algorithm

Every index entry you see in a database arrived there through B-tree insertion. When you execute INSERT INTO orders VALUES (...), the database must update every index on that table—each update invoking the B-tree insertion algorithm to place the new key in exactly the right location while preserving all structural invariants.

B-tree insertion is more complex than search because it must maintain balance. Unlike a naive binary search tree that can degenerate into a linked list with skewed insertions, a B-tree guarantees logarithmic height regardless of insertion order. This guarantee comes from a beautiful mechanism: node splitting.

B-tree insertion follows a two-phase approach:

1. Search Phase: Navigate from root to the appropriate leaf node where the key should reside
2. Insert Phase: Add the key to the leaf, splitting nodes as necessary to maintain size invariants

The Core Invariants Insertion Must Preserve:

• Ordering: Keys remain sorted within each node and across the tree
• Balance: All leaves remain at the same depth
• Occupancy: Each non-root node contains between ⌈t/2⌉-1 and t-1 keys (for minimum degree t)
• Root Occupancy: The root contains between 1 and t-1 keys

The challenge is that inserting a key into a full node would violate the maximum occupancy invariant. The solution is splitting: dividing an overfull node into two nodes of acceptable size.

High-Level Algorithm:

BTREE-INSERT(tree, key, value):
    // Case 1: Root is full - split it first (tree grows taller)
    IF tree.root.numKeys = 2t - 1:
        newRoot ← AllocateNode()
        newRoot.isLeaf ← FALSE
        newRoot.children[0] ← tree.root
        SPLIT-CHILD(newRoot, 0)  // Split old root
        tree.root ← newRoot
    
    // Now root is guaranteed to have space
    INSERT-NONFULL(tree.root, key, value)

The elegantly simple structure handles the special case where the root is full before descending, ensuring we never need to propagate splits upward after completing insertion—a technique called proactive splitting or preemptive splitting.

The core insertion logic handles two cases: inserting into a leaf (base case) and recursively descending through internal nodes.

Algorithm: INSERT-NONFULL

INSERT-NONFULL(node, key, value):
    i ← node.numKeys - 1
    
    IF node.isLeaf:
        // Case A: Insert into leaf node
        // Shift keys right to make room
        WHILE i >= 0 AND key < node.keys[i]:
            node.keys[i+1] ← node.keys[i]
            node.values[i+1] ← node.values[i]
            i ← i - 1
        
        // Insert new key at position i+1
        node.keys[i+1] ← key
        node.values[i+1] ← value
        node.numKeys ← node.numKeys + 1
        DISK-WRITE(node)
    
    ELSE:
        // Case B: Internal node - find correct child
        WHILE i >= 0 AND key < node.keys[i]:
            i ← i - 1
        i ← i + 1  // i is now the index of child to descend into
        
        DISK-READ(node.children[i])
        
        // Proactive splitting: if child is full, split it now
        IF node.children[i].numKeys = 2t - 1:
            SPLIT-CHILD(node, i)
            // After split, determine which half to insert into
            IF key > node.keys[i]:
                i ← i + 1
        
        INSERT-NONFULL(node.children[i], key, value)

Let's trace through each component:

Node splitting is the heart of B-tree balancing. When a node becomes full (has 2t-1 keys), we cannot insert another key without violating the size invariant. Splitting divides the node into two nodes, each with acceptable key counts.

The SPLIT-CHILD Algorithm:

SPLIT-CHILD(parent, i):
    // parent.children[i] is full (has 2t-1 keys)
    fullChild ← parent.children[i]
    newChild ← AllocateNode()
    newChild.isLeaf ← fullChild.isLeaf
    
    // New child gets the upper half of keys (t-1 keys)
    newChild.numKeys ← t - 1
    FOR j ← 0 TO t - 2:
        newChild.keys[j] ← fullChild.keys[t + j]
        newChild.values[j] ← fullChild.values[t + j]  // For leaves
    
    // If not a leaf, also copy child pointers
    IF NOT fullChild.isLeaf:
        FOR j ← 0 TO t - 1:
            newChild.children[j] ← fullChild.children[t + j]
    
    // Full child keeps the lower half (t-1 keys)
    fullChild.numKeys ← t - 1
    
    // Make room in parent for new child pointer
    FOR j ← parent.numKeys DOWNTO i + 1:
        parent.children[j + 1] ← parent.children[j]
    parent.children[i + 1] ← newChild
    
    // Make room in parent for median key
    FOR j ← parent.numKeys - 1 DOWNTO i:
        parent.keys[j + 1] ← parent.keys[j]
        parent.values[j + 1] ← parent.values[j]
    
    // Median key moves up to parent
    parent.keys[i] ← fullChild.keys[t - 1]  // The median
    parent.numKeys ← parent.numKeys + 1
    
    // Write all modified nodes to disk
    DISK-WRITE(fullChild)
    DISK-WRITE(newChild)
    DISK-WRITE(parent)

Visual Example: Splitting a Node with t=3

Before split (node with 5 keys is full):

Parent: [... | 30 | ...]
              |
        [10, 20, 25, 28, 29]  ← Full child

After split (median 25 moves up):

Parent: [... | 25 | 30 | ...]
              |    |
       [10, 20]  [28, 29]  ← Two half-full children

Key observations:

• The full child keeps keys less than the median (indices 0 to t-2)
• The new child gets keys greater than the median (indices t to 2t-2)
• The median key (index t-1) moves to the parent
• Both resulting nodes have exactly t-1 keys—the minimum allowed

Let's trace through a series of insertions into a B-tree with minimum degree t=2 (each node holds 1-3 keys). Starting from an empty tree, we'll insert: 10, 20, 30, 40, 25, 15, 35.

Insert 10 (empty tree):

Create root as leaf: [10]

Insert 20:

Insert into root (has space): [10, 20]

Insert 30:

Insert into root (has space): [10, 20, 30]  ← Root now full

Insert 40: Root is full! Must split before inserting:

Step 1: Create new root
Step 2: Split old root at median (20)
Step 3: Tree structure:
           [20]
          /    
      [10]    [30]

Step 4: Insert 40 into right leaf
           [20]
          /    
      [10]    [30, 40]

Insert 25: Descend: 25 > 20, go right → [30, 40] has space

           [20]
          /    
      [10]    [25, 30, 40]  ← Right leaf now full

Insert 15: Descend: 15 < 20, go left → [10] has space

           [20]
          /    
   [10, 15]    [25, 30, 40]

Insert 35: Descend: 35 > 20, must go right. But wait—right child [25, 30, 40] is full!

Proactive split at [25, 30, 40]:
- Median 30 moves to root
- Left: [25], Right: [40]

Tree after split:
           [20, 30]
          /    |    
   [10, 15]  [25]  [40]

Now insert 35: goes into right child (35 > 30)
           [20, 30]
          /    |    
   [10, 15]  [25]  [35, 40]

B+-tree insertion differs from B-tree insertion in several important ways due to the structural difference: data resides only in leaves, and internal nodes contain separator keys only.

Key Differences:

1. Insertion always targets a leaf: We always descend to a leaf node before inserting, regardless of whether we encounter the key as a separator in internal nodes.

2. Separator key handling during splits: When a leaf splits, we must copy the median key up to the parent (it remains in the leaf). When an internal node splits, we promote the median key (it moves, not copies).

3. Leaf linking: After a leaf split, we must update sibling pointers to maintain the linked list structure.

Understanding insertion complexity requires analyzing both the common case (no split) and worst case (cascading splits to root).

Time Complexity:

• Search phase: O(t · log_t n) comparisons

  • Traverse O(log_t n) levels
  • At each level, O(t) comparisons (or O(log t) with binary search)

• Insert phase (no split): O(t)

  • Shift O(t) keys within the leaf to make room

• Insert phase (with splits): O(t · log_t n) in worst case

  • Each split affects O(t) keys
  • At most O(log_t n) splits (one per level)

Amortized Analysis:

While a single insertion can trigger O(log_t n) splits, this is rare. Using aggregate analysis:

• A split creates two nodes from one, each half full
• Before another split can occur on these nodes, at least (t-1) insertions must target them
• Total splits across n insertions: O(n/t)
• Amortized cost per insertion: O(1) splits

Space Complexity:

• Auxiliary space during insertion: O(log_t n) for recursion stack
• Space per new key: O(1) additional space in existing node
• Space increase from splits: One new node per split, amortized O(1/t) per insertion

Disk I/O Analysis:

For a B-tree with t=100 containing 1 billion keys:

• Height: ~5 levels
• Non-split insertion: 5 reads + 1 write = 6 disk I/Os
• Split at leaf: 5 reads + 3 writes = 8 disk I/Os
• Cascade to root (extremely rare): 5 reads + 15 writes = 20 disk I/Os

With upper levels cached in memory, typical insertion requires 1-2 disk reads and 1-3 writes.

There are two fundamental approaches to handling full nodes during insertion:

Proactive (Preemptive) Splitting:

Split full nodes on the way down, before they're needed:

descend(node, key):
    FOR each child on path:
        IF child is full:
            split child now
        descend into appropriate child
    insert into leaf (guaranteed non-full)

Advantages:

• Single pass—never backtrack
• Simpler implementation—no need to track ancestors
• Works well with latch coupling (can release parent latch immediately)

Disadvantages:

• May split nodes unnecessarily (if actual insertion goes elsewhere)
• Slightly lower average space utilization

Reactive Splitting:

Descend to leaf, insert, then propagate splits upward:

descend(node, key):
    path ← []  // Stack of ancestors
    WHILE not at leaf:
        path.push(node)
        descend to appropriate child
    
    insert into leaf
    IF leaf overflows:
        propagate splits up using path stack

Advantages:

• Only splits when actually necessary
• Better space utilization

Disadvantages:

• Requires ancestor tracking (stack)
• Must hold latches on all ancestors during propagation (concurrency issues)
• Two-pass structure more complex