How it works
The bottom level contains every entry in sorted order. Higher levels contain progressively smaller subsets of those entries, forming express lanes through the same data.
To find a key, start at the highest level and move right while the next key is smaller than the target. When you cannot move right, drop down a level and continue. For keys 10, 20, 30, 40, and 50, an upper-level pointer might take you directly from 10 to 40 before you descend to find 30.
On insertion, randomly choose the new entry's height and link it into each level it occupies. With a promotion probability of one-half, roughly half the entries reach the second level and one-quarter reach the third. Deletion removes the entry from all its levels; neither operation needs tree rotations.
Search, insertion, and deletion take expected O(log n) time, though the worst case is O(n). A range query first seeks to its lower bound, then walks the bottom level, giving expected O(log n + k) time for k returned entries.
For ranking by score, order entries by a composite key such as (score, item_id) so ties are deterministic. Add span counts to the pointers if you need expected O(log n) rank lookup; a plain skip list does not provide that automatically. A separate hash map can locate an item's current score before a score update removes and reinserts it.
A worked example
Finding price alerts crossed by a price drop
Suppose one instrument has 100,000 active alerts that fire when its price reaches or falls below a threshold. Store them in a skip list ordered by (threshold, alert_id). If the price drops from $105 to $100, newly crossed thresholds are in [$100, $105), assuming earlier prices were already processed. Seek to $100, then scan until $105. If 200 alerts match, index work is expected O(log 100,000 + 200), rather than scanning every alert. Serialize price processing with alert registration and cancellation for that instrument, and durably record triggered alerts before asynchronous notification. The skip list accelerates matching; it does not provide ordering, recovery, or duplicate suppression.
Trade-offs to say out loud
- Ordered access versus direct lookup
- Skip lists support ranges and sorted traversal, while a hash table is usually a better starting point for equality-only lookups.
- Expected rather than worst-case bounds
- Randomized heights give expected logarithmic operations, unlike a balanced search tree's worst-case logarithmic guarantee.
- Pointer and allocation overhead
- Multiple forward pointers and scattered nodes consume memory and can have poorer cache locality than packed arrays or page-oriented trees.
- Simpler structural updates, nontrivial concurrency
- Avoiding rotations can help concurrent implementations, but correct pointer publication, deletion, and memory reclamation still require careful synchronization.
- An index is not a durability mechanism
- An in-memory skip list needs a separate recovery strategy, such as a write-ahead log and persisted tables, if acknowledged data must survive crashes.
- Rank support adds maintenance work
- Span counts enable efficient rank queries but add metadata and update logic, especially when concurrent writes must preserve consistent ranks.
When to reach for it
- You need frequent inserts and deletes alongside ordered range queries over an in-memory dataset.
- You are designing an LSM-tree storage engine and need a sorted mutable memtable that can later be flushed in order.
- You need an exact, frequently changing ranking with score ranges, top-K reads, or rank queries.
- You need to find matching thresholds in a changing ordered set, such as price alerts indexed by trigger price.
How to bring it up in the interview
- Start with the operations: point lookups, score updates, range scans, or ranks. Explain why a hash table alone cannot serve the ordered queries.
- State expected O(log n) updates and O(log n + k) range reads, then account for result size; retrieving a million matches still requires substantial work.
- Compare it with a balanced tree for an in-memory index and a B-tree for page-oriented storage. Defend the choice using access patterns and memory layout, not just asymptotic complexity.
- Expect follow-ups on duplicate scores, atomic score changes, concurrent readers, and recovery. Specify tie-breaking keys and the synchronization boundary around related index updates.
- Separate local indexing from distributed correctness: sharding a ranking still requires a merge strategy, and a skip list does not solve replication or hot partitions.
Common mistakes
- Claiming guaranteed O(log n) performance instead of expected O(log n) performance.
- Assuming a plain skip list supports efficient rank queries without span metadata.
- Updating a score in place even though that changes the entry's sorted position.
- Treating a concurrent implementation as automatically lock-free or treating ordered traversal as a consistent snapshot.
- Choosing a skip list for equality-only access, or assuming an in-memory index makes writes durable.
Where it comes up
Interview questions where skip lists is part of a strong answer, and why.
- Design a distributed key-value storeA skip-list memtable is a concrete option when explaining the storage engine's write path, ordered reads, and flush behavior.
- Design a top K trending systemAn ordered score index supports changing exact rankings, including removing and reinserting items as sliding-window scores decrease.
- Design a price alert systemAn ordered threshold index supports finding alerts crossed by a price update without scanning every registered alert.
Questions people ask
What is a skip list?
A skip list is a sorted linked structure with multiple levels of forward pointers. Sparse upper levels accelerate navigation, while the bottom level holds every entry and supports ordered scans.
How does a skip list compare with a balanced binary search tree?
Both support efficient ordered lookups and updates. A randomized skip list offers expected O(log n) operations without tree rotations, while a balanced tree provides worst-case O(log n) operations. Memory layout, concurrency requirements, and implementation complexity often matter more than their similar asymptotic costs.
Why use a skip list in an LSM-tree memtable?
A memtable needs to accept writes while keeping keys ordered for reads and sorted flushes. A skip list supports those operations without rebalancing a tree. It is one implementation option, not a requirement of LSM trees, and durability comes from mechanisms outside the skip list.