Skip Lists: The Shortcut Nobody Rotates
Balanced trees rebalance with rotations. Skip lists layer express lanes with random promotion—same O(log n) search, simpler locking.
On this page
You want to search a sorted list of 100 million records. A naive walk touches every node: 100 million comparisons, O(n), unusable. A balanced tree cuts it to 27 comparisons (O(log n)), but rebalancing after each insert means rotating branches, locking subtrees, and reasoning about five cases. A skip list needs only four comparisons and a coin flip. That coin flip is the whole idea.
Left: O(n) linear scan of a sorted linked list. Right: O(log n) jump across express lanes in a skip list.
The Problem: Why Sorted Lists Are Slow, Trees Are Complex
Start with a sorted linked list: 10 -> 20 -> 30 -> 40 -> 50 -> null. To find 50, you have no choice but to walk: check 10 (too small), check 20, check 30, check 40, then finally 50. Five nodes touched to reach the last one — and there is no shortcut available, because a linked list only lets you step one node at a time. With a million nodes you touch half a million on average. That is O(n), and no amount of CPU helps.
A balanced tree fixes this. Red-black or AVL trees keep O(log n) height by rotating subtrees when insertions unbalance the tree. The math is right—27 comparisons for a million nodes. But the implementation cost is brutal: five rotation cases, parent pointers, color bits, complex locking because rotations touch multiple nodes at once. And every language reimplements this, usually with bugs.
There is a third path: express lanes.
The Breakthrough: Layers, Not Rotations
A skip list is a sorted linked list plus a shortcut. Take roughly 50% of the nodes and promote them to a second level, then roughly 50% of those to a third level, and so on. Now the top-level nodes are spaced widely apart. To find 50:
- Start at the highest level, where only the widely-spaced towers exist, and walk right as far as you can without passing your target.
- The moment the next node on this lane would overshoot, drop down one level — you are now closer, on a denser lane.
- Repeat until you land on the base level and step onto the node itself.
Each drop-down halves the remaining stretch of list, so the search path is a staircase rather than a march: about three nodes touched here instead of five, and about log n instead of n at scale. The randomness—flipping a coin at each promotion—replaces the complex rebalancing logic. No rotations. No subtree updates. Just a few forward pointers.
The cost: randomness means O(log n) in expectation, not absolute worst case (you could unluckily flip all heads and build a single tall tower). In practice, with a million nodes, the probability of seeing O(n) is less than one in 10^18. Every database accepts this trade.
How Random Promotion Works
When you insert a new node, you don’t decide its level ahead of time. You flip a coin: heads, promote to level 1. Flip again: heads, promote to level 2. Keep flipping until you lose. This gives you:
- 50% of nodes at level 0 only
- 25% promoted to level 1
- 12.5% promoted to level 2
- 6.25% promoted to level 3
- And so on
Left: Random coin-flip promotion (50% chance each level). Right: Tree rotations ripple up the tree, requiring coordination between multiple nodes.
This randomness has a beautiful consequence: the expected height is O(log n), and the data structure organizes itself without any rebalancing logic. Compare a balanced tree insertion: you insert at a leaf, then walk up checking balance factors, rotating subtrees, updating heights. A skip list insertion: insert at the base level, flip coins to decide how high to promote, done.
Why Concurrency Loves Skip Lists
Here’s where skip lists win in the real world: locking.
In a balanced tree, a rotation needs exclusive access to at least three nodes: the parent, the child, and the grandchild. If you’re using mutexes, readers block while you rotate. If you’re using lock-free CAS loops, coordinating three nodes atomically is hard. Most databases don’t even try—they lock the entire tree during updates.
In a skip list, an insertion modifies only the forward pointers of a few nodes on the path to insertion. You can lock each node independently as you descend, release it, and move on. Other threads can insert into non-overlapping parts of the list concurrently. No cascading rotations. No need to lock the root.
This is why Redis sorted sets (ZSET) are fast under concurrent load, and why LSM MemTables (the in-memory write buffer) use skip lists instead of trees. High-throughput databases need throughput; skip lists give it with minimal coordination.
For lock-free concurrency (no mutexes, just compare-and-swap), skip lists are dramatically simpler. You can implement a lock-free skip list by atomically updating the level pointers using CAS. Trees require coordinating rotations atomically, which is so complex that most lock-free trees are only used in research papers.
The Honest Trade-Off: Expected, Not Worst-Case
Skip lists are O(log n) in expectation. With pathological coin flips, the height could reach O(n). Is this acceptable?
Yes, for most systems. The probability of height exceeding 30 levels in a billion-node list is less than 1 in 10^15. Your hardware will fail first. For systems that need strict O(log n) worst-case guarantees (hard real-time systems, or latency SLAs at the 99.99th percentile), use a deterministic balanced tree. They are rare.
Database choice: Transient data structures that see churn (MemTables, index buffers) use skip lists. Persistent data (disk-resident trees, distributed consensus logs) use balanced trees—the worst-case guarantee is worth the complexity when data is expensive to recompute.
When you insert, you touch only the node and a few ancestors. Concurrent access needs only local locking. O(log n) expected, O(1) space overhead per node (two or three pointers).
Every operation is guaranteed O(log n) worst-case. Rotations are well-understood and tested for 70 years. Need parent pointers, balance factors, or color bits. Concurrency is harder.
Real-World Implementations
Redis ZSET: Uses a skip list for O(log n) range queries and O(1) sorted-set inserts, layered with a hash table for O(1) lookups by member. The skip list gives you both ZRANGE by score and ZSCORE by member in one data structure.
RocksDB MemTable: The in-memory write buffer is a skip list. When it fills, it’s sorted already; no need to sort on disk. The log-structured merge (LSM) tree uses the skip list’s speed and simple concurrency model.
Sorted set in Go (standard library avoided): Most implementations use trees or heaps because the author prefers deterministic worst-case. Skip lists are common in educational codebases and highly concurrent systems.
The pattern: high-concurrency, transient data → skip list. Persistent, read-heavy data → tree. You’ll rarely choose between them for a single use case; they’re designed for different constraints.
Closing: Simplicity Is a Performance Feature
Balanced trees are optimal in theory—O(log n) worst-case, minimal wasted space. But they bury the optimal algorithm under complex rotation logic that must be rewritten in every language, debugged, and locked down for concurrency.
Skip lists are suboptimal in theory (expected vs worst-case) but dramatically simpler: insert, flip coins, done. The coin flips cost nothing—true random number generation is hard, but a simple linear-congruential generator or even a counter modulo a prime works fine in practice. The simplicity is why lock-free skip lists exist and lock-free trees don’t.
When you see Redis sorted sets or LSM MemTables, you’re seeing a bet that simplicity and concurrency matter more than worst-case guarantees. For most modern systems, that’s the right bet.
Frequently asked questions
What is a skip list and how does it speed up search?
A skip list layers 'express lanes' over a sorted linked list by randomly promoting nodes to higher levels. Instead of walking every node (O(n)), you jump along the top lanes and drop down when you overshoot, visiting only O(log n) nodes. The randomness replaces the need for rotations or complex rebalancing logic.
Why do Redis sorted sets and LSM MemTables use skip lists instead of balanced trees?
Skip lists are simpler to implement and reason about, but the real win is concurrency. Insertion touches only a few forward pointers; no tree rotations cascade through multiple branches. This makes lock-free implementations dramatically simpler. Redis ZSET uses skip lists alongside hash tables for range queries and scoring; LSM MemTables use them to keep writes sorted in memory with minimal locking.
How does randomness give O(log n) worst case?
Randomness gives O(log n) in *expectation*, not worst case—that's an honest trade. With probability 1/2, a node is promoted one level; with probability 1/4, two levels; with probability 1/8, three levels. This produces roughly equal numbers of nodes per level (50% at level 1, 25% at level 2, etc.), so the total height is O(log n) with very high probability. Worst case is O(n), but practically impossible.
How do you lock a skip list for concurrent inserts without rotations blocking readers?
Each node has a lock only on its forward pointers, not the node itself. An inserter locks the predecessor pointers it will modify, inserts at the base level, then unlocks before promoting—readers never block on insertion. Compare this to tree rotations, which need to lock multiple parent-child relationships simultaneously. The simplicity is why lock-free skip list implementations (CAS loops, no mutexes) are so much more practical than lock-free trees.
When should you NOT use a skip list instead of a balanced tree?
Use a tree if you need strict O(log n) worst-case guarantees and can afford the complexity. Use a tree if you need parent pointers for range deletions or efficient reverse traversal. Skip lists win when you prioritize simplicity, concurrent inserts, or range scans (you just walk the base level). Most databases choose skip lists for in-memory work (transient, high churn); trees for persistent storage (predictable latency, stability).
/* Comments */
Comments are offline right now — we reconnect automatically, nothing is lost.