Project: release a warehouse plan after indexed mutations

Last updated: 5 Oct 202617 min read

project

A warehouse release deletes retired bay IDs, changes a delayed dispatch job's priority, removes old owner records, and orders dependent work. Each structure answers a different question. The B+ index supports ordered bay scans; an indexed heap selects the next priority; an open-addressed directory resolves bay ownership; a dependency graph prevents shipment before prerequisites. Write a test plan that checks their separate invariants after each mutation. Then define the state boundary visible to readers. Correct individual operations do not make a release atomic across four indexes.

Mutation contract

Start with bay IDs 19, 26, 31, 47, 52, 58, 61, 67, 73, and 83. Retire the first six. The remaining B+ leaf chain must scan 61, 67, 73, 83, and every nonroot page must meet its minimum occupancy. Queue J-47 at priority 9, J-52 at 6, J-61 at 12, and J-83 at 7. Decrease J-61 to 3; its removal must precede J-52. In the owner directory, 47, 58, and 69 collide under eleven slots. Removing 47 must leave both later records discoverable. Insert 80 after the removal and check it separately.

Dependency contract

Stock precedes reserve; reserve precedes pick and label; pick precedes pack; pack and label precede ship. Accept any complete order respecting those edges. Reject an added edge from ship back to stock as a cycle. Record whether the release publishes all new index roots and queue state together, or whether readers may see an intermediate state. If the system persists its records, specify the log or transaction boundary and what recovery does after a process stops between two index writes. The in-memory examples here do not supply those facilities.

Acceptance trace

Bay scan: 61, 67, 73, 83
First dispatch: J-61 at priority 3
Owner 58: present after deleting 47
Owner 80: present after insertion
Ship: after pack and label
Added ship-to-stock edge: cycle rejected

Cost and ownership review

State page capacity when assessing B+ occupancy. Count an O(k) lower bound for returning k scanned bays, even if finding the first leaf is fast. Indexed-heap priority changes are expected O(log n) with a working position map. Linear probing is expected constant time only under a suitable key distribution and controlled load; a collision run can force O(n) probing. Topological ordering scans O(V + E) tasks and edges. These costs describe in-memory algorithms. They do not include disk page writes, retries, process crashes, or coordination among concurrent writers. Those require separate acceptance tests and a documented owner of the committed state.

Common Mistakes

Do not verify only the final B+ scan while leaving stale internal separators.
Do not change a job's priority without repairing the heap and its position map.
Do not turn a tombstone into an empty slot before the collision chain is rebuilt.
Do not return a partial task order as success when a cycle remains.
Do not call four separate writes one atomic release without a publication rule.

Connected lessons

data structures

projects