Skip to content

B+tree: implement merge-on-underflow for delete (deferred from Phase 01) #13

Description

@forkwright

Finding

crates/pinax/src/btree/mod.rs module doc (and mutate.rs's collapse_root_if_needed doc): delete never merges or rebalances an underflowing leaf/interior page. apply_result_to_interior's Replaced arm only ever repoints an existing child pointer — it never removes a separator key — so an ancestor's key count is monotonically non-decreasing across the tree's lifetime. A leaf/interior page is allowed to sit far under its natural fan-out after a delete-heavy workload; the tree stays correct (an empty leaf is a valid leaf, collapse_root_if_needed handles the one degenerate root shape that can still occur) but is not space-optimal.

Evidence

  • crates/pinax/src/btree/mod.rs::delete (was crates/pinax/src/btree.rs:817-857 pre-split): builds the replacement leaf via remove_cell_at alone, with no underflow check against free_space/a minimum-occupancy threshold.
  • crates/pinax/src/btree/mutate.rs::apply_result_to_interior: the NodeResult::Replaced arm calls interior_set_child_at/interior_set_rightmost only — no code path ever calls remove_cell_at on an interior page's own key/child pair.
  • crates/pinax/src/btree/mutate.rs::collapse_root_if_needed: the one defensive exception, collapsing a zero-key interior root to its sole child. Confirmed still unreached by any current delete path (collapse_root_if_needed_collapses_a_zero_key_interior_root builds the zero-key shape directly rather than through delete).

Why this matters

ROADMAP.md Phase 01's acceptance criteria (CRUD correctness, crash safety, checksums, buffer-pool eviction) do not require space-optimal trees under a delete-heavy workload, so this is a deliberate, documented phase boundary rather than a defect — but a delete-heavy production workload will grow the on-disk tree unboundedly relative to its logical content until this lands, and the module doc's own claim ("tracked as deliberate follow-up scope, not silently dropped") needs a real tracking artifact to back it, which is what this issue is.

Desired correction

Implement leaf and interior merge/rebalance on underflow: when a delete leaves a leaf or interior page below a minimum-occupancy threshold, either merge it with a sibling or redistribute entries, propagating the resulting separator-key removal up through apply_result_to_interior the same way a split propagates a new one up today. Add negative/boundary tests exercising sustained delete-heavy workloads that assert the on-disk page count stays bounded relative to live key count, not just that keys remain readable (the current delete_most_of_a_multi_level_tree_leaves_remaining_keys_readable test proves correctness but not compactness).

Done when: deleting a large fraction of keys from a multi-level tree measurably shrinks (or at least does not grow) the interior page count, apply_result_to_interior has a code path that removes a separator key, and a test proves it.

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions