Expand description
B+tree delete path with merge / borrow rebalancing.
Mirrors insert.rs: every node touched is rewritten to a fresh
page; pre-delete pages enter the freelist only after the new
root is staged. The caller still owns the commit boundary —
BTree::delete does NOT call Pager::commit.
§Underflow policy
A non-root node is “underflowing” when its post-delete occupied
byte count falls below MIN_OCCUPIED_BYTES = PAYLOAD_BYTES / 2.
At underflow:
- If a sibling is rich enough that moving one slot from it keeps both halves above the threshold, borrow.
- Otherwise merge with the sibling. The two halves combine into a single page; the separator pivot in the parent is removed (leaf merge) or absorbed (internal merge).
Root collapse: an internal root with exactly one child (zero pivots) is replaced by its child. A leaf root with zero slots is allowed and is the bootstrap “empty tree” state.
§Power-of-ten posture
- Rule 1. Iterative descent + iterative bubble-up; no recursion.
- Rule 2. Every loop is bounded by
MAX_BTREE_DEPTHor a node’s slot count. - Rule 5.
validate_noderuns on every encoded node.