Skip Lists: The Structure Redis Chose Over Balanced Trees

You're building a leaderboard. Ten million players, tens of thousands of score updates a second, and the product spec wants two queries on every page load: "what's my score?" and "what's my rank?" A hash table answers the first in O(1) and is hopeless for the second. A sorted array answers rank instantly and turns every score update into an O(n) shuffle. A balanced tree handles both in O(log n) — if you augment every node with subtree sizes and maintain those sizes through every rotation, in code you will get wrong the first three times you write it.

This is not a hypothetical. It's the exact design problem Redis sorted sets solve, and Redis's answer was none of the above. It was a sorted linked list wearing a probabilistic hat — plus a hash map on the side. The skip list's entire pitch is that it deletes the hardest code in the balanced-tree world (rebalancing) and replaces it with a random number generator, at the price of "expected" instead of "guaranteed" O(log n). William Pugh introduced it in a 1990 CACM paper with a title that was a straight-up challenge: "Skip Lists: A Probabilistic Alternative to Balanced Trees." Thirty-six years later, it's load-bearing in Redis, LevelDB, RocksDB, and the JDK. The challenge held up.

A sorted linked list with express lanes

Start from what's broken. A sorted linked list gives you ordered traversal and O(1) splicing — and O(n) search, because you can't binary search something you can only walk one node at a time.

{ "type": "linked-list", "title": "level 0 alone: sorted, spliceable, and O(n) to search", "data": [3, 9, 17, 26, 42] }

The fix is the subway-map move: keep the local line that stops everywhere, and add an express line that stops at every fourth station, and an express-express line above that. To reach a station, ride the fastest line as far as it goes without overshooting, then drop down one line and repeat. Each line you drop from has done exponentially more of the distance than the one below it.

Concretely: every element sits in the level-0 list. Some elements also appear in level 1, fewer in level 2, and so on. A node that appears in levels 0 through k is one "tower" with k+1 forward pointers. Search holds a single invariant: you are always at the rightmost node whose key is less than the target, at the current level. Move right while the next key is still less than the target; when the next key is too big (or NIL), drop down a level. At level 0, the next node either is your target or proves it's absent.

flowchart LR
    S1["start at HEAD, top level"] --> S2["level 2: next is 17, still below 26 — step right"]
    S2 --> S3["level 2 at 17: next is NIL — drop to level 1"]
    S3 --> S4["level 1 at 17: next is 26 — stop, drop to level 0"]
    S4 --> S5["level 0: next IS 26 — found"]
    style S1 fill:#374151,color:#fff
    style S5 fill:#22c55e,color:#111

Two things fall out of this shape for free. Range queries: once you've found the left edge of a range, the rest of the answer is a level-0 walk — O(log n + k) for k results, with no re-descending and no auxiliary stack. And ordered iteration is just "follow the bottom lane," which is the operation linked lists were born for.

The coin flip that replaces rebalancing

The balanced tree's problem was never search — it's maintaining balance under mutation. AVL and red-black trees earn their worst-case O(log n) by detecting invariant violations after every insert and delete and repairing them with rotations. The repair logic is where the case analysis lives, and delete is where the case count explodes.

The skip list's answer: don't maintain balance. Manufacture it statistically. When a node is inserted, flip a biased coin to decide its height — keep growing while the flip succeeds, with probability p per level:

def random_level(p=0.25, max_level=32):
    level = 1
    while random.random() < p and level < max_level:
        level += 1
    return level

That's a geometric distribution: with p = 1/4, about 75% of nodes are height 1, ~19% are height 2, ~4.7% height 3. Level k has about n·pᵏ nodes — exactly the exponentially-thinning express lanes we wanted, with nobody coordinating anything. This is the same bet Bloom filters make: accept a probabilistic guarantee in exchange for a radically simpler structure. Redis's version of this function is four lines of C; the constants next to it read ZSKIPLIST_P 0.25 and ZSKIPLIST_MAXLEVEL 32, with a comment noting 32 levels is enough for 2⁶⁴ elements (Pugh's rule: cap at log₁/ₚ of the biggest n you'll ever hold).

Here's the whole structure in Python. Note what's absent: there is no rebalance step, because there is nothing to rebalance.

import random

class Node:
    __slots__ = ("key", "forward")
    def __init__(self, key, height):
        self.key = key
        self.forward = [None] * height      # forward[i]: next node at level i

class SkipList:
    P, MAX_LEVEL = 0.25, 32

    def __init__(self):
        self.head = Node(None, self.MAX_LEVEL)   # sentinel tower, full height
        self.level = 1                           # highest level in use

    def _random_level(self):
        h = 1
        while random.random() < self.P and h < self.MAX_LEVEL:
            h += 1
        return h

    def _find_predecessors(self, key):
        """update[i] = rightmost node with key < target, at level i."""
        update = [self.head] * self.MAX_LEVEL
        x = self.head
        for i in range(self.level - 1, -1, -1):
            while x.forward[i] and x.forward[i].key < key:
                x = x.forward[i]
            update[i] = x
        return update

    def search(self, key):
        x = self._find_predecessors(key)[0].forward[0]
        return x is not None and x.key == key

    def insert(self, key):
        update = self._find_predecessors(key)
        h = self._random_level()
        self.level = max(self.level, h)
        node = Node(key, h)
        for i in range(h):                       # splice in at each level
            node.forward[i] = update[i].forward[i]
            update[i].forward[i] = node

    def delete(self, key):
        update = self._find_predecessors(key)
        x = update[0].forward[0]
        if x is None or x.key != key:
            return False
        for i in range(len(x.forward)):          # unsplice at each level
            if update[i].forward[i] is x:
                update[i].forward[i] = x.forward[i]
        while self.level > 1 and not self.head.forward[self.level - 1]:
            self.level -= 1
        return True

The update array is the one idea worth staring at: it records, per level, the last node you stood on before dropping down. Those are precisely the nodes whose forward pointers must be rewired to splice a node in or out. Insert and delete are both "run the search, keep the breadcrumbs, rewire." Compare that to the red-black delete you were going to write.

Why O(log n) is the expected bill

The informal argument is short enough to give in an interview. Height first: level k holds about n·pᵏ nodes, so the levels run out when n·pᵏ ≈ 1 — at k ≈ log₁/ₚ(n). For p = 1/4 and a million elements, that's about 10 levels.

Steps per level: walk the search path backwards, from the target up to the head. At each node, ask: was this node's tower taller, letting me climb? That happened with probability p. Or did I arrive here by a horizontal step, because the coin said stop? Probability 1 − p. Each level is therefore a geometric run: on average about 1/p horizontal steps before you get to climb — a constant. Constant work per level, log levels:

Expected search cost, n = 1,000,000:

height        ≈ log_{1/p}(n)
comparisons   ≈ (1/p) · log_{1/p}(n)

p = 1/2:  20 levels × 2 steps  ≈ 40 comparisons, 2.00 pointers/node
p = 1/4:  10 levels × 4 steps  ≈ 40 comparisons, 1.33 pointers/node

Read that twice, because it's the punchline of Pugh's paper: halving p to 1/4 leaves the expected comparison count essentially unchanged while cutting pointer overhead by a third (expected pointers per node is 1/(1−p)). That's why Pugh recommends p = 1/4 for most uses, and why ZSKIPLIST_P is 0.25 and LevelDB's kBranching is 4. The theoretical optimum for pure search steps is p = 1/e, but nobody ships that; the memory savings at 1/4 win.

And the tail is well-behaved. The O(n) worst case requires the RNG itself to misbehave across many independent flips — the bad events are exponentially unlikely, and none of them depend on your keys. A BST degrades to a linked list if an adversary (or an innocent ORDER BY) feeds it sorted input. A skip list cannot be attacked through insertion order, because heights never look at keys. The randomness is a defense, not just a convenience.

