Data structures · 14 min

Skip list

Keep a million-player leaderboard in score order and find any score in about 40 steps, using a linked list, some extra lanes and a coin.

Your game has a leaderboard with a million players, kept in score order. Every few milliseconds a match ends and someone’s new score has to slot into the right place.

Finding that place is the hard part. This article gets there in four attempts. The first is obvious and slow; each one after fixes the last one’s problem.

Attempt 1: one long chain of players

A plain sorted array is out. Putting a new score in the middle means shifting every entry after it one slot along, and that can be a million moves.

So use a sorted linked list instead. The new player sakura scores 99. Once you know she goes between mio (96) and kenji (104), adding her is cheap: mio now points to sakura, and sakura points to kenji.

But to find that spot, you start at the lowest score and follow pointers one by one, comparing each score with 99. You can’t jump to the middle, because each item only knows the next one. With a million players that is half a million comparisons on average. Cheap inserts, slow finds.

Attempt 2: add an express lane

A subway line fixes the same problem with an express train. It stops only at some stations. You ride it most of the way, then switch to the local train for the last few stops.

Do the same here. Keep the full chain as level 1. Above it, build level 2: a second chain that links only every other player. To find 99, run along level 2 until the next stop would pass 99, then step down to level 1 and walk the last stretch.

Level 2 holds 500,000 players. On average you walk half of them, 250,000, plus a step or two on level 1. That is half the work of attempt 1. Better, but still far too many.

Attempt 3: lanes on top of lanes

If one express lane halves the work, add another. Level 3 links every other player from level 2, level 4 every other player from level 3, and so on, until the top level holds a single player.

Halve a million 20 times and about 1 player is left, because 2²⁰ is 1,048,576. So there are about 20 express levels above level 1.

A search starts on the top level, on the left, and works down. When it drops to a level, the level above has already brought it to just before the next express stop. On this level that stop is only 2 players away, because the express level kept every other player. So the search looks at no more than 2 scores per level: at most one step right, then one score that is too big. About 20 levels × 2 is about 40 comparisons, instead of half a million.

The wall: someone new joins

Attempt 3 is fast to search, but it depends on a perfect pattern: exactly every other player goes up a level. Now sakura arrives with 99.

Re-arranging existing items to restore a pattern is called rebalancing. Here it costs as much as the slow search we were trying to avoid. The perfect pattern is the problem.

Attempt 4: let a coin decide

This is the step that makes it a skip list. Drop the rule “every other player”. Instead, each player builds their own tower when they join, by flipping a coin:

1. Every player is on level 1.
2. Flip a coin. Heads: also join level 2. Tails: stop.
3. After each heads, flip again. Each heads adds one more level; the first tails stops it.
4. Hook the tower in: on each of its levels, redirect the player before it to point at the new player, and point the new player at the one after.

About half the players get heads on the first flip, so about half reach level 2. Half of those get heads again, so about a quarter reach level 3. That is roughly the shape of attempt 3, but no tower depends on its neighbours.

When sakura joins, she flips her own coins and nobody else changes. When a player leaves, you unhook their tower and nobody else changes either.

Searching works as before: start at the top level on the left, move right while the next score is smaller than the one you want, and drop down a level when it is bigger or the level ends. If the next score is exactly the one you want, on any level, you have found it and can stop.

Joining and leaving, step by step

Every search begins at start: a fixed header before the lowest score, with a slot on every level. Adding sakura (99) is that same search plus a little bookkeeping:

1. Search down from the top level. On each level, remember the last player before 99, or start if no one on that level comes before 99. Their pointers are the ones that will change.
2. Flip coins to pick her tower’s height. If it is taller than any tower so far, start grows a new, empty level, and start’s slot is what gets remembered there.
3. Splice her in, from level 1 upward. On each level of her tower, the remembered player now points to her, and she points to the player it used to point to. That is 2 pointers written per level: one redirected, and one new pointer of her own.

Removing a player runs the same search. The search first meets the leaver on their top level, so from there down you know their tower and remember the player (or start) just before them on each level. On each of those levels, that player now points to whoever the leaver pointed to, skipping over them. The leaver’s own pointers are thrown away with it, so nothing else is written. If the leaver was alone on the top level, that level is now empty, and start drops it.

Why a million players get about 20 express levels

Follow the coin through a million players. To reach a level, a player needs one more heads in a row than for the level below, so each level keeps about half:

How many scores does a search look at on each level? It is the same gap as in attempt 3, now set by coins. Flip a coin 100 times and you get about 50 heads, so a heads turns up about every 2 flips. In the same way, about every second player on a level also reaches the level above, so the next express stop is about 2 players away. You look at about 2 scores before one is too big and you drop.

Put together: about 2 comparisons on each of about 20 levels is about 40 comparisons for a million players. For n players the rough rule is 2 × log₂ n.

Check it against the demo. 2¹⁶ is 65,536 and 2¹⁷ is 131,072, so log₂ 100,000 is between 16 and 17, about 16.6. The rule gives 2 × 16.6 = 33.2, and the demo measured 35.0. For 1,000 players (log₂ about 10) the rule gives 20 and the demo measured 17.1. Both numbers are in the “At real sizes” table under the demo. The rule is a rough guide, off by a few either way.

The whole thing in code

Search, add and remove share one loop. The part to notice is that it remembers the last player it passed on each level, because those are the pointers add and remove have to change. start is the header from the demo, and top is the tallest tower so far.

find(score):
    x = start
    for level in top .. 1:              # top level first
        while x.next[level] and x.next[level].score < score:
            x = x.next[level]           # move right
        before[level] = x               # then drop down
    x = x.next[1]
    return x if x and x.score == score else none

add(player):
    find(player.score)                  # fills before[]
    height = 1
    while flip_coin() == heads:
        height += 1
    if height > top:                    # a new tallest tower
        for level in top+1 .. height:
            before[level] = start
        top = height
    for level in 1 .. height:           # hook in, level by level
        player.next[level] = before[level].next[level]
        before[level].next[level] = player

remove(score):
    x = find(score)                     # fills before[]
    if x is none: return
    for level in x.height .. 1:         # unhook, top level first
        before[level].next[level] = x.next[level]
    while top > 1 and start.next[top] is none:
        top -= 1                        # drop an empty top level

Where real leaderboards keep their scores

Redis is an in-memory database that many games use for exactly this job. Its sorted sets keep members ordered by score. Once a sorted set grows past 128 members (the default setting), Redis stores it as a skip list plus a hash table (the structure behind a map).

The hash table answers “what is aoi’s score?” in one lookup. The skip list answers “where does 99 go?” and “who are the top 10?” in a few dozen steps, even with millions of members.

Redis tunes the coin: it comes up heads only 1 time in 4. For 1,000 members that is about 1,000 + 250 + 63 + 16 + 4 + 1 ≈ 1,334 pointers, about 1.33 each instead of 2. Searches take a few more steps, but memory is what an in-memory database runs short of first.

• LevelDB and RocksDB are databases that store data on disk in sorted files. New writes arrive fast and must stay sorted until they are saved, so they collect in an in-memory skip list first.
• Java’s ConcurrentSkipListMap is a sorted map many threads can update at once. An insert touches only the pointers next to its own tower, so two threads adding far-apart scores don’t get in each other’s way.

So when a collection has to stay sorted while things join and leave all the time, a skip list gives you a linked list’s cheap inserts and search in about 2 × log₂ n steps. The only balancing it ever does is a coin flip.