Project: design a versioned warehouse index

Last updated: 3 Oct 202616 min read

project

A warehouse needs four read paths: reject shipment IDs that are definitely absent, show active device slots from a fixed ID range, scan bay keys in order, and answer daily count ranges against both current and earlier audit revisions. A fifth path reports the minimum delay in every three-reading window. Write an operation contract before choosing storage. A fast local structure does not replace the authoritative shipment index or the durable audit record.

Design the access paths

Put a Bloom filter in front of the exact shipment index, but query that index whenever the filter says possible. Keep active device IDs in a sparse set only if the bounded universe fits memory; document that swap deletion changes iteration order. For mutable ordered bay keys, compare a skip list with an actual page-oriented B+ index. The one-level leaf-split lesson is an invariant exercise, not a deployable database. Choose a persistent segment tree when auditors must compare historical range totals after point corrections. Use a monotonic deque for one-pass fixed-width delay windows.

Acceptance trace

Start with daily counts 47, 31, 26, and 58. The old [1, 4) total is 115. Replace index two with 29 and keep the old root; the new total is 118 while the old remains 115. Activate device slots 47, 61, and 52, then remove 61; membership for 61 is false even if its sparse cell has a stale index. Insert bay 58 between 52 and 61. A positive Bloom response still needs an exact lookup. For readings 47, 31, 26, 58, 19, and 42 with width three, report minima 26, 26, 19, and 19.

Old range version: 115
New range version: 118
Active slots after removal: 47, 52
Bay order around insertion: 52, 58, 61
Three-reading minima: 26, 26, 19, 19

Cost and failure review

State memory for the filter's bit capacity, the sparse set's full ID universe, skip-list links, each retained range version, and the window deque. Distinguish expected skip-list lookup from worst-case lookup, and distinguish a B+ page visit from Python list shifting. Specify how an authoritative write and its filter update become consistent, how audit roots are retained or discarded, and how ordered-index changes survive a process failure. A design passes only when its reported snapshot and exact record source agree with the operation contract.

Common Mistakes

Do not accept a Bloom positive as an exact hit.
Do not call an in-memory root a durable audit record.
Do not use a static sparse-set universe without sizing its memory.
Do not call the one-level page split a complete B+ index.

Connected lessons

data structures

projects