When a leaf split fills its parent, the parent splits too, and the split can cascade all the way to a new root. Today you complete insert so overflow at any level propagates upward, keeping every leaf at equal depth.
When splicing a separator overflows an internal node, split it and propagate upward, growing a new root if the old root splits.
The last piece of insert is symmetry: an internal node that overflows after
absorbing a child’s separator splits exactly like a leaf does in spirit - it
calls splitInternal, keeps its left half, and sends its median up to its parent
as a new separator. If that parent overflows too, the same thing happens one level
higher, and so on. The split cascades as far up as it needs to.
When the cascade reaches the root and the root splits, there is no parent - so, just like lesson 20, the tree grows a new root above it and gets one level taller. This is the complete growth story: leaves split, separators climb, and the tree only ever grows from the top, which is precisely why every leaf stays at the same depth. The tree is now a real, arbitrarily tall B+Tree that keeps itself balanced through any sequence of inserts.
// in insert(): after splicing the child's separator, if this internal// node now exceeds maxKeys, splitInternal it and return (promote,// newRightID, true) to the caller above.// in Put(): if the ROOT returned a split, build a new internal root// with [promote] and children [oldRoot, newRight] (same as lesson 20).func (t *Tree) Put(key, val uint64) { /* handle a root-level split */ }