Balanced trees — red-black trees, AVL trees, B-trees — get their O(log n) guarantees from careful bookkeeping: rotations, rebalancing, parent pointers, and color bits that have to be updated correctly on every insert and delete. Skip lists get the same expected O(log n) behavior from something much simpler: a coin flip. Invented by William Pugh in 1990 as an explicitly probabilistic alternative to balanced trees, the skip list trades a worst-case guarantee for a much simpler implementation — and that trade-off turned out to be exactly what two of the most widely deployed storage systems in the industry wanted. Redis uses a skip list to back every sorted set. LevelDB and RocksDB use one to hold every write before it reaches disk.
At a Glance
| Attribute | Detail |
|---|---|
| What it is | A linked list with multiple “express lane” layers, used to search, insert, and delete in expected O(log n) time |
| How balance is achieved | Randomized level assignment (a coin flip per node) instead of rotations or rebalancing rules |
| Expected time complexity | O(log n) search, insert, and delete |
| Worst case | O(n), but no specific input sequence can force it — the randomness is independent of insertion order |
| Space overhead | About 1.33 pointers per node on average, with the recommended p = 1/4 |
| Real-world uses | Redis sorted sets (ZSET), LevelDB and RocksDB memtables |
| Origin | William Pugh, “Skip Lists: A Probabilistic Alternative to Balanced Trees,” Communications of the ACM, June 1990 |
Short Verdict
A skip list isn’t trying to beat a balanced tree on worst-case guarantees — it can’t, and it doesn’t claim to. What it offers instead is an ordered structure with expected logarithmic search, insert, and delete, implemented with plain forward pointers and a random number generator instead of rotation logic, parent pointers, or color bits. That simplicity is precisely why Redis chose it for sorted sets and why LevelDB chose it for the in-memory write buffer every key passes through before it’s flushed to disk: both systems needed fast ordered inserts into a structure that also supports cheap, correct concurrent reads, and a skip list delivers that with far less code than a balanced tree would.
The Problem: Fast Search in a Linked List
A plain sorted linked list supports O(log n) search in theory — except it doesn’t, because you can’t binary-search a linked list. There’s no way to jump to the middle element without walking every node before it, so search, insert, and delete are all O(n). Arrays solve this by supporting random access, but then insertion in the middle requires shifting every subsequent element. Balanced trees solve it by keeping a tree structure that self-corrects on every modification, at the cost of rotation logic that’s notoriously easy to get wrong.
Pugh’s 1990 paper poses a different question: what if a linked list had extra pointers that let a search skip over large chunks of it, the way an express train skips local stops? That’s literally the mechanism. A skip list is a series of linked lists stacked on top of each other. The bottom layer contains every element in sorted order, like an ordinary linked list. Each layer above it contains a randomly chosen subset of the layer below, so a search can start at the top, move right as far as possible without overshooting, then drop down a level and repeat — covering large distances quickly near the top and refining the position near the bottom.
How Randomized Leveling Works
The key design decision is how many levels each node gets, and Pugh’s answer is to decide it randomly at insertion time, independent of how many elements are already in the list. Each new node starts at level 0. A biased coin is flipped with success probability p; as long as it comes up heads, the node’s level increases by one, up to a fixed maximum. Pugh’s paper recommends p = 1/4 for general use, noting that p = 1/2 trades a bit of extra memory for lower variance in search time — a tuning choice, not a correctness requirement.
Because node height is chosen independently of insertion order, no sequence of inserts can deliberately produce a degenerate skip list the way a sorted sequence of inserts can produce a degenerate unbalanced binary tree. The structure can still get unlucky — the paper is explicit that the worst case is O(n) — but Pugh’s analysis shows the probability of a search taking much longer than O(log n) falls off exponentially, which is why “expected” rather than “guaranteed” logarithmic time is an acceptable trade in practice. With p = 1/4, the expected number of forward pointers per node works out to about 1.33, since a node has one pointer at level 0 for certain and a geometrically-decreasing chance of further pointers above that.
A Minimal Skip List in Python
This implementation shows the two operations that matter: randomized level assignment on insert, and the level-by-level descent that both search and insert rely on.
import random
class Node:
def __init__(self, value, level):
self.value = value
self.forward = [None] * (level + 1)
class SkipList:
def __init__(self, max_level=16, p=0.25):
self.max_level = max_level
self.p = p
self.level = 0
self.head = Node(None, max_level)
def _random_level(self):
lvl = 0
while random.random() < self.p and lvl < self.max_level:
lvl += 1
return lvl
def insert(self, value):
update = [self.head] * (self.max_level + 1)
node = self.head
for i in range(self.level, -1, -1):
while node.forward[i] and node.forward[i].value < value:
node = node.forward[i]
update[i] = node
new_level = self._random_level()
if new_level > self.level:
for i in range(self.level + 1, new_level + 1):
update[i] = self.head
self.level = new_level
new_node = Node(value, new_level)
for i in range(new_level + 1):
new_node.forward[i] = update[i].forward[i]
update[i].forward[i] = new_node
def search(self, value):
node = self.head
for i in range(self.level, -1, -1):
while node.forward[i] and node.forward[i].value < value:
node = node.forward[i]
node = node.forward[0]
return node is not None and node.value == value
sl = SkipList()
for v in [3, 1, 4, 1, 5, 9, 2, 6]:
sl.insert(v)
print(sl.search(5)) # True
print(sl.search(7)) # False
The update array is the detail that makes insertion work: as the search descends, it records the rightmost node reached at every level, so once the new node’s random level is known, splicing it in at each relevant level is a constant-time pointer update rather than another full pass over the list.
Real-World Uses: Redis and LevelDB
Redis’s own documentation for sorted sets describes the underlying structure as “a dual-ported data structure containing both a skip list and a hash table,” which is why a Redis ZSET supports both O(log(N)) insertion by score (via the skip list) and O(1) lookup of a member’s current score (via the hash table) at the same time. Redis documents ZADD as costing O(log(N)) and range queries like ZRANGE as O(log(n) + m), where m is the number of elements returned — exactly the profile a skip list provides: logarithmic positioning plus a cheap linear walk once you’re there, which is ideal for leaderboard and ranking use cases where you frequently need “the top N” or “everyone between rank X and Y.”
LevelDB, Google’s embedded key-value store, uses a skip list for an entirely different reason: as the in-memory MemTable that absorbs every write before it’s flushed to disk as an immutable sorted file. LevelDB’s own skiplist.h source comments describe the node’s height as chosen so that it “increase[s] height with probability 1 in kBranching” with kBranching set to 4 — the same geometric-level idea from Pugh’s paper, just named differently. The comments also note that “the contents of a Node except for the next/prev pointers are immutable after the Node has been linked into the SkipList,” which is precisely what makes the structure safe for concurrent, lock-free reads while a single writer inserts — a property a balanced tree’s in-place rotations don’t offer nearly as cleanly. RocksDB, Meta’s fork of LevelDB, inherited the same design for its own memtable.
This pairs naturally with ideas covered elsewhere on this site: LevelDB’s skip-list memtable is the entry point for the exact write-then-flush-then-compact pipeline described in our LSM-trees vs. B-trees piece, and once data lands on disk as an SSTable, systems like Cassandra use a Bloom filter to decide whether that file is even worth checking.
Skip Lists vs. Balanced Trees
| Factor | Skip List | Balanced Tree (e.g. red-black) |
|---|---|---|
| Balancing mechanism | Randomized node height, decided once at insertion | Deterministic rotations and recoloring on every insert/delete |
| Worst case | O(n), vanishingly unlikely, independent of input order | O(log n), guaranteed by construction |
| Implementation complexity | Low — forward pointers and a random level generator | Higher — multiple rotation cases to implement correctly |
| Concurrent reads during writes | Straightforward, since existing nodes aren’t mutated in place on insert | Harder, since rotations restructure existing nodes |
| Range queries | Natural — walk the bottom-level linked list | Natural via in-order traversal, but requires tree-aware iteration logic |
Trade-offs
- No hard worst-case guarantee: a vanishingly unlucky sequence of coin flips can still degrade to O(n), which matters for systems with strict real-time latency requirements.
- Memory overhead is probabilistic, not fixed: a node’s pointer count depends on its random level, so total memory use varies run to run, even for the same dataset.
- Requires a decent random number generator: a poor one can bias level distribution and erode the expected-time guarantees the structure depends on.
- Simplicity is the main win: no rotation logic, no color bits, and — as LevelDB’s design shows — existing nodes stay immutable on insert, which simplifies safe concurrent reads.
Bottom Line
Skip lists prove that a probabilistic structure can match a deterministic one’s expected performance with a fraction of the implementation complexity. That’s not a theoretical curiosity: it’s the exact reasoning Redis’s engineers applied when they needed an ordered structure for sorted sets, and the exact reasoning behind LevelDB’s choice of memtable, where immutable-once-inserted nodes make concurrent reads safe without a maze of locking around tree rotations. If you need guaranteed worst-case bounds — a hard real-time system, for instance — a balanced tree still wins. If you need an ordered structure that’s simple to implement correctly, supports fast range queries, and plays well with concurrent readers, a skip list is usually the better trade.
FAQ
Are skip lists actually used in production, or just a teaching tool?
They’re in production at serious scale: Redis’s sorted set type and LevelDB/RocksDB’s memtable both use skip lists as their core structure, not as a simplification for textbooks.
What probability p should I use for level assignment?
Pugh’s paper recommends p = 1/4 for general use as a good balance of time and space; p = 1/2 uses more memory per node but reduces the variance of search times, which can matter if consistent latency matters more than average memory use.
Can a skip list’s performance degrade to O(n) in practice?
Theoretically yes, but Pugh’s analysis shows the probability shrinks exponentially as n grows, and — critically — no adversarial insertion order can force it, unlike an unbalanced binary search tree fed sorted input.
Why does Redis use a skip list instead of a balanced tree for sorted sets?
Redis’s own documentation says sorted sets pair a skip list with a hash table specifically to get O(log(N)) ordered operations and O(1) score lookups together, and the simpler skip-list implementation was a deliberate engineering trade-off over a more complex balanced-tree structure.
Sources
- William Pugh, “Skip Lists: A Probabilistic Alternative to Balanced Trees,” Communications of the ACM, June 1990
- Redis Documentation — Sorted Sets
- LevelDB source — db/skiplist.h
- Related reading on this site: LSM-Trees vs. B-Trees
- Related reading on this site: Bloom Filters Explained
Discover more from Software Online Review
Subscribe to get the latest posts sent to your email.
