./ahmedhashim

Consider the Skip List

If you need sorted data with quick lookups and inserts, you’d probably think of a balanced tree, which is great if you’re given one by a library. If you’re trying to code one yourself, it’s a whole different story. Rotations are what keep it balanced, and that’s where all your edge cases come from.

William Pugh stated this in his original skip list paper:

implementing balanced trees is an exacting task and as a result balanced tree algorithms are rarely implemented except as part of a programming assignment in a data structures class.

There are times where you do not need a tree. Using a skip list can give you the same time complexity of O(log n) and with much less code.

Express lanes

A skip list is simply a sorted linked list with additional levels that act as fast lanes. All values will be in the bottom-most list. Each list above contains fewer values than the list below it, which means each hop on a higher list skips over more nodes on the lists below it.

Start from the top and go right until the next value is greater than your target. Then go down one level and repeat until you get to the bottom. Each time you go down a level, you cut your search space roughly in half, similar to binary search.

We’ll be searching for 47 in the skip list below, going level by level. From the top lane we jump straight to 19:

  flowchart TD
    subgraph L2["Level 2"]
        direction LR
        H2["HEAD"] --> B2["19"] --> N2["NIL"]
    end
    subgraph L1["Level 1"]
        direction LR
        H1["HEAD"] --> A1["7"] --> B1["19"] --> C1["47"] --> N1["NIL"]
    end
    subgraph L0["Level 0"]
        direction LR
        H0["HEAD"] --> V3["3"] --> A0["7"] --> V12["12"] --> B0["19"] --> V30["30"] --> C0["47"] --> V52["52"] --> N0["NIL"]
    end
    L2 ~~~ L1
    L1 ~~~ L0
    classDef seen stroke:#5ea1ff,stroke-width:2px
    classDef cur fill:#5ea1ff,stroke:#5ea1ff,color:#16181a
    class H2 seen
    class B2 cur

Nothing after 19 on the top row helps, so it falls down to level 1. We see that 47 is our next value, but the walk only asks if the next value is less than what we’re looking for.

  flowchart TD
    subgraph L2["Level 2"]
        direction LR
        H2["HEAD"] --> B2["19"] --> N2["NIL"]
    end
    subgraph L1["Level 1"]
        direction LR
        H1["HEAD"] --> A1["7"] --> B1["19"] --> C1["47"] --> N1["NIL"]
    end
    subgraph L0["Level 0"]
        direction LR
        H0["HEAD"] --> V3["3"] --> A0["7"] --> V12["12"] --> B0["19"] --> V30["30"] --> C0["47"] --> V52["52"] --> N0["NIL"]
    end
    L2 ~~~ L1
    L1 ~~~ L0
    classDef seen stroke:#5ea1ff,stroke-width:2px
    classDef cur fill:#5ea1ff,stroke:#5ea1ff,color:#16181a
    class H2,B2 seen
    class B1 cur

It isn’t, so we fall down again without traveling and save that equality check for when we reach the bottom. Back in our list of all values, we go to 30 and then 47. So out of 7 values, we only visited 3:

  flowchart TD
    subgraph L2["Level 2"]
        direction LR
        H2["HEAD"] --> B2["19"] --> N2["NIL"]
    end
    subgraph L1["Level 1"]
        direction LR
        H1["HEAD"] --> A1["7"] --> B1["19"] --> C1["47"] --> N1["NIL"]
    end
    subgraph L0["Level 0"]
        direction LR
        H0["HEAD"] --> V3["3"] --> A0["7"] --> V12["12"] --> B0["19"] --> V30["30"] --> C0["47"] --> V52["52"] --> N0["NIL"]
    end
    L2 ~~~ L1
    L1 ~~~ L0
    classDef seen stroke:#5ea1ff,stroke-width:2px
    classDef found fill:#5eff6c,stroke:#5eff6c,color:#16181a
    class H2,B2,B1,B0,V30 seen
    class C0 found

Inserts

An insert starts with the same walk. To place 40, we drop at 19 on the 2nd level, drop at 19 on the 1st level, and step over to 30 on the bottom. We stop because 47 is greater than 40. As we drop, we keep track of every node we drop at, since our new value will be inserted after these nodes:

  flowchart TD
    subgraph L2["Level 2"]
        direction LR
        H2["HEAD"] --> B2["19"] --> N2["NIL"]
    end
    subgraph L1["Level 1"]
        direction LR
        H1["HEAD"] --> A1["7"] --> B1["19"] --> C1["47"] --> N1["NIL"]
    end
    subgraph L0["Level 0"]
        direction LR
        H0["HEAD"] --> V3["3"] --> A0["7"] --> V12["12"] --> B0["19"] --> V30["30"] --> C0["47"] --> V52["52"] --> N0["NIL"]
    end
    L2 ~~~ L1
    L1 ~~~ L0
    classDef seen stroke:#5ea1ff,stroke-width:2px
    classDef mark fill:#5ea1ff,stroke:#5ea1ff,color:#16181a
    class H2,B0 seen
    class B2,B1,V30 mark

