Engineering Atlas › System Design Fundamentals

Skip lists: fast ordered lookups

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

Levels

Level 0 is an ordinary sorted linked list of every element. Each node also appears at level 1 with probability p, at level 2 with probability p^2, and so on, up to a maximum level. A head sentinel has pointers at every level. With p = 1/2, level 1 holds about half the nodes, level 2 a quarter, and the top level a handful. The tallest level is about log_(1/p)(n): 20 levels for a million elements at p = 1/2, 10 at p = 1/4.

A node's level is decided once, at insert, by flipping a biased coin until it fails. That is the whole balancing scheme: randomness keeps the structure balanced in expectation regardless of insertion order. The tail is thin: Pugh showed that once a list holds more than 250 elements, the chance a search takes over three times the expected time is below one in a million (Pugh 1990).

Search

Start at the head on the top level and move right while the next key is less than the target; otherwise drop a level. At level 0 the next node is the target or proof it is absent. Each level costs about 1/p steps, roughly 2 log2(n) comparisons in total at p = 1/2.

Insert and delete

Search for the key, recording the last node visited at each level: the predecessors. Choose a random level and splice the new node in after its predecessor at each of its levels. Deletion unlinks the node using the same predecessors. Nothing else moves.

Choosing p

Expected pointers per node are 1 / (1 - p): 2 at p = 1/2, 1.33 at p = 1/4, which trades memory for slightly longer searches. Pugh's own advice was p = 1/4 unless the variability of running times matters most, and production engines follow it: Redis (ZSKIPLIST_P 0.25, server.h), LevelDB (kBranching = 4, skiplist.h) and RocksDB (branching factor 4, max height 12, inlineskiplist.h). LevelDB and RocksDB cap height at 12 because a memtable is small; Redis caps it at 32.

Ranges and ranks

Range queries are natural: search for the lower bound, then walk level 0 until the upper bound. Redis extends each forward pointer with a span, the number of level-0 nodes it skips, so it can compute a member's rank or jump to the k-th element in O(log n). That is how ZRANK and ZRANGE ... LIMIT stay fast on sorted sets with millions of members.

Concurrency

Inserting into a skip list is a sequence of independent single-pointer updates from the bottom level up. Each can be done with a compare-and-swap, and a node is logically present as soon as it is linked at level 0. Readers never block and see either the old or new pointer. Deletion first marks the node, then unlinks it. Java's implementation does the marking by CAS-ing a special marker node in after the victim, so no concurrent insert can slip in behind it, a technique it credits to Tim Harris and Keir Fraser's lock-free list work (OpenJDK source). Balanced trees need rotations that touch several nodes at once, which is why lock-free trees are rare and lock-free skip lists are common.

Down the stack

Layer 1The contract

A skip list is an ordered map: point lookups, inserts, and deletes in expected O(log n), and in-order iteration from any key. The bounds are probabilistic, so a specific operation can be slower, though large deviations are vanishingly rare. Java's ConcurrentSkipListMap adds lock-free thread safety with weakly consistent iterators, which never throw but may or may not reflect concurrent changes (Java 21 docs). Older material says its size() walks the list in O(n); that was true in Java 8, but current JDKs keep a LongAdder counter, so size() is cheap. It is still only a moment-in-time estimate while other threads write.

Layer 2The mechanism

Redis's zskiplistNode holds a double score, a backward pointer for reverse iteration, and a variable-length array of levels, each a forward pointer plus a span. ZSKIPLIST_MAXLEVEL is 32 and ZSKIPLIST_P is 0.25. Up to Redis 8.4 the node also held a pointer to a separately allocated member string. Redis 8.6 embeds the member string in the same allocation, after the level array, and reuses the unused level-0 span for bookkeeping, one of the "unified score/value structures" behind its sorted-set memory savings (Redis 8.6 notes). A sorted set also keeps a hash table from member to score for O(1) score lookups. Small sorted sets skip all of this and use a compact listpack until they exceed 128 entries or 64-byte members (zset-max-listpack-entries and zset-max-listpack-value in redis.conf; Redis before 7.0 called the encoding ziplist).

RocksDB's default memtable is an InlineSkipList. Each node stores its next pointers immediately before the key bytes in one allocation from the memtable's arena, so a node is a single contiguous block. Concurrent writers insert by compare-and-swap on each level's pointer, bottom up. This is on by default (allow_concurrent_memtable_write = true), and only the skip-list memtable supports it; the hash-based and vector memtables do not (RocksDB wiki). Nothing is ever removed from it: deletes are written as tombstone entries, and the whole memtable is freed after it is flushed.

