Skip List
A sorted linked list is easy to keep sorted and slow to search. Give every node a height chosen by coin flips, and let the nodes of each height form a sparser sorted list stacked above the full one: express lanes. A search starts at the top, runs right while the next key is still too small and drops a level when it is not, so it skips most of the bottom list. Half the nodes reach each next level on average, which makes search, insert and delete O(log n) expected, with no rotations and no rebalancing; an insert changes a handful of pointers on the search path and nothing else, which is why concurrent ordered maps are usually skip lists.
Search for 44. The bottom row L0 is the whole sorted list; each row above keeps only the nodes tall enough to reach it, and the head on the left reaches every level. Start at the top of the head, run right while the next key is below 44, and drop a level when it is not. Every drop halves the stretch still to scan, on average.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 2, with their answers.
On level 3 the next key is none and the target is 44. What now?
Answer: Drop a level: the next key is past the target. Run right while the next key is smaller than the target; otherwise drop, and at the bottom the next key decides.
On level 2 the next key is 44 and the target is 44. What now?
Answer: Stop: the next key is the target. Run right while the next key is smaller than the target; otherwise drop, and at the bottom the next key decides.
How it runs, step by step
Search for 44. The bottom row L0 is the whole sorted list; each row above keeps only the nodes tall enough to reach it, and the head on the left reaches every level. Start at the top of the head, run right while the next key is below 44, and drop a level when it is not. Every drop halves the stretch still to scan, on average.
Searching a skip list of 9 keys for 44.
Level 3 at the head: the next key on this lane is nothing, the end of the lane. It is not below 44, so drop to level 2 and keep looking from here.
Level 3: Drop a level: the next key is past the target.
Level 2 at the head: the next key on this lane is 44. That is 44: found, after 2 comparisons.
Level 2: Stop: the next key is the target.
44 found after 2 comparisons, against up to 9 in a plain sorted list. The express lanes are what make the difference: with heights chosen by coin flips, about half the nodes reach each next level, so a search does O(log n) work on average, and the structure never needs rebalancing. The seed decides the flips here; a different seed draws different lanes.
Found 44.
Remember
- Run right while the next key is below the target; drop a level when it is not; the bottom decides.
- Heights come from coin flips: half the nodes reach each next level, so lanes thin out geometrically.
- Insert is a search that remembers its path, then a splice on every level the new node reaches.
Topics covered
Where this is used
DatabasesRedis sorted sets
Above a small size threshold a Redis sorted set is a hash map from member to score for O(1) ZSCORE, paired with a skip list ordered by score so ZRANGE and ZRANGEBYSCORE can start anywhere and walk the bottom lane in order. Redis also stores a span on each forward pointer, the number of bottom nodes that pointer jumps, so one top-down descent adds the spans it follows and answers ZRANK without counting nodes one at a time.
Storage enginesLevelDB and RocksDB memtables
The in-memory write buffer of an LSM engine is a skip list. It has to absorb writes at full speed and still be readable in sorted key order at any instant, so the buffer can be flushed straight out as a sorted file, which rules out a hash table. LevelDB's version takes one externally synchronized writer and any number of concurrent readers that need no internal locking at all, because an insert only publishes new forward pointers and never moves or rewrites an existing node.
ConcurrencyConcurrentSkipListMap in the JDK
Java's lock-free sorted map is a skip list rather than a tree. Splicing a node in is one compare-and-swap per level on a single next pointer, so threads working on different parts of the key range never contend, and a reader crossing a half-finished insert still sees a well-formed list. Index levels are linked in a pass after the bottom one, and that pass can rarely fail outright, so a node may stay reachable only at level 0; the cost is a longer walk, never a wrong answer. HBase's in-memory store is built directly on this class.
SearchSkip data inside Lucene posting lists
A posting list is the sorted list of document ids that contain a term, and an AND query repeatedly advances one list to the first id at or past a target from another. Lucene writes multi-level skip data beside each long posting list so that advance jumps over whole blocks instead of decoding every id in between. The lanes are built deterministically at index time rather than by coin flips, but the search is the same move-right-then-drop.
Why it works this way
Why coin flips instead of a balance rule?
A node's height comes from a coin, so the shape of the lanes depends on your random numbers and not on the order the keys arrived. That is what buys O(log n) with no rotations: there is no arrangement of inputs that is bad for you, so there is nothing to rebalance. The price is that the bound is expected rather than guaranteed - an unlucky run of flips can leave a search walking a long stretch of the bottom list, which is vanishingly rare at any real size but never impossible.
Choosing the promotion probability and the height cap
With promotion probability p, each node carries 1/(1-p) forward pointers on average and a search costs about (1/p) x log base 1/p of n comparisons. That product comes out the same for p = 1/2 and p = 1/4, but 1/4 stores about 1.33 pointers per node instead of 2 and builds half as many levels, so Redis and LevelDB both use 1/4 and accept a little more variance in search time. The cap matters too: set it near log base 1/p of the largest n you expect (Redis caps at 32, LevelDB at 12), because a cap set too low crowds every tall node into the top lane and the first stretch of each search turns linear.
The trap: stopping at the level where the key first matches
It is tempting to return true the moment x.next[level].key == key part way down. For a pure search that is correct and saves a few drops, but for insert and delete it is a real bug: those need update[level], the last node before the key, at every level, and you only have the full path once the descent reaches the bottom. Size update[] for maxLevel and start it at head, not at the list's current level, since a new node can be taller than anything present and the head is its predecessor on those lanes.
Why isn't every in-memory index a skip list?
Every comparison is a pointer dereference into a node that may be anywhere in memory, so one search touches a few dozen scattered addresses and pays a cache miss for most of them. A B-tree packs dozens of keys contiguously into each node, so one miss brings in a run of keys the next several comparisons all read, and its single-threaded lookups measure faster on the same data. The skip list is not paying for read speed. It is paying for a write path where the nodes that change are exactly the ones the search already visited, which is what a rotation gives up: a rotation rewrites pointers far from the key you touched, so it has to exclude readers that were nowhere near it.
Read more
- Skip Lists: A Probabilistic Alternative to Balanced TreesPugh, CACM 1990 · 15721.courses.cs.cmu.edu
- Skip listWikipedia
- Redis sorted setsRedis
- leveldb/db/skiplist.hLevelDB · github.com
- ConcurrentSkipListMapJava 21 API · docs.oracle.com