B-Tree Insert & Node Splitting

Insertion is where B-trees get interesting. When a node overflows, it splits — and this split can cascade up to the root, growing the tree by one level.

Insert Algorithm (Simplified)

1. Search for the correct leaf node (using the search algorithm)
2. Insert the key into the leaf in sorted position
3. If the leaf overflows (has M keys), split it

What Happens During a Split?

When a node has M keys (one too many for order M):

Node [10, 20, 30] overflows (order 3, max 2 keys)

Step 1: Find the median → 20
Step 2: Split into two nodes → [10] and [30]
Step 3: Push median (20) up to the parent

The median key is promoted to the parent node, and the overfull node becomes two half-full nodes.

Cascading Splits

If the parent also overflows after receiving the promoted key, it splits too. This can cascade all the way to the root:

Before inserting 5 (order 3):
        [20]
       /    \
   [10]    [30,40]

Insert 5 into [10]: [5,10] → fits (max 2 keys) ✓

Before inserting 35:
        [20]
       /    \
   [5,10]  [30,40]

Insert 35 into [30,40]: [30,35,40] → overflow!
Split: median=35, left=[30], right=[40]
Push 35 to parent: [20,35] → fits ✓

Result:
        [20,35]
       /   |   \
   [5,10] [30] [40]

Root Splits

When the root splits, a new root is created with a single key. This is the only way a B-tree grows taller:

Root [10,20] → insert 30 → [10,20,30] → overflow!
Split: median=20, left=[10], right=[30]
New root: [20] with children [10] and [30]

    [20]        ← new root (tree grew one level)
   /    \
 [10]  [30]

Why B-Trees Stay Balanced

Every leaf is always at the same depth because:

1. New keys are always inserted at leaves (bottom)
2. Splits push keys up, never down
3. The tree only grows taller at the root (top)

This guarantees O(log n) height.

Implementation Tips

A clean approach is proactive splitting (top-down): split full nodes on the way down during search, before they overflow. This avoids the need for recursive split propagation:

function insert(node, key):
    if node is full:
        split node and push median to parent
    find correct child
    insert into child

How SQLite Handles Splits

SQLite's balance() function in btree.c handles splits. It actually uses a more sophisticated approach — it considers adjacent siblings and tries to redistribute keys before splitting, reducing tree growth.

Your Task

Implement B-tree insert with node splitting. Test with order 3 to see splits happen frequently.