Skip lists

How a sorted list of a million names can be searched in about 20 hops

A skip list is a sorted linked list with express lanes stacked on top. In a plain linked list, each item points only to the next one, so finding one name among a million can mean walking through most of them.

When an item is added, the skip list flips a coin. On heads, the item also joins the lane above, and it keeps flipping until it gets tails. The bottom lane holds every item, the next about half, the next about a quarter, and so on.

To search, you start in the top lane and move right while the next item is still smaller than your target. Then you drop down a lane and repeat until you land on the item.

Skip lists

Redis sorted sets, used for game leaderboards, are built on skip lists

Redis, a popular in-memory database, stores larger sorted sets as a skip list plus a hash table. Sorted sets keep members ordered by score, so games use them for leaderboards: add a score, then read the top 10.

LevelDB and RocksDB, storage engines used inside many databases, also keep newly written keys in an in-memory skip list, called the memtable, before writing them to disk in sorted order.

Skip lists

Coin flips build express lanes that let a search skip most of the list

Each lane holds about half the items of the lane below. So in each lane a search moves only about two steps on average before dropping down. About log₂(n) lanes times a couple of steps gives O(log n) search, insert and delete on average.

Inserting needs no global rebalancing, unlike balanced search trees: flip coins for the new item's height and fix the pointers beside it in each lane. Local changes also suit multithreaded code, as in Java's ConcurrentSkipListMap.

The cost is randomness. An unlucky run of coin flips could make the list slow, but that is very unlikely for large lists. With p = 1/2, each item stores about 2 pointers on average.