Internal nodes fill up too, and they split differently from leaves - the median key moves up and is removed, rather than being copied. Today you write that split as a pure function, pinning the even and odd cases.
Split an overflowing internal node, promoting its median key upward and dividing keys and children between the two halves.
An internal split differs from a leaf split in one decisive way: the median key is
promoted and removed, not copied. A leaf must keep every key because leaves hold
the data; an internal node’s keys are only signposts, so the median can leave to
become the parent’s new separator, and the children on either side of it go with
the half they belong to. That is why the child arrays divide at mid + 1: the
promoted key’s two neighboring subtrees end up split across the two halves.
The counting has to be exact. A node with k keys has k + 1 children; after
promoting keys[mid], the left keeps mid keys and mid + 1 children, the right
takes the rest, and the promoted key accounts for the one key that vanished from the
totals. Pinning both an even and an odd node keeps that arithmetic honest - off by
one on the child split and a whole subtree goes missing.
// mid = len(keys)/2. promote = keys[mid] and is NOT kept in either half.// left keys[:mid], children[:mid+1]// right keys[mid+1:], children[mid+1:]func splitInternal(n *InternalNode) (left *InternalNode, promote uint64, right *InternalNode) {}