Layer 3The machine

Each step to a node not in cache is a dependent load costing 80 to 100 ns from DRAM, so a 10-level search with 40 node visits can reach a few microseconds when cold. Arena allocation helps: nodes inserted close in time are close in memory, and inlining the key avoids a second miss to compare it.

Concurrency relies on the memory model. A writer fully initialises a node, then publishes it with a release store or CAS; readers use acquire loads, so they never see a half-built node. On x86 ordinary stores are already ordered, so release costs almost nothing; on ARM it needs barrier instructions. An uncontended CAS costs about 10 to 20 ns, while a contended one forces the cache line to move between cores. In Redis everything runs on one thread, so no atomics are needed, and an average node at p = 1/4 carries about 1.33 levels of 16 bytes each plus 16 bytes of score and backward pointer. Before 8.6 it also paid an 8-byte member pointer and a second allocation for the string, which meant a likely extra cache miss on every comparison that tied on score.

Why it's built this way

  1. Balanced trees keep their bounds by restructuring several nodes at once, which is hard to make concurrent.
  2. Random levels keep the structure balanced in expectation while every change stays local to a few pointers.
  3. Local single-pointer changes map directly onto compare-and-swap, which makes lock-free versions practical.
  4. Pointer chasing is slow on real CPUs, so engines inline keys, use arenas, and defer freeing memory until a whole memtable is dropped.

Diagram

flowchart LR
    S["Search key 42"] --> T["Head, top level"]
    T --> R{"Next key < 42?"}
    R -->|yes| M["Move right"]
    M --> R
    R -->|no| L{"Level 0?"}
    L -->|no| D["Drop one level"]
    D --> R
    L -->|yes| F{"Next key = 42?"}
    F -->|yes| Y["Found"]
    F -->|no| N["Absent; predecessors known for insert"]

Worked example

A storage engine uses an LSM tree. Writes go to an in-memory memtable that must accept 200,000 inserts per second from 16 writer threads while point reads and range scans run concurrently. When it reaches 64 MB it becomes immutable and is flushed to a sorted file.

With 100-byte entries, a 64 MB memtable holds about 600,000 keys. At p = 1/4 the expected height is about log4(600,000), roughly 10 levels, and each node carries 1.33 pointers on average, about 11 bytes of pointer overhead per entry on a 64-bit machine. A lookup costs about 4 steps per level over 10 levels, around 40 key comparisons, each a likely cache miss: on the order of 2 to 4 microseconds.

A balanced tree needs about 20 comparisons with similar cache misses, so it is not much faster single-threaded. The difference is concurrency: 16 writers insert in parallel with compare-and-swap, and readers never lock, whereas a red-black tree would serialise writers behind locks around rotations.

Flushing is a single walk along level 0, already in key order.

Pointer chasing is cache-unfriendly, so engines store keys inline in each node and allocate nodes from a contiguous arena.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Skip listSimple, no rebalancing, easy lock-free concurrency, cheap ordered scansProbabilistic bounds, pointer overhead, cache-unfriendlyConcurrent in-memory ordered maps, memtables
Balanced BST (red-black, AVL)Worst-case O(log n), compactRotations make concurrency hardSingle-threaded ordered maps
B-tree / B+treeCache and disk friendly, high fanoutMore complex code, splits and mergesOn-disk indexes and large in-memory indexes
Hash mapO(1) lookupsNo ordering, no range scansPoint lookups only

Pitfalls in production

Leadership lens

Check yourself

  1. Why does a skip list stay balanced without any rebalancing step?

    Show answer

    Each node's height is chosen independently at random when it is inserted, so the expected number of nodes per level halves (or quarters) regardless of key order, and no operation can push the structure into a bad shape except through bad luck.

  2. Why are lock-free skip lists common but lock-free balanced trees rare?

    Show answer

    A skip-list insert is a series of independent single-pointer updates that can each be done with compare-and-swap, while tree rotations must change several pointers atomically.

  3. What does lowering p from 1/2 to 1/4 trade?

    Show answer

    Fewer pointers per node (1.33 instead of 2), so less memory, at the cost of more horizontal steps per level and slightly longer searches.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →