Module 10 · Data structures for scale · Lesson 7 of 11
Skip lists
A sorted linked list with randomised express lanes giving logarithmic search, insert and delete without rebalancing. Why Redis sorted sets and LSM memtables use it instead of a balanced tree, coin-flip levels.
The video walkthrough is part of Pro.
See what Pro includesWhy it matters
Sorted data that changes constantly, leaderboards, time-ordered indexes, the in-memory write buffer of an LSM engine, needs a structure with fast ordered inserts, deletes and range scans. Balanced trees do it but need rotations and are awkward to make concurrent. The skip list reaches the same logarithmic bounds with a trick that is simple to implement and friendly to concurrent access, which is why Redis, LevelDB, RocksDB and many others chose it. Interviewers ask because it reveals whether you understand randomisation as an engineering tool.
The idea
Start with a sorted linked list. Searching it is linear. Now give some nodes a second pointer that skips ahead several nodes, forming an express lane; give fewer nodes a third, faster lane; and so on. To search, start on the top lane, move right while the next key is smaller than the target, drop a level when it is larger, and repeat until the bottom lane. With each lane roughly halving the nodes of the one below, search visits about log n nodes.
The randomisation is in how nodes get levels: on insert, flip a coin repeatedly; the number of heads before the first tail is the node's level (capped). About half the nodes have level 1, a quarter level 2, an eighth level 3, which produces the halving structure on average without any rebalancing.
Operations
- 1
Search
Top lane, move right while next key is less than target, drop down when it is greater or equal, finish at the bottom. Expected O(log n). - 2
Insert
Search to find the position at every level, recording the last node passed on each lane; flip coins for the new node's level; splice it into each lane up to that level. No rotations, no rebalancing. - 3
Delete
Search, then unlink the node from every lane it appears in. Again purely local pointer changes. - 4
Range scan
Search to the start key, then walk the bottom lane. Ordered iteration is as cheap as a linked list, which trees cannot match without threading. - 5
Rank and by-rank queries
Store the span (number of bottom-level nodes skipped) on each forward pointer; summing spans during a search gives an element's rank in O(log n), and the same walk finds the element at a given rank. This is how Redis answers ZRANK and ZRANGE by index.
Why systems pick it over a balanced tree
| Skip list | Balanced tree (red-black, AVL) | |
|---|---|---|
| Bounds | O(log n) expected, with high probability | O(log n) worst case |
| Rebalancing | None; levels from coin flips | Rotations on insert and delete |
| Implementation | Short and hard to get wrong | Long and easy to get wrong |
| Concurrency | Local pointer updates; lock-free versions are practical (Java ConcurrentSkipListMap) | Rotations touch many nodes; fine-grained locking is hard |
| Memory | About 1.33 pointers per node on average plus the key | Two child pointers plus colour or height per node |
| Ordered iteration | Walk the bottom lane | In-order traversal with a stack or parent pointers |
Redis sorted sets use a skip list plus a hash table (for O(1) score lookup by member), LevelDB and RocksDB use a lock-free skip list as the memtable so writers and readers proceed concurrently, and Lucene uses skip-list-like structures over postings for fast seeking.
Caveats
Bounds are probabilistic: a pathological run of coin flips is possible but astronomically unlikely for large n. Pointer-chasing across levels is cache-unfriendly compared with a B-tree's dense pages, so skip lists are an in-memory structure, not a disk one. The per-node overhead of multiple pointers matters for very small keys.