Redis: a skip list and a hash map, joined at the hip

Now the production story. A Redis sorted set is, per the docs, "a dual-ported data structure containing both a skip list and a hash table." Every member lives once; both structures point at the same string.

flowchart TD
    CMD1["ZSCORE board alice — O(1)"] --> DICT["dict\nmember → score"]
    CMD2["ZRANK board alice — O(log n)"] --> SL["skiplist\nordered by (score, member)\nspan on every forward pointer"]
    CMD3["ZRANGE board 0 9 — O(log n + 10)"] --> SL
    DICT --> ELE["one shared copy of member string + score"]
    SL --> ELE
    style DICT fill:#0e7490,color:#fff
    style SL fill:#a855f7,color:#fff
    style ELE fill:#22c55e,color:#111
    style CMD1 fill:#1e293b,color:#e2e8f0
    style CMD2 fill:#1e293b,color:#e2e8f0
    style CMD3 fill:#1e293b,color:#e2e8f0

This is the same design move as an LRU cache: no single structure answers both "point lookup by key" and "position in an ordering" well, so you run two structures over shared elements and pay pointers instead of duplication. ZSCORE and ZINCRBY hit the dict. ZRANGE, ZRANGEBYSCORE, and ZRANK hit the skip list. An update touches both, and both operations are cheap, so ZADD stays O(log n).

The skip list inside t_zset.c is Pugh's algorithm with three modifications the source comment spells out: duplicate scores are allowed; ordering compares the score and then the member string (so ties are deterministic and a specific member is findable among equal scores); and level-0 nodes carry a backward pointer, making the bottom lane doubly linked so ZREVRANGE can walk high-to-low without any cleverness.

The fourth modification is the one that answers the interview question. Each forward pointer carries a span: how many level-0 links it jumps over. Sum the spans along the search path and you've computed the node's position — that's ZRANK in O(log n), and it's also how ZRANGE board 0 9 finds the starting element by index instead of by score. In a balanced tree you'd get the same power by augmenting nodes with subtree sizes — and then updating those sizes correctly through every rotation. In a skip list, inserts already rewrite exactly the pointers on the search path, so maintaining spans is a few +1s in code you were touching anyway. Simplicity isn't an aesthetic preference here; it's what made the feature cheap to build.

When antirez (Salvatore Sanfilippo) was asked why not a balanced tree, his stated reasons were exactly these: skip lists aren't memory-hungry and p is a tuning knob; sorted sets spend their lives serving ZRANGE/ZREVRANGE, which are linked-list walks with cache locality at least as good as a tree's in-order traversal; and the implementation is simpler to modify — the span augmentation landed as a small patch.

Worth doing the memory math, since "not memory-hungry" deserves numbers:

Redis skiplist node, 64-bit, p = 0.25 (illustrative):

fixed:     ele pointer 8B + score double 8B + backward 8B   = 24 B
per level: forward pointer 8B + span 8B                     = 16 B
expected levels: 1/(1 - 0.25)                               = 1.33

expected node ≈ 24 + 1.33 × 16                              ≈ 45 B
+ dict entry (key ptr, value, next)                         ≈ 24 B
+ dict bucket array share                                   ≈  8 B

≈ 77 B of structure per member, excluding the string itself.
10M-player leaderboard ≈ 770 MB overhead + member strings.
A red-black node (left, right, parent, color) starts ≈ 32 B
before you add the subtree-size augmentation ZRANK needs.

So the honest verdict: comparable to a tree, tunable downward, and not the reason you'd lose sleep. And for small sets Redis sidesteps the whole thing — a sorted set stays encoded as a flat listpack until it exceeds 128 entries or a 64-byte member (defaults as of mid-2026), because below that size a linear scan of a contiguous buffer beats any pointer structure. Most sorted sets in the wild never grow a single tower.

