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.
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 elements has expected height and expected search path length .
Top-Down Express-Lane Search Path
Probabilistic Level Assignment & Memory Overhead.
When inserting a node, we pick its height using geometric coin flips:
- With : expected pointers per node = .
- With (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 or elements) and seed a fast PRNG (xorshift/splitmix64) rather than a global mutex-locked RNG.
Forward-Pointer Spans for O(log N) Rank & Range Queries.
A standard skip list finds a key in , but counting how many elements precede it would take .
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 .
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] = nodeWhy 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
nextpointer as logically deleted (mark_bit) before physically unlinking, preventing concurrent traversals from splicing a new node onto a deleted node.
Skip List vs. Red-Black Tree vs. B-Tree.
- Skip List: Best for concurrent in-memory ordered maps (
ConcurrentSkipListMap), LSMMemTables, andZSETrank 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 skip lists, but harder to make lock-free.
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-localxorshift64*. - Unbounded
MAX_LEVEL: IfMAX_LEVELis too small (e.g., 8 for 100M keys), upper express lanes saturate and degrade to . - 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: Make the trade-off yourself.
Why does Redis use `p = 1/4` instead of `p = 1/2` for its `zskiplist` implementation?