Page splits and rebalancing: preserve search boundaries

Consider a teaching B+ leaf holding four entries at capacity. Inserting a fifth requires either reclaiming eligible obsolete space, changing representation, or creating another page. A simple split sorts all five entries and divides them into two valid groups. The parent receives a separator that routes searches to the new right page. In this lesson, the separator is the smallest right-page key and equality routes right. Other formats may choose a different fence-key convention, which must be used consistently by lookup and range traversal.

Separators in a B+ style tree are routing information; copying one into the parent does not remove the corresponding record from its leaf. With duplicates, a complete implementation needs rules that route and scan every matching entry, often using additional ordering components or boundary semantics. Sibling links and fence keys must agree with the redistributed ranges. A reader arriving during structural change cannot be allowed to conclude that a moved entry vanished merely because it followed a parent pointer created before the split.

The new child reference consumes parent space. If that parent is full, it may split and require another separator in its own parent. This can propagate through several levels, but most leaf splits do not imply immediate root growth. Only an overflowing root requires creating a new root level under the teaching algorithm. Counting a split as a fixed one-page write therefore misses both the common local case and the rarer multi-level case. Recovery logging and sibling changes can add work beyond the new page itself.

Split policy depends on the expected workload and byte layout. A roughly balanced split can provide headroom on both sides for random insertions. An implementation may choose a different distribution for an append-heavy edge. Fill factor is typically a construction or maintenance policy, not a permanent guarantee that pages remain at that exact percentage. A lower initial fill spends space to leave insertion room; it does not eliminate all later splits. Evaluate the resulting page count and future write behavior together rather than optimizing one number.

Classical trees may redistribute or merge underfull siblings to maintain a stated minimum occupancy, with special handling for the root. Production MVCC indexes may defer removal until old versions are no longer needed and may use page deletion rules that differ from textbook immediate merging. A logically deleted row can retain index entries while snapshots still need them. Reclaiming obsolete versions can avoid a split, but deleting an entry before its visibility lifetime ends is a correctness error rather than useful space recovery.

Crash recovery must make every reachable state interpretable. A structural change can involve the original leaf, a new sibling, neighboring links, and a parent; these changes require the engine's prescribed logging and publication protocol. The queue lab isolates maintenance capacity instead. Reset, set λ=4 and μ=3, predict backlog grows by one work unit per second, then Play or Step. Reset again, set λ=2 and μ=3, predict four initial work units drain in four seconds, then Play or Step. This constant-rate model does not execute splits, replay a log, or verify a tree invariant.