Inserting and Splitting B-Tree Nodes

Insert: the easy case and the hard case

Inserting into a B-tree starts exactly like search: descend from the root, using each node's sorted keys to pick a child, until you reach a leaf. The easy case is when that leaf still has room — you insert the key into its sorted position and you're done, tree shape unchanged.

The hard case is what this lesson is really about: what happens when the leaf is already full?

Order and overflow

A B-tree of order M allows at most M-1 keys per node. If a node already holds M-1 keys and you insert one more, it temporarily holds M keys — an overflow. The fix is to split the node:

1. Insert the new key into the overfull node so it has M keys, sorted.
2. Find the median key (the middle element of those M keys).
3. Everything left of the median becomes the left half of the split; everything right becomes the right half.
4. The median key gets pushed up into the parent as a new separator key, with the left and right halves becoming its two new children.

For a leaf split, the median key is duplicated: it moves up to the parent and stays as the smallest key of the right half (this is the difference between a strict B-tree and a B+tree — for this exercise, follow whichever convention your solution's tests expect, but be consistent). For an internal node split, the median key is only pushed up, not kept in either half, since internal-node keys are pure separators.

Recursive propagation

Pushing a key into the parent can itself overflow the parent — if the parent already had M-1 keys, it now has M. So the split logic must be recursive: after splitting a node and inserting the median into the parent, check if the parent overflowed, and if so, split the parent too, propagating upward.

function insert(root, key):
    leaf = descend to the leaf where key belongs
    insert key into leaf, keeping it sorted
    node = leaf
    while node.keys.length >= M:
        median, left, right = split(node)
        if node is root:
            new_root = make_node(keys=[median], children=[left, right])
            root = new_root
            break
        parent = node.parent
        replace node in parent.children with [left, right]
        insert median into parent.keys at the right sorted position
        node = parent

Growing at the root

If the split propagates all the way up and the root itself overflows and splits, the tree grows one level taller: a brand new root is created holding just the median key, with the two halves of the old root as its two children. This is the only way a B-tree grows in height, and it's why B-trees stay so shallow — height only increases when the root splits, which happens rarely once the tree is reasonably full.

Walk through the example in the exercise with order 3 (max 2 keys per node):

INSERT 10 → [10]
INSERT 20 → [10,20]
INSERT 30 → overflow! split [10,20,30] at median 20
            → new root [20] with children [10] and [30]

Things to get right

• Median index for even vs. odd node sizes. With M-1 max keys, after inserting you have M keys — pick the middle index consistently (M/2 or M/2 - 1 depending on convention) and use it everywhere.
• Reparenting children. When an internal node splits, its child pointers must be divided between the left and right halves along with the keys — get the count of children (k+1 for k keys) right or you'll drop or duplicate a subtree.
• Finding the correct insertion index in the parent for the pushed-up median — it's another sorted-insert, same logic as inserting into a leaf.
• The root-split case is distinct code — every other split replaces a node's slot inside its parent, but the root has no parent, so it needs the "wrap in a new root" branch.

Get this right and you have a self-balancing tree that never needs explicit rebalancing on insert — the split-and-push mechanism keeps every leaf at the same depth automatically.