The Runtime Theory

B-Tree Insertion: From Leaf Insert to Root Split

Watch a key enter a B-tree: descend to the leaf, insert, and when a node overflows, watch it split and propagate upward until the tree grows a new level.

The Runtime Theory Team08 stages

trace / request.md

DESCEND FROMTHE ROOTFIND THELEAF SLOTKEY IS WRITTENIN PLACECHECK THEFILL LIMITLEAF SPLITSIN TWOSPLIT WALKSUPWARDROOT SPLITS,TREE GROWSINVARIANTSHOLD AGAIN

readyStarting at the root, the insert key is compared at each internal node, and the child pointer that brackets the key is followed. Each level is one comparison against the node's keys.

B-trees keep their balance by refusing to let any node overflow. This diagram shows insertion as a two-phase operation: a descent and a cleanup. The descent is a sequence of comparisons — at every internal node the database picks the child whose key range brackets the new key, and it always ends at a leaf. The cleanup is where the structure is preserved: an overflowing node splits in half, promoting its middle key to the parent, and the promotion can cascade all the way to the root. A root split is the only time the tree grows, and it adds exactly one level, so every leaf stays at identical depth.

That uniform depth is the entire reason databases use B-trees: lookup, insert, and delete are all O(log n) with the log based on the node's fanout, and the tree never needs the rebalancing rotations that avl-style structures require. Each stage here is a page-sized unit of work, which is exactly how the database thinks about it — one page at a time.