Randomness will determine how high it goes. It begins at the lowest level and is promoted to the next level if a random event allows it. This process continues until it fails which then places the node at that level. In this case it was promoted 2 times allowing it to be placed in the top level. We can now insert it into the skip list. For each level we have the previous remembered node pointing to 40 and 40 pointing to where the previous remembered node pointed. All levels remain sorted and no other nodes have changed position:

  flowchart TD
    subgraph L2["Level 2"]
        direction LR
        H2["HEAD"] --> B2["19"] --> X2["40"] --> N2["NIL"]
    end
    subgraph L1["Level 1"]
        direction LR
        H1["HEAD"] --> A1["7"] --> B1["19"] --> X1["40"] --> C1["47"] --> N1["NIL"]
    end
    subgraph L0["Level 0"]
        direction LR
        H0["HEAD"] --> V3["3"] --> A0["7"] --> V12["12"] --> B0["19"] --> V30["30"] --> X0["40"] --> C0["47"] --> V52["52"] --> N0["NIL"]
    end
    L2 ~~~ L1
    L1 ~~~ L0
    classDef ins fill:#5eff6c,stroke:#5eff6c,color:#16181a
    class X2,X1,X0 ins

It’s random. That’s what you use to balance it. Half the nodes stay on the bottom, a quarter get to the first level, and an eighth make it to the second level. There’s no need to rebalance. By randomly promoting, you’re achieving what the rotations do. This is what Pugh means by probabilistic balancing.

Implementation

The entire thing can be done in less than 50 lines of Python:

import random

MAX_LEVEL = 16
P = 0.5


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


class SkipList:
    def __init__(self):
        self.head = Node(None, MAX_LEVEL)
        self.level = 1

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

    def search(self, value):
        node = self.head
        for i in reversed(range(self.level)):
            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

    def insert(self, value):
        update = [self.head] * MAX_LEVEL
        node = self.head
        for i in reversed(range(self.level)):
            while node.forward[i] and node.forward[i].value < value:
                node = node.forward[i]
            update[i] = node

        level = self._random_level()
        self.level = max(self.level, level)
        node = Node(value, level)
        for i in range(level):
            node.forward[i] = update[i].forward[i]
            update[i].forward[i] = node

search just follows the path from our diagram: go right if the value to the right is too small, and go down a level otherwise. insert does the same walk but keeps track of where you went down at each level (update), and inserts your new node into all the levels its random height allows for. You could implement delete by doing the same walk as insert, but unsplicing the nodes instead.

No rotations and no balance factor, so you can’t really screw it up. A MAX_LEVEL of 16 covers 2^16 elements, so just base it off the log of the number of elements you expect to have.

Use Cases

Say you want to create an in-memory leaderboard, with millions of entries, where you need to look up a rank or a range of ranks. You could use a balanced tree. But Redis sorted sets use a skip list. When asked why he didn’t use B-trees, antirez answered:

  1. They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make [them] less memory intensive than btrees.

  2. A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.

  3. They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

This last point is the one I’d stress the most. It was easy to extend by someone who knew nothing about the data structure, and it was put into production.

Concurrency tilts things further. Inserting into a tree can cause rotations far away from the original insertion point, which is difficult to lock. Inserting into a skip list only modifies a few adjacent nodes. That’s why java.util.concurrent has a ConcurrentSkipListMap and not a concurrent red-black tree.

Tradeoffs

It’s not guaranteed to be fast, though. If you get unlucky with promotions, your list can end up flat, and you’re forced into an O(n) scan. Pugh calculated the chance of a search taking three times longer than expected at 4,096 items: less than 1 in 200 million. That’s great for a server, but not good enough for a hard real-time system, where you want a tree’s worst-case guarantee.

Memory is comparable to a tree and you can adjust it (which was antirez’s first point). For every level a node reaches, it takes 1 forward pointer. With a 1/2 chance of promotion you will have 2 pointers per node on average which is the same as a tree. If you decrease the chance to 1/4 you will have 1.33 pointers on average and your search will be a bit faster as well. This is why Pugh suggests 1/4.

The real cost is where the nodes live in memory. Each node is at its own memory address, so when you’re searching through it you’re jumping around, and each time you jump, you risk a cache miss. With B-trees you have many values in each node, so when you’re doing a search you’re pulling in a big sorted chunk of data at once. When you’re dealing with disk this jump becomes even more of an issue, which is why B-trees should be used for data on disk and the hottest code paths.

The other weakness is finding positions. Asking for the 500th item in a list takes a while, since you have no idea how many elements your pointer jumps over. You could store this on each link, but then you’d need to do the same with a tree. So it’s a wash.

None of that changes the headline. Skip lists give you tree-like performance in memory for linked-list effort, especially when you’re the one who has to build and debug it. If you’re ever dealing with sorted data and thinking about rotations, try randomness instead.