When does an ordered map plus a separate hash index beat the ordered map alone for a booking service keyed by start time?

## The setup A room-booking service keys bookings by start timestamp. The ordered map is not optional: the product needs *the nearest free slot before or after a requested time* (nearest-key queries) and *everything booked between two timestamps* (a range walk). Those requirements alone decide the structure. The question is whether to add a hash index over the same keys because the hot path also does plenty of exact-key lookups — "fetch the booking that starts at exactly this instant". This is a **dual-index** decision, and it is the shape most real ordering-versus-hashing arguments actually take once ordering has been established as a requirement. ## What the second index actually buys Only a constant factor on one query shape. The ordered map is not *missing* exact lookup; it performs it in `O(log n)`. So the win is `log n` comparisons replaced by one hash plus a probe. Put numbers on it. At a million bookings, `log2(n)` is about 20. If keys are fixed-width timestamps, each comparison is a register operation, and the descent's real cost is the pointer chasing — call it a few hundred nanoseconds of mostly cache misses. Against a request that already spent a network round trip and a serialization pass, that is invisible. The measurement to demand is what share of the request budget exact-key lookup occupies today. If the honest answer is "under one percent", the second index is optimizing a rounding error. The case flips when comparisons are expensive. Keys that are long composite strings — a tenant identifier concatenated with a room code and an ISO timestamp — turn each of those 20 comparisons into a memory-walking string compare, and hashing the key once genuinely wins. That is the specific circumstance that justifies the split, and it is worth stating as the trigger condition rather than as a general preference. ## What it costs **Memory, multiplied by the fleet.** A second index is another entry per booking: its own node or slot, its own key reference, its own overhead. On a single instance that may be a rounding error; on a fleet with a per-instance memory ceiling it is the constraint that decides how many instances you need, and it scales with the same 10x growth everything else does. Memory ceilings are the first thing to break at 10x here, before any latency does. **Consistency, which is a correctness cost, not a performance one.** Every mutation now has two obligations. Insert, cancel, reschedule, TTL expiry, bulk import, the admin override path, the compensating action in a failed transaction — each must update both structures. The failure mode is asymmetric and nasty: the hash index retains an entry the ordered map no longer has, and a lookup returns a cancelled booking. That is not a slow response; it is a wrong one, and it surfaces long after the deploy that introduced it. At 10x traffic this stops being a latency question and becomes an incident class. **Cognitive and organisational cost.** Two structures is an invariant the team must know about, hold in review, and preserve under time pressure. Every new mutation path is a new opportunity to update one and forget the other, including paths written by people who joined after the decision. That invariant is a permanent tax with no expiry date. ## How to decide, and how to say so The order I would argue it: 1. **State the budget.** What latency number is the service contracted to? If none exists, the split cannot be justified, because there is nothing it is failing. 2. **Measure.** Profile the request path and find exact-key lookup's actual share. Cheap experiments first: pre-size the container, check whether comparison cost or cache misses dominate. 3. **Try the cheaper fixes.** A shorter or fixed-width key form makes comparisons cheap and can close the gap without a second structure at all. Caching the last-resolved entry helps if lookups are temporally clustered, which in a booking service they often are. 4. **If you still split, encapsulate.** Both structures go behind a single owning type with mutation methods that update both; no caller ever touches one directly. That converts "an invariant everyone must remember" into "an invariant enforced in one file", which is the only version of this design that survives team turnover. 5. **Test the invariant.** A property test that applies a random sequence of mutations and asserts the two views agree is the artefact that makes the design maintainable. Without it, the split is a bet on everyone being careful. ## The judgment being tested A candidate who answers "yes, add the hash index, exact lookups become O(1)" has optimized asymptotics with no budget, no measurement, and no account of the consistency cost. A candidate who answers "never denormalize" is equally unhelpful — the composite-key case is real, and refusing to consider it is dogma. The defensible answer names the trigger condition (measured budget miss, dominated by comparison cost), names the price (memory across the fleet, dual-write correctness, a permanent maintenance invariant), and names the containment (one owning type, one property test). That is the same reasoning that applies to every derived index anywhere: a second view of the same data is a correctness liability bought with a performance gain, and the exchange rate has to be quoted before the trade is made.