Skip list: an interactive visualization of search and express lanes

A skip list is a sorted linked list with express lanes. Every key is on the bottom level; about half are also on the level above, a quarter on the level above that, and so on, decided by coin flips. A search runs along the sparse top lane and drops down as it gets close, so finding, inserting and deleting take O(log n) steps on average, with no rebalancing. Redis sorted sets, the memtables of LevelDB and RocksDB, and Java’s ConcurrentSkipListMap are skip lists.

The playground draws a skip list as a grid, keys across and levels up. Pick how many keys and how likely a promotion is, flip the coins again, and click a key on the bottom level to search for it.

Search and insert

A search starts at the top of the head and moves right while the next key on that lane is smaller than the target; when the next key is too big, or the lane ends, it drops a level. On the bottom level the next key is the target, or the target is absent. An insert does the same walk, remembering the last node it passed on each level, flips coins to choose the new key’s height, and splices it into those levels. Only the neighbouring pointers change, which is why skip lists are a favourite for concurrent, lock-free sorted maps.

Why coin flips are enough

With promotion probability 1/2, the expected height is about log₂ n and a search makes about 2 log₂ n comparisons: around 40 for a million keys, against 500,000 for walking a list. Each key carries 2 forward pointers on average. With probability 1/4 the expected search is about the same, since lanes are sparser but there are fewer of them, and keys carry only 1.33 pointers, which is why Redis uses 1/4. Bad luck is possible but rare: the chance of a search much slower than average falls off exponentially.

On small lists the express lanes do not pay: in the playground, 32 keys average 8.9 comparisons against 16.5 for the linked list, but 8 keys can take more comparisons than walking them. Redis stores small sorted sets, up to 128 entries by default, as a flat packed list and switches to a skip list beyond that.

A skip list insert in code

import random

class Node:
    def __init__(self, key, level):
        self.key, self.next = key, [None] * level

def insert(head, key, p=0.5):
    """head is a Node with a pointer for every possible level."""
    update, node = [], head
    for lvl in reversed(range(len(head.next))):       # top lane down
        while node.next[lvl] and node.next[lvl].key < key:
            node = node.next[lvl]
        update.append(node)                            # last node before key, per lane
    update.reverse()
    level = 1
    while random.random() < p and level < len(head.next):
        level += 1                                     # flip coins for the height
    new = Node(key, level)
    for lvl in range(level):                           # splice in: only local pointers change
        new.next[lvl], update[lvl].next[lvl] = update[lvl].next[lvl], new

Redis sorted sets put this behind commands. Each lane pointer also stores how many keys it skips, so rank queries are O(log n) too:

ZADD leaderboard 4200 alice 3900 bob 5100 carol
ZINCRBY leaderboard 300 bob                 # O(log n): find, unlink, reinsert
ZRANGE leaderboard 0 9 REV WITHSCORES       # top 10: a walk along level 1
ZREVRANK leaderboard bob                    # O(log n), from spans kept on the lanes

In a system design interview

Skip lists come up through Redis: “The leaderboard is a Redis sorted set, a skip list plus a hash from member to score, so a score update and a rank lookup are both O(log n), and the top 100 is a short walk along the bottom level. Ten million players fit in a few gigabytes on one shard; beyond that we shard by score range or keep exact ranks only for the top.” Expect the follow-ups: why not a B-tree in a database, how to rank across shards, and how ties are ordered.

Read the guide to skip lists and sorted sets or Redis data structures, compare the B-tree and the LSM tree, whose memtable is often a skip list, or watch a strong candidate design a leaderboard.

Questions people ask