B-Tree Insert: Overflow and Split

After this lesson BTREE INSERT keeps the tree balanced by itself. A new key goes into a leaf; when a node ends up with more keys than it may hold, it splits in two and sends one key up. No rebalancing pass is ever needed, and the height grows only when the root splits.

The easy case and the hard case

Inserting starts like a search: descend to the leaf where the key belongs. If the key is already anywhere on the path, nothing changes and the answer is DUPLICATE (keys are unique, and a key in an internal node counts). Otherwise insert it into the leaf at its sorted position. If the leaf still has at most m-1 keys, you are done.

If the leaf now holds m keys, it has overflowed.

Splitting a node

Take the node's m keys in order, and let mid = m / 2 (rounded down). Then:

1. the key at position mid is the median: it moves up into the parent
2. the keys before it stay in this node (they form the left half)
3. the keys after it move to a new right sibling
4. an internal node's children are divided the same way: its first mid + 1 children stay, the rest go with the new sibling

The parent inserts the median at the position where the descent came down, and the new sibling becomes the child right after the old node. The parent may overflow in turn, so the split propagates upward.

order 3 (at most 2 keys), insert 10, 20, 30

[10]                    [10,20]                 [10,20,30]  overflow: mid = 1
                                                median 20 moves up
                                                           [20]
                                                          /    \
                                                       [10]    [30]

If the split reaches the root, there is no parent to receive the median. The tree creates a new root holding just that key, with the old root and its new sibling as children. This is the only way a B-tree gets taller, and every leaf moves down one level together, which is why all leaves stay at the same depth.

Worked example: inserting 1 to 5, order 3

insert 1,2     [1,2]
insert 3       [1,2,3] overflow, median 2 up        [2] / [1] [3]
insert 4       goes right: [3,4]                    [2] / [1] [3,4]
insert 5       [3,4,5] overflow, median 4 up        [2,4] / [1] [3] [5]

The root [2] received the median 4 and now has two keys and three children. Inserting 6 and 7 would overflow the root, split it around its median 4, and create a new root [4] over [2] and [6]: the tree grows a level.

Which index is the median

With m keys after the insert, the median is at index m / 2 rounded down: index 1 for m = 3, index 2 for m = 4 and m = 5. For an even m the left half is one key larger than the right (m = 4: two keys stay, one moves). The choice is arbitrary but the tests are exact, so use this one. Both halves respect the minimum of (m-1)/2 keys: for m = 4 the minimum is 1.

Output

BTREE INSERT <key> prints OK or DUPLICATE. Errors: ERR no tree, ERR usage: BTREE INSERT <key> and ERR bad number: <text>. Inspect results with PRINT, CHECK, STATS and RANGE from earlier lessons; after any sequence of inserts CHECK must say VALID.

Common mistakes

• Dropping children in an internal split. k keys need k+1 children on each side; moving the keys and forgetting the child pointers corrupts whole subtrees.
• Splitting before the overflow (a pre-emptive split on the way down) produces different shapes than this lesson expects.
• Duplicating the median in both halves (that is a B+tree leaf split).
• Forgetting the new root. Without it the last insert of a growing tree loses a key.

Your exercise

The starter has everything except the two functions that change the tree. You write ins (recursive, reporting a split to its caller) and insert_key (handles the root). The mistake to avoid: leaving the new sibling without its share of the children.