Skip to main content
← CONCEPTS / ALGORITHMS & DATA STRUCTURES
An end-to-end domain learning journey

Skip Lists &
Probabilistic Multi-Level Indexing.

A skip list layers probabilistic express lanes on top of a sorted linked list so searches, insertions, and range scans run in O(log N) expected time without global tree rebalancing.
Start the journey7 sections
FIRST PRINCIPLES. PRODUCTION SCALE.
The idea to keep with you

A skip list layers probabilistic express lanes on top of a sorted linked list so searches, insertions, and range scans run in O(log N) expected time without global tree rebalancing.

TL;DR30-second simplified summary
▾

A sorted linked list supports O(1) insertion once a position is found, but finding that position takes O(N) linear time. Balanced binary search trees (AVL, Red-Black) achieve O(log N) search, yet require complex rotations that lock wide subtrees under concurrent writes. Skip lists solve this by stacking multiple sorted linked-list layers—express lanes—above a base sorted list.

Each inserted key flips a weighted coin (commonly p = 1/2 or p = 1/4) to decide its tower height, up to MAX_LEVEL. Roughly half of all nodes appear at Level 1, a quarter at Level 2, and so on. Searches start at the top-left HEAD node, stepping right while the next key is smaller than the target, and dropping down one level whenever the next key overshoots—reaching any key in O(log N) expected steps.

By storing a span count on every forward pointer (the number of Level-0 nodes skipped by that edge), an indexed skip list also computes exact 1-based rank (ZRANK) and range-by-rank (ZRANGE) queries in O(log N) expected time—which is why Redis implements Sorted Sets (ZSET) with a skip list + hash table.

Key trade-offs and failure modes: skip lists use more pointer memory than balanced trees (~1.33 to 2 pointers per node on average) and have poorer cache locality than B-Trees on disk; worst-case search degrades to O(N) if the RNG is weak or unseeded, and lock-free concurrent variants require careful logical-deletion mark bits before physical unlinking.

From patterns to decisions.

Understand how randomized tower heights, forward-pointer spans, and lock-free CAS updates make skip lists the backbone of Redis ZSETs and RocksDB MemTables.

Full walkthrough · 7 stages
01
STAGE 01 · CORE INTUITIONfoundation

From O(N) Linked Lists to Multi-Level Express Lanes.

Imagine a subway line with local stops (Level 0) and express stops (Levels 1–3). To travel from station 0 to station 52, you ride the top express lane until the next stop overshoots 52, drop down one level, and repeat.

Because each upper level skips roughly 1/p of the nodes below it, a list of NN elements has expected height O(log⁡1/pN)O(\log_{1/p} N) and expected search path length O(log⁡N)O(\log N).

Top-Down Express-Lane Search Path

Level 3 (Express)Level 2Level 1Level 0 (Target)
02
STAGE 02 · RANDOMIZATIONfoundation

Probabilistic Level Assignment & Memory Overhead.

When inserting a node, we pick its height using geometric coin flips:

  • With p=1/2p = 1/2: expected pointers per node = ∑k=0∞(1/2)k=2.0\sum_{k=0}^{\infty} (1/2)^k = 2.0.
  • With p=1/4p = 1/4 (used by Redis zskiplist): expected pointers per node drops to 1.33, saving ~33% pointer memory at the cost of a slightly taller constant factor in search.
  • Always cap height at MAX_LEVEL (e.g., 32 for 2322^{32} or 4164^{16} elements) and seed a fast PRNG (xorshift / splitmix64) rather than a global mutex-locked RNG.
03
STAGE 03 · ORDER STATISTICSintermediate

Forward-Pointer Spans for O(log N) Rank & Range Queries.

A standard skip list finds a key in O(log⁡N)O(\log N), but counting how many elements precede it would take O(N)O(N).

By storing span[lvl] on each forward pointer—the exact number of Level-0 nodes between the current node and forward[lvl]—we accumulate rank += current.span[lvl] every time we step right during search. That yields exact 0-based or 1-based rank in O(log⁡N)O(\log N).

04
STAGE 04 · IMPLEMENTATIONintermediate

Bounded Skip List Insert & Search with Safe Level Clamping.

Tracking the update[0..level] predecessor array on the way down makes insertion purely local—zero global rotations:

import random

class SkipNode:
    __slots__ = ('key', 'val', 'forward')
    def __init__(self, key, val, level):
        self.key = key
        self.val = val
        self.forward = [None] * (level + 1)

class SkipList:
    def __init__(self, max_level=32, p=0.25):
        self.max_level = max_level
        self.p = p
        self.level = 0
        self.head = SkipNode(float('-inf'), None, max_level)

    def _random_level(self):
        lvl = 0
        while random.random() < self.p and lvl < self.max_level:
            lvl += 1
        return lvl

    def insert(self, key, val):
        update = [None] * (self.max_level + 1)
        cur = self.head
        for i in range(self.level, -1, -1):
            while cur.forward[i] and cur.forward[i].key < key:
                cur = cur.forward[i]
            update[i] = cur
        nxt = cur.forward[0]
        if nxt and nxt.key == key:
            nxt.val = val  # Update in-place without allocating duplicate node
            return
        new_lvl = self._random_level()
        if new_lvl > self.level:
            for i in range(self.level + 1, new_lvl + 1):
                update[i] = self.head
            self.level = new_lvl
        node = SkipNode(key, val, new_lvl)
        for i in range(new_lvl + 1):
            node.forward[i] = update[i].forward[i]
            update[i].forward[i] = node
05
STAGE 05 · CONCURRENCYintermediate

Why RocksDB MemTables and Java ConcurrentSkipListMap Prefer Skip Lists.

In a Red-Black tree, inserting a node can trigger rotations up to the root, forcing coarse locks. In a skip list:

  • Insert: First CAS-link the node at Level 0 (the linearization point), then link upper levels bottom-up.
  • Delete: Atomically mark next pointer as logically deleted (mark_bit) before physically unlinking, preventing concurrent traversals from splicing a new node onto a deleted node.
06
STAGE 06 · TRADE-OFFSadvanced

Skip List vs. Red-Black Tree vs. B-Tree.

  • Skip List: Best for concurrent in-memory ordered maps (ConcurrentSkipListMap), LSM MemTables, and ZSET rank indexing. Weak CPU cache locality due to pointer chasing.
  • B-Tree / B+Tree: Best for disk/SSD and cache-line-friendly in-memory scans because keys sit contiguously in 4–16 KB nodes.
  • Red-Black Tree: Lower pointer memory than p=1/2p=1/2 skip lists, but harder to make lock-free.
07
STAGE 07 · GOTCHASadvanced

Weak RNG Seeds, Pointer-Chasing Cache Misses & Delete Races.

  • Unseeded or Contended RNG: Sharing a global rand() across threads serializes inserts on an RNG mutex; use thread-local xorshift64*.
  • Unbounded MAX_LEVEL: If MAX_LEVEL is too small (e.g., 8 for 100M keys), upper express lanes saturate and degrade to O(N)O(N).
  • ABA / Physical Unlink Race: Never free a deleted node while lock-free readers may hold a pointer; use epoch-based reclamation (EBR) or hazard pointers.
Practice · Explain the consequences

Practice: Make the trade-off yourself.

Question 1 of 3
Score: 0/3

Why does Redis use `p = 1/4` instead of `p = 1/2` for its `zskiplist` implementation?

Recommended Learning Flow