One caveat to the locality story: the descent is not cache-friendly. Every hop follows a pointer to an unpredictable heap address — at 10 levels and ~4 steps per level, a search touches a few dozen scattered cache lines, roughly like a BST. A cache-optimized in-memory B-tree, which packs many keys per node into consecutive lines, will beat both on raw search throughput. The skip list's locality win is specifically the level-0 range walk, which happens to be the operation sorted sets serve most. Redis chose correctly for its access pattern, not universally — and antirez's claim was scoped exactly that way.

The concurrency story: memtables and ConcurrentSkipListMap

The second production home for skip lists is the write path of LSM-tree storage engines. LevelDB and RocksDB buffer incoming writes in a memtable — an in-RAM sorted structure that absorbs random writes and is periodically flushed to disk as a sorted run.

flowchart LR
    W["writes"] --> MT["memtable\n(skip list, in RAM)"]
    MT -->|"full — flush"| SST["immutable SSTable\n(sorted file on disk)"]
    SST --> COMP["compaction merges runs"]
    style W fill:#1e293b,color:#e2e8f0
    style MT fill:#00e5ff,color:#111
    style SST fill:#374151,color:#fff
    style COMP fill:#374151,color:#fff

A memtable needs exactly a skip list's strengths: fast ordered inserts, a full sorted scan at flush time, and reads running concurrently with writes. LevelDB's skiplist.h (kMaxHeight = 12, kBranching = 4) states the contract in its header comment: writes require external synchronization, but reads only require that the skip list outlive them — they proceed with no locking at all. It works because an insert is a publication: build the node fully, then swing predecessor pointers with release-store atomics so any reader doing an acquire-load sees either the old list or a completely initialized node. Never a half-state. Try writing that guarantee for a red-black rotation, where a structural change touches several existing nodes at once and temporarily violates the tree's own invariants. RocksDB ships skiplist as its default memtable, and its docs note that concurrent memtable insert is enabled by default and skiplist is the only memtable type supporting it.

Java reached the same conclusion for general-purpose code. ConcurrentSkipListMap — the JDK's standard concurrent ordered map — documents itself as "a concurrent variant of SkipLists" with expected average log(n) cost for get, put, and remove, safe under full multi-threaded mutation with weakly consistent iterators. There is no ConcurrentRedBlackTreeMap, and that absence is the argument: CAS-ing a couple of forward pointers is a tractable lock-free design; coordinating rotations across threads is a research problem. The usual fine print applies — bulk operations aren't atomic, and counting elements means traversing them, since a lock-free design has no cheap globally consistent counter to maintain.

Skip list vs. the alternatives

{ "type": "bst", "title": "the balanced-tree alternative: same O(log n) search, plus rotation machinery you now own", "data": [26, 9, 42, 3, 17, 30, 50] }

	Skip list	Red-black / AVL tree	B-tree / B+ tree	Hash table
Search	O(log n) expected	O(log n) guaranteed	O(log n) guaranteed	O(1) average
Insert / delete	O(log n) expected, splices only	O(log n) + rotations	O(log n) + node splits	O(1) average
Range scan (k items)	O(log n + k), walk level 0	O(log n + k), needs stack or parent pointers	Excellent — keys packed per node	Unsupported
Rank / k-th element	O(log n) with spans (cheap to add)	Needs subtree-size augmentation through rotations	Needs augmentation	Unsupported
Concurrency	Lock-free friendly — local pointer publication	Hard — rotations touch shared ancestors	Lock coupling, well-studied	Excellent (striping)
Cache / disk behavior	Poor descent, good level-0 scan; RAM-only	Poor — pointer chase	Best in class; the on-disk default	Great for point lookups
Worst case	O(n), RNG-dependent, key-independent	O(log n)	O(log n)	O(n) under collision attack
Implementation	~40 lines	Hundreds of lines, hard delete	Substantial	Small–medium

