Skip lists
A balanced search structure with no balancing code - it gets its shape from coin flips, and the coin flips are why it is easy to make concurrent.
Balanced trees are correct and unpleasant. Red-black trees need rotation cases, AVL trees need rebalancing on the way back up, and both need enough of the structure locked during an update that making them concurrent is genuinely hard.
Pugh’s observation in 1990 was that you can get the same asymptotics from randomness, and give up almost nothing in exchange.[1]paperSkip Lists: A Probabilistic Alternative to Balanced Trees
Express lanes
Start with an ordinary sorted linked list, where finding an element means walking every node.
Now give some nodes a second forward pointer that skips ahead. Those form a sparser list over the same data - an express lane. Give some of those a third pointer, and so on.
To search, start at the highest level and move right while the next node’s key is below your
target. When the next hop would overshoot, drop down a level and continue. Each level halves
the remaining distance, so you arrive in about log n hops.
The widget draws each node with intensity proportional to its tower height, and highlights the path each search actually takes. Watch it skip long distances at the top, then refine.
The height of a tower is a coin flip
This is the part that feels like it should not work. When a node is inserted, its height is
chosen by flipping a biased coin: promote with probability p, keep flipping, stop on the
first failure.
No node knows anything about the others. There is no rebalancing, no rotation, no global invariant to restore. The structure is well-shaped because a geometric distribution over many independent draws is reliably well-shaped, not because anyone arranged it.
Expected height is 1/(1-p), and expected search cost is:
(1/p) · log_{1/p}(n)Why p = 1/2 and not something extreme
The two factors in the cost formula pull against each other. A small p means fewer levels
to descend - but far more nodes to walk at each level, because the express lanes are sparse.
A large p means dense lanes and short walks, but a very tall structure and more memory.
Drag promotion probability to 0.05 in the widget. The towers flatten, the express lanes disappear, and search cost climbs toward walking the whole list. Then push it to 0.9 and watch mean tower height explode while search barely improves.
Pugh’s recommendation was p = 1/4 for the memory saving; p = 1/2 is more common in
practice because it is simpler to reason about.[1]paperSkip Lists: A Probabilistic Alternative to Balanced Trees
Where they actually get used
Redis sorted sets are a skip list paired with a hash table, giving both ranked access and
O(1) lookup by member.[3]source codeRedis - t_zset.c, the sorted set skip list LevelDB uses one for its
memtable.[4]source codeLevelDB - skiplist.h, the memtable index Java’s ConcurrentSkipListMap is the ordered
concurrent map in the standard library.
The common thread is concurrency. Because an insert only touches the forward pointers of the nodes immediately preceding it at each level, updates are local and the structure lends itself to fine-grained locking or lock-free implementation in a way rotation-based trees do not.[2]paperConcurrent Maintenance of Skip Lists
The bounds are probabilistic
Worth being precise about what you are buying. A red-black tree guarantees O(log n). A skip list gives O(log n) with high probability - a pathological run of coin flips could in principle produce a tall, useless structure.
In practice the probability of meaningful deviation falls off exponentially with n, so for
any realistic size it is not a concern. But it is a different kind of guarantee, and worth
knowing which one you have when the answer matters.
What p actually buys
Promotion probability trades tower memory against search cost. Both lists hold the same keys; only p differs.
p = 0.5
The textbook value: every node has a 50% chance of another level.
p = 0.1
Far fewer towers, so far less pointer memory.
| Measure | p = 0.5 | p = 0.1 | Gap |
|---|---|---|---|
| Nodes visited per search | 9.75 | 15.5 | 1.6× |
| Mean tower height | 2.11 | 1.16 | 1.8× |
The dial
The line - when someone asks
A skip list is a sorted linked list with extra forward pointers: each node is promoted to the next level with probability p, so higher levels act as express lanes over the data. Search starts at the top level and drops down whenever the next hop would overshoot, giving expected O(log n) with no rebalancing at all. It is the structure you pick when you want ordered access and concurrent updates, which is why it shows up in Redis sorted sets, LevelDB memtables and java.util.concurrent.
Recall
Loading…
Where are you with this?
Saved on this device. Sign in to keep it across devices.
Sources
Primary
- [1]
- [2]
Secondary
- [3]
- [4]