Skip to main content

Module delete

Module delete 

Source
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_DEPTH or a node’s slot count.
  • Rule 5. validate_node runs on every encoded node.