The pattern in that table: the skip list never wins a column outright except implementation size and concurrency-friendliness — and those two turn out to decide real systems more often than asymptotic elegance does. Where a column really matters on its own, a different structure takes it: B+ trees own the disk (every serious database index), balanced BSTs own hard latency guarantees, hash tables own pure point lookup. And if all you need is repeated access to the max element, skip the ordering entirely and use a heap.

What breaks

A quiet RNG failure degrades you to O(n) with no error message. Heights don't depend on keys, so nothing in your data can flatten a skip list — but your own code can. A stubbed random source in tests, a misconfigured p, or a copy-paste that compares against the wrong threshold produces a structure that still returns correct answers, just linearly. Nothing crashes; your p99 does. If you implement one, assert on the observed height distribution in a test with a few hundred thousand inserts.

Deleting at level 0 only. The classic implementation bug: unsplice the node from the bottom list and forget the upper levels. The update array exists precisely because a node must be unspliced at every level it appears in. Miss one and a later search follows a forward pointer into freed memory (C) or resurrects a deleted key (everywhere). If your skip list "sometimes finds deleted elements," this is why.

Duplicate keys without a tiebreaker. Compare by score alone and two members with equal scores become indistinguishable to the search path — delete may unsplice the wrong node's pointers at some levels and corrupt the list. Redis's fix is in the ordering itself: compare (score, member) lexicographically, so every element has a unique position. If your keys can collide, your comparator needs a second component. Not optional.

Using it where cache or disk dominates. Each level hop is a dependent load from a random address. On disk that's a seek per hop — catastrophically wrong, which is why mainstream on-disk indexes are B+ trees and every LSM engine flushes its skip-list memtable into flat, block-indexed SSTables. Even in RAM, if your workload is search-heavy point lookups over a mostly-static set, a cache-aware layout (sorted array, B-tree) will beat you on throughput.

Trusting "expected" where you promised "guaranteed." The concentration bounds are genuinely strong — meaningfully degenerate structures are astronomically unlikely at real sizes — but a hard real-time system that must bound every operation can't cite probability in the postmortem. That's the one argument that legitimately sends you back to a red-black tree.

The interview answer, done properly

"Why did Redis pick a skip list over a balanced tree?" is the modern phrasing of "tell me about balanced search trees," and it deserves a real answer, not "skip lists are simpler." Structure it as the requirements, then the fit.

A sorted set needs four things: O(1) score lookup by member, O(log n) insert/update, range queries by score and by rank, and cheap ordered iteration both directions. No single structure delivers the first plus the rest, so Redis runs a dict and a skip list over shared elements — the point-lookup requirement is answered before the tree-vs-skip-list debate even starts. Within the ordered half: range scans are level-0 pointer walks (with backward pointers for ZREVRANGE); rank queries come from span-augmented pointers, an augmentation that costs a few lines in a skip list but must survive every rotation in a tree; memory is tunable and lands around 1.33 forward pointers per node at p = 1/4; and the worst case a tree protects against can't be triggered by input order anyway, because heights are key-independent. Redis is also single-threaded on the data path, so the tree's one decisive advantage — guaranteed worst-case bounds under any interleaving — buys little. Every remaining consideration points the same direction.

Then show you know the boundaries, because that's what separates the memorized answer from the earned one. Choose a skip list when you're building a concurrent ordered map or an LSM memtable, when you need rank/order statistics without augmentation pain, or when you genuinely must implement and maintain the structure yourself. Choose a balanced BST when worst-case guarantees are contractual. Choose a B+ tree the moment data touches disk or search throughput over cold caches is the metric. And in application code, choose whatever ordered map your language ships — which, if you're on the JVM and need it concurrent, is a skip list anyway.

The meta-lesson is the one worth carrying out of the interview: Redis didn't pick the structure with the best worst case. It picked the one whose simplicity made the next feature — spans, backward pointers, score-and-member ordering — a small patch instead of a rewrite. Data structure choices compound. The coin flip wasn't the clever part; knowing what the rotations would have cost later was.