Project: test mutation invariants across four indexes

Last updated: 3 Oct 202618 min read

project

A parts service has four read contracts: find a bay ID, list bay IDs in order, reject overlapping maintenance windows, and resolve a complete part code. Its writes arrive in batches that can split index pages or rotate trees. Write a small acceptance test around the linked lessons. The test is the deliverable: each assertion should name the invariant it protects and should compare against an independent simple model. Keep the model small enough to inspect. A sorted set, a list of windows, and a plain set of part codes are enough for this exercise.

Operation contract

Insert bay IDs 47, 19, 83, 26, 61, 52, 58, 31, 67, and 73 into a B+ index capped at three keys per page. Require an ordered leaf scan and point lookup after every insertion, then check that all leaves have the same depth and every internal separator equals the smallest key in its right child. Insert the same IDs into the red-black index. Check sorted order, a black root, no right-leaning red links, and equal black height after each mutation. Duplicate inserts must leave both indexes unchanged.

Interval and key lifecycle

Insert half-open windows [47, 61), [19, 26), [52, 58), [83, 91), and [31, 42) into the AVL interval index. Query [25, 32): some stored window must overlap. Query [62, 80): none may overlap. Recompute height and subtree maximum from children after every rotation; a correct returned overlap is insufficient if the metadata is stale. Insert dock47, dock52, doll61, and dock into a compressed trie. Delete dock and confirm dock47 survives; delete dock52 and confirm doll61 survives. Removing dock52 again must report false. A prefix path alone does not prove exact membership.

Acceptance trace

Bay scan: 19, 26, 31, 47, 52, 58, 61, 67, 73, 83
Bay 58: found; bay 49: missing
Window [25, 32): overlap; [62, 80): none
Delete dock: true; dock47: present
Delete dock52 again: false; doll61: present

Cost and boundary review

For n keys, balanced ordered operations take O(log n) in memory, subject to page width and list shifts in the B+ model. An ordered scan returning k keys costs at least O(k), even when reaching its first leaf is logarithmic. The AVL overlap query finds one result in O(log n); reporting all matches needs output work. Trie mutation depends on key length and branch search. A persistent segment tree can preserve older aggregate versions, but it does not make a B+ page write durable. State where a transaction commits, how readers see a consistent version, and what recovery does if a process stops after changing one index but before changing the others. In-memory property tests do not answer those storage questions.

Common Mistakes

Do not compare two implementations that share the same faulty helper; use a smaller independent oracle.
Do not accept a correct leaf scan while internal separators route point lookups to the wrong page.
Do not ignore metadata after AVL rotations because one overlap query happened to pass.
Do not clear a compressed-trie branch used by another stored key.
Do not treat separate successful in-memory mutations as an atomic durable update.

Connected lessons

data structures

projects