⏱️ Lectura: 13 min
Redis sorts millions of elements in its sorted sets without balancing a tree: each new node flips a coin to decide how many shortcuts it will have. That structure is called a skip list, and it’s also what LevelDB and RocksDB use for their in-memory MemTable.
📑 En este artículo
The idea behind a skip list is simple: instead of forcing perfect balance with rotations the way an AVL or red-black tree does, chance is left to distribute the shortcuts. The result is a structure that’s easier to implement, easier to parallelize, and delivers expected O(log n) performance for search, insertion, and deletion.
TL;DR
- You’ll understand how a skip list achieves expected O(log n) searches without rotations or tree rebalancing.
- You’ll be able to implement a full skip list in JavaScript, with insertion, search, and random levels.
- You’ll know why Redis uses skip lists in its sorted sets and how to verify it with OBJECT ENCODING.
- You’ll understand why LevelDB and RocksDB use skip lists in their in-memory MemTable.
- You’ll be able to choose between a skip list, a balanced tree, or a hash table depending on the actual use case.
- You’ll learn the common mistakes when choosing the probability p and the maximum level of a skip list.
- You’ll understand why skip lists are easier to parallelize than a balanced tree.
What Skip Lists Are and Why They Matter
Picture a train line that stops at every station. If you want to go from station 1 to station 30, you have to pass through the 29 before it: that’s a sorted linked list, and looking up a value costs O(n). Now add an express line that only stops every 4 stations, and above that, another one that stops every 16. To go from station 1 to station 30, you take the fastest line available, ride it as far as you can, and drop down a level only when you’re about to overshoot. That’s exactly what a skip list does.
The concept was formalized by William Pugh in 1990 in the paper “Skip Lists: A Probabilistic Alternative to Balanced Trees,” published in Communications of the ACM. His central observation: instead of maintaining guaranteed balance through strict rules (as a red-black tree does), you can achieve an equally good expected balance by letting each node flip a coin to decide how many levels it will participate in.
This matters because classic balanced trees are notoriously hard to implement correctly: the rotations in an AVL tree or the four recoloring cases in a red-black tree are a constant source of subtle bugs. A skip list solves the same problem (keeping data sorted with fast access) with an algorithm that fits in under 50 lines.
How a Skip List Works Internally
Each node in a skip list stores a value and an array of “forward” pointers, one for each level it participates in. The header node (head) holds no real value: it points to the first node at each level. When a new node is inserted, its level is decided with a simple loop: start at level 1, and while a random number is less than a probability p, go up one more level (up to a maximum cap).
With p = 0.5 (Pugh’s original value), half the nodes reach level 2, a quarter reach level 3, an eighth reach level 4, and so on. That means the top level is exponentially sparser than the base level, just like the express train line stops at far fewer stations than the local line.
The search algorithm starts at the highest level of the header node and advances as long as the next node at that level has a value smaller than the target. When the next node would overshoot the target (or doesn’t exist), the algorithm drops down a level and repeats, until it reaches level 0, where it compares directly against the target value.
flowchart LR
subgraph N3["Level 3 (express)"]
H3["START"] --> A3["30"] --> F3["END"]
end
subgraph N2["Level 2"]
H2n["START"] --> A2["10"] --> B2["30"] --> F2["END"]
end
subgraph N1["Level 1"]
H1["START"] --> A1["5"] --> B1["10"] --> C1["20"] --> D1["30"] --> F1["END"]
end
subgraph N0["Level 0 (all data)"]
H0["START"] --> A0["5"] --> B0["10"] --> C0["15"] --> D0["20"] --> E0["25"] --> G0["30"] --> F0["END"]
endPractical Examples with Code
To see the difference, let’s first compare a naive search over a sorted linked list:
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
function searchInSortedList(head, value) {
let current = head;
let steps = 0;
while (current !== null && current.value < value) {
current = current.next;
steps++;
}
const found = current !== null && current.value === value;
return { found, steps };
}This function walks through the list node by node. If the list has 1 million sorted elements and we search for the last one, the result is 1 million comparisons: pure O(n).
Now, the complete implementation of a skip list, with insertion and search:
class SkipListNode {
constructor(value, level) {
this.value = value;
this.forward = new Array(level + 1).fill(null);
}
}
class SkipList {
constructor(p = 0.25, maxLevel = 16) {
this.p = p;
this.maxLevel = maxLevel;
this.level = 0;
this.head = new SkipListNode(-Infinity, maxLevel);
}
randomLevel() {
let lvl = 0;
while (Math.random() < this.p && lvl < this.maxLevel) {
lvl++;
}
return lvl;
}
insert(value) {
const update = new Array(this.maxLevel + 1).fill(this.head);
let current = this.head;
for (let i = this.level; i >= 0; i--) {
while (current.forward[i] !== null && current.forward[i].value < value) {
current = current.forward[i];
}
update[i] = current;
}
const newLevel = this.randomLevel();
if (newLevel > this.level) {
for (let i = this.level + 1; i <= newLevel; i++) update[i] = this.head;
this.level = newLevel;
}
const newNode = new SkipListNode(value, newLevel);
for (let i = 0; i <= newLevel; i++) {
newNode.forward[i] = update[i].forward[i];
update[i].forward[i] = newNode;
}
}
search(value) {
let current = this.head;
let comparisons = 0;
for (let i = this.level; i >= 0; i--) {
while (current.forward[i] !== null && current.forward[i].value < value) {
current = current.forward[i];
comparisons++;
}
}
current = current.forward[0];
comparisons++;
const found = current !== null && current.value === value;
return { found, comparisons };
}
}
const list = new SkipList();
for (const n of [5, 10, 15, 20, 25, 30, 35, 40]) list.insert(n);
console.log(list.search(25));With 8 elements, search(25) usually resolves in 2 to 4 comparisons instead of walking through all 8 nodes one by one. The difference becomes dramatic at scale: with 1 million elements, a linked list needs up to a million comparisons in the worst case, while a skip list needs, on average, only about 20.
sequenceDiagram
participant N3 as Level 3
participant N2 as Level 2
participant N1 as Level 1
participant N0 as Level 0
Note over N3: search for 25, start at the top
N3->>N3: compare with 30, it's greater: go down
N3->>N2: drop one level
N2->>N2: compare with 30, it's greater: go down
N2->>N1: drop one level
N1->>N1: compare with 20, advance
N1->>N1: compare with 30, it's greater: go down
N1->>N0: drop one level
N0->>N0: compare with 25, foundHow to Get Started Step by Step
The fastest way to see a skip list in action is through Redis, which uses it internally in its sorted sets (ZSET):
redis-cli ZADD ranking 100 "player1" 250 "player2" 80 "player3"
redis-cli OBJECT ENCODING ranking
redis-cli CONFIG GET zset-max-listpack-entries
redis-cli ZRANGEBYSCORE ranking 0 200OBJECT ENCODING ranking returns listpack while the sorted set has few small elements. As soon as it exceeds zset-max-listpack-entries (128 by default) or a value exceeds zset-max-listpack-value (64 bytes by default), Redis switches the encoding to skiplist: that’s where the structure we saw above comes in, implemented in its source code as zskiplist.
💡 Tip: runOBJECT ENCODINGbefore and after adding hundreds of elements to a sorted set to watch the switch fromlistpacktoskiplistlive.
To try your own implementation in Node.js, the flow is straightforward:
mkdir skiplist-demo && cd skiplist-demo
npm init -ySave the SkipList class from the block above in a file called skiplist.js, export it with module.exports = SkipList, and in another file do const SkipList = require('./skiplist') to insert values and call search.
flowchart TD
A["Insert new node"] --> B["Level = 0"]
B --> C{"Flip coin"}
C -->|"heads (25%)"| D["Level += 1"]
D --> C
C -->|"tails (75%)"| E["Final level decided"]
E --> F["Insert node at all levels from 0 to Level"]Real-World Use Cases
Redis‘s sorted sets are the most visible example: they’re used for leaderboards, priority queues, and rate limiters, and their internal encoding switches to a skip list precisely to sustain fast inserts and range queries as they grow.
LevelDB, Google’s key-value database, implements its MemTable (the in-memory buffer where writes land before flushing to an SSTable on disk) directly as a skip list, defined in db/skiplist.h in the official repository. RocksDB, Facebook’s fork of LevelDB, inherits that same design as its default MemTable.
Java ships concurrent skip lists in its standard library: ConcurrentSkipListMap and ConcurrentSkipListSet, in the java.util.concurrent package, are lock-free sorted structures designed for multiple threads reading and writing at once.
Search engines that implement inverted indexes also use skip lists to jump over entire blocks of a postings list when intersecting the results of multiple terms, avoiding scanning every document one by one.
Common Mistakes and Best Practices
The most frequent mistake is choosing the probability p poorly. A very high p (close to 1) generates too many levels and wastes memory on pointers that are barely used. A very low p (close to 0) leaves almost all nodes at level 0, degrading the structure to a plain linked list.
Redis chose p = 0.25 instead of Pugh’s original 0.5, a detail worth understanding in the next section.
Another mistake is not setting a reasonable maxLevel. In theory, without a cap, a node could generate an absurdly high level; in practice, a ceiling is calculated based on the expected size of the dataset (Redis uses 32 as the maximum).
⚠️ Watch out: a skip list isn’t cache-friendly. Its pointers jump across scattered memory locations, while a B-tree groups several keys per node and makes better use of the CPU cache. That’s why disk indexes almost always use B-trees or B+ trees, not skip lists.
Finally, a skip list implemented directly like the one in this article isn’t safe for multiple simultaneous writers. Production-grade concurrent versions avoid a global lock by using compare-and-swap atomic operations on each level’s pointers.
Comparison with Alternatives
| Option | When to use it | Advantage | Limitation |
|---|---|---|---|
| Skip list | In-memory structures with concurrent reads and writes | Simple to implement, easy to parallelize | Not cache-friendly, more memory due to extra pointers |
| AVL or red-black tree | When guaranteed worst-case balance is required | O(log n) guaranteed, not just expected | Complex rotations to implement and debug |
| B-tree or B+ tree | Disk indexes or databases | Groups keys per node, leverages cache and minimizes I/O | Worse for concurrent writes in pure memory |
| Hash table | Exact lookup without needing order | Expected O(1) lookup | Doesn’t maintain order, no good for ranges |
| Sorted linked list | Very small datasets | Trivial to implement | O(n) on every search |
Going Deeper: The Theory Behind Skip Lists
The expected number of levels in a skip list with n elements is approximately log base 1/p of n. With p = 0.5, that’s log₂(n); with p = 0.25, it’s log₄(n), fewer levels but with more nodes per level.
Each node has, on average, 1/(1 – p) forward pointers. With p = 0.5 that gives 2 average pointers per node; with p = 0.25 it drops to 1.33 average pointers. That’s the concrete reason Redis chose 0.25: fewer pointers per node means less memory consumed per entry in a sorted set, a resource far more expensive in an in-memory database than in a disk-based one.
💭 Key point: lowering p from 0.5 to 0.25 is a deliberate tradeoff between memory and CPU: you pay with more comparisons during search in exchange for a lighter structure in RAM.
The theoretical worst case for a skip list is still O(n), if by bad luck every coin flip comes out the same and no node ever rises a level. But the probability of that scenario decreases exponentially with the size of the structure, which is why the observed behavior in practice is consistently O(log n).
The reason concurrent skip lists are simpler to reason about than a concurrent balanced tree is that inserting a middle node only requires updating one pointer per level, without needing to rebalance the rest of the structure the way a tree rotation demands.
📖 Summary on Telegram: View summary
Your next step: clone the SkipList class from this article, insert 1000 random numbers, and count how many levels your instance actually uses with console.log(list.level) to check that it approaches log base 1/p of n.
Frequently Asked Questions
Is a skip list faster than a balanced tree?
In practice, the expected performance is similar, O(log n) in both cases. The difference lies in implementation simplicity and in the fact that a balanced tree guarantees the worst case, while a skip list only guarantees it on average.
What happens in the worst case of a skip list?
The theoretical worst case is O(n), if the random level generator produced an unfavorable distribution. The probability of that happening decreases exponentially as the structure grows.
Why does Redis use skip lists instead of a B-tree?
Because Redis’s sorted sets live entirely in memory, where the benefit of a B-tree (grouping keys to minimize disk operations) doesn’t apply, and the simplicity of implementing and parallelizing a skip list outweighs it.
Can a skip list be used for disk indexes?
It’s uncommon, because its scattered pointers don’t make good use of the CPU cache or minimize disk reads the way a B-tree or B+ tree does, which groups many keys into each node.
What probability p should I use?
Pugh’s original value is 0.5. Redis uses 0.25 to reduce average memory per node in exchange for more comparisons during search, a reasonable tradeoff when RAM is the scarcest resource.
Do lock-free concurrent skip lists exist?
Yes, Java’s ConcurrentSkipListMap is the best-known example: it uses compare-and-swap atomic operations on each level’s pointers instead of global locks.
References
- Wikipedia: Skip list: history, formal definition, and complexity analysis of the structure.
- Redis Docs: Sorted sets: official documentation for ZADD, ZRANGEBYSCORE, and the internal encoding of sorted sets.
- GitHub: google/leveldb: LevelDB source code, including the skip list implementation in db/skiplist.h.
📱 Enjoying this content? Follow @programacion on Telegram for daily tech content in Spanish: quick summaries, fresh content every day. @programacion
Imagen destacada: Foto de Julia Kadel en Unsplash
0 Comments