When does a skip list beat a balanced search tree for a concurrently updated, price-ordered catalog index?
answer
- Ask what the writers do, not the readers
- How far can a repair propagate?
- Local pointer rewiring versus restructuring
- Expected bounds versus a contractual ceiling
- Geometric sum gives pointers per key
basics
~20 sA skip list wins when many threads mutate the index: its updates rewire a few neighbouring pointers with no rebalancing, so fine-grained locking and lock-free variants stay tractable, and its bottom level scans price ranges in order. A balanced tree wins when worst-case bounds or memory are contractual.
solid answer
~50 sFor a warehouse catalog index keyed by price, both structures give you ordered iteration and logarithmic lookup, so the decision turns on how updates behave under concurrency. A skip-list insert or delete touches only the new node and a handful of recorded predecessors — there is no rebalancing that can propagate toward a root — which makes per-node locking and compare-and-swap designs practical, and keeps the code small enough to review. Range scans like "SKUs priced between 20 and 50" run straight along the bottom level. What you give up: bounds are expected rather than worst-case, so a hard per-operation latency ceiling is uncomfortable; you pay roughly two forward pointers per key at p = 1/2; and pointer-chasing across scattered towers has worse cache behaviour than a wide-fanout node layout. If the index is read-mostly, rebuilt in bulk, or memory-constrained, the balanced tree — or a sorted array — is the better call.
go deeper
Know that both a skip list and a balanced search tree give ordered iteration with logarithmic lookup, and that hash-based storage cannot answer range queries at all.
Be ready to contrast how each structure absorbs an insertion: local pointer splicing with no repair versus restoring a structural invariant along the path toward the root.
Argue the choice from the workload — writer concurrency, range-scan shape, memory per key at real scale — and name what you give up, especially the expected rather than worst-case bound.
Own the constraint framing: whether an expected bound is acceptable against a latency commitment, whether the fleet can afford the pointer overhead, and whether the team can maintain a lock-free variant it did not write.
## Framing the decision The requirement is a price-ordered index over a warehouse catalog: point lookups by price, range scans ("everything between 20 and 50"), and continuous mid-range insertions and price updates from many concurrent writers as suppliers push changes. Hash-based storage is out immediately — it answers point lookups but has no notion of order, so range scans would mean sorting the whole key set. That leaves ordered structures, and among them the interesting comparison is skip list versus balanced search tree. Both deliver: logarithmic point lookup, ordered iteration, predecessor/successor queries, and cheap positional insertion once the position is found. Choosing between them means looking past the asymptotics they share. ## Where the skip list wins **Locality of mutation.** A skip-list insert splices the new node into the levels its coin flips gave it, touching only its recorded predecessors. A delete unlinks it the same way. The set of modified pointers is small, bounded in expectation, and adjacent to the key. A balanced tree, by contrast, must restore its structural invariant after a modification, and that repair can propagate up the path toward the root. In a single-threaded program that is merely more code; under concurrency it is the whole problem, because a repair that may touch the root means a writer may need to exclude everyone. **Concurrency follows from that.** Because a skip-list writer's footprint is local and known before it starts, you can lock exactly the predecessor nodes involved, or go lock-free: link the new node bottom-level-first with compare-and-swap so that a concurrent reader that has descended to level 0 always sees a consistent list, and handle deletion by logically marking a node before unlinking it. Readers can then run without any lock at all, because level 0 always holds the truth. Building the equivalent on a rotating tree is markedly harder — that difficulty, not raw single-thread speed, is the main reason skip lists get chosen in concurrent systems. **Range scans.** Level 0 is a plain sorted chain, so after locating the low end of a price band you walk forward at O(1) per result. A tree can do ordered traversal too, but it requires either explicit successor computation or threading, and the walk hops around the structure rather than along one line. **Reviewability.** The insert path has no case analysis over structural configurations. Small, boring code that a team can actually maintain is a legitimate engineering argument, and it is the one to make out loud at senior level. ## Where it loses **No worst-case guarantee.** A balanced tree bounds every operation's height; a skip list bounds it in expectation, with strong concentration but no ceiling. If the catalog service publishes a hard per-operation latency commitment, or feeds something that does, "exponentially unlikely to be slow" may still be the wrong shape of promise — and the degenerate case is not a slow path, it is a silently linear structure. **Memory.** With promotion probability p, the expected number of forward pointers per key is a geometric sum: 1 + p + p² + … = 1/(1−p), which is 2 at p = 1/2 and 1.33 at p = 1/4. Across a 10⁸-key index that is on the order of 2×10⁸ forward pointers plus per-node overhead — real money on a fleet. Lowering p to 1/4 cuts pointers by a third at the cost of longer walks per level. **Cache behaviour.** Towers are scattered across the heap, so a descent is a chain of dependent, cache-missing loads. A structure that packs many keys into one wide node touches far fewer cache lines for the same key count. On a read-mostly index this often outweighs everything above. **Bulk loading.** Building a balanced structure from already-sorted data is a straightforward linear pass. A skip list built by repeated insertion pays a logarithmic factor and gets a random shape either way. ## The decision, stated as rules - **Many concurrent writers, ordered access required** → skip list; the locality of its updates is exactly the property that makes concurrent ordered indexing tractable. - **Read-mostly, rebuilt periodically, memory-conscious** → a wide-fanout ordered structure, or simply a sorted array with binary search plus a small overlay for recent changes. - **Hard worst-case latency in the contract** → a structure with a guaranteed height bound, and pay the rebalancing complexity. - **Point lookups only, no ordering needed** → neither; hash-based storage, and revisit the requirement that put ordering on the table. One scale note for the catalog: at 10⁸ keys with p = 1/2, the expected maximum level is about log₂ 10⁸ ≈ 27, so a level cap in the low thirties is generous, and a cap well below that quietly converts the top lane into a long linear walk. Export the observed top level and tower-height histogram; those two metrics separate "the index is slow because it is large" from "the index is slow because it has gone flat."
- At 10^8 keys with p = 1/2, how much pointer overhead does the index carry?The expected forward pointers per key are 1 + p + p² + … = 1/(1−p) = 2, so about 2×10⁸ forward pointers plus per-node headers and the key itself. Dropping p to 1/4 gives 1.33 per key — a third less pointer memory — at the cost of longer right-walks per level, since fewer keys are promoted. The expected top level is about log₂ 10⁸ ≈ 27, so cap the level array in the low thirties.
- Why do readers need no lock in a well-built concurrent skip list?Because level 0 holds every key and is linked before the upper levels are. If a writer links a new node bottom-level-first with atomic pointer writes, a reader descending the levels either sees the new node or does not, and in both cases lands on a consistent bottom-level chain. Deletion marks a node logically before unlinking, so a reader holding it can tell that it is gone rather than following a dangling pointer.
- The index is read-mostly and rebuilt nightly. Does the skip list still win?No — the argument evaporates. With no concurrent writers, the locality-of-update advantage buys nothing, and the costs remain: extra pointers per key and scattered, cache-missing descents. A sorted array with binary search gives better cache behaviour, lower memory and worst-case logarithmic lookup, with a bulk rebuild that is a single sorted pass. Reach for the skip list when mutation under concurrency is the hard part.
- What would you monitor to catch the degenerate case in production?The observed maximum level and the histogram of tower heights, exported alongside key count. Healthy behaviour at p = 1/2 has the top level tracking log₂ n and heights roughly halving at each step. A top level pinned low while the key count grows means promotion has stopped — a stubbed or fixed random source — and the index has quietly become a linear chain. Latency alone reads as ordinary growth.
A balanced tree is a building with a strict code inspection after every renovation — the inspector may need to walk to the roof. A skip list has no code to satisfy, so a renovation disturbs only the two rooms next door.
saying these in an interview costs you the question
- Picks a skip list for raw speed over a balanced tree
- Ignores that the bound is expected, not guaranteed
- Forgets the extra pointers per key at scale
- Assumes good cache locality from pointer chasing
- Chooses an ordered structure for point lookups only