db-10 step 02 — Insert and delete (split, borrow, merge)

Goal

Implement mutation: insert(k, v) and delete(k) -> bool. Both operations must preserve the height invariant — every leaf at the same depth, every node within [MIN_KEYS, MAX_KEYS] (except the root).

Tasks

  1. Insert.
    • If root.keys.len() == MAX_KEYS, grow up: wrap the old root in a new internal root with one child, then split_child(new_root, 0). This is the only place height ever increases.
    • Then insert_nonfull(root, k, v).
  2. insert_nonfull(node, k, v).
    • If node.is_leaf: splice the entry into the sorted slot. If the key already exists, overwrite the value in place.
    • Else: find i such that key <= node.keys[i].0 (the child whose range covers the key). If children[i] is full, split first (pre-emptive split), then if key > node.keys[i].0 advance i. Recurse into children[i].
  3. split_child(parent, i). Precondition: parent.children[i].keys.len() == MAX_KEYS == 3. Effect:
    • Promote the middle key (index 1) into parent.keys[i].
    • Move the right half (key 2 plus children 2..=3) into a new sibling at parent.children[i + 1].
    • The left half (key 0 plus children 0..=1) remains in parent.children[i].
  4. Delete. Recursive delete_from(node, k) -> bool that maintains the invariant the node we're descending into has ≥ T keys. Three cases at a leaf or internal node hit:
    • Key in this leaf → splice out, return true.
    • Key in this internal node → replace with in-order predecessor or successor (drawn from whichever neighbor child has ≥ T keys), then recursively delete that pred/succ.
    • Key not in this subtree (descending into children[i]):
      • If children[i].keys.len() < T, borrow from children[i-1] or children[i+1] if one of them has > MIN_KEYS. Prefer left. Otherwise merge children[i] with its left or right sibling (prefer right if it exists, else left), pulling the separating key from the parent.
      • Recurse into children[i] (which is now safe).
  5. After delete_from returns, if root became a keyless internal node, collapse: root = root.children.remove(0). This is the only place height ever decreases.

Acceptance

Inline unit tests:

  • insert_then_get_roundtrip — insert 50 keys, all of them retrievable.
  • insert_overwrites — inserting ("k", "v1") then ("k", "v2") yields get("k") == "v2" and len() == 1.
  • delete_existing_returns_true — insert "k", delete "k" returns true, get("k") returns None.
  • delete_missing_returns_false — BTree::new().delete(b"k") is false.
  • inserts_grow_tree — insert enough keys to force at least one grow-up; check len() matches insertions.
  • deletes_shrink_tree — insert N keys then delete them all; len() goes to 0, tree is still well-formed (collapsed root).

All six green in Rust, Go, and C++.

Discussion prompts

  • Why is pre-emptive split preferred over "descend, recurse, split on the way back"?
  • For deletion, why must we ensure children[i].keys.len() >= T before descending, not after?
  • What's the tie-break rule when both siblings have spare keys — borrow from left or right? What's the cost of getting it wrong?
  • How would copy-on-write change split_child and delete_from?