Skip lists achieve O(log n) search, insert, and delete with probability 1 using nothing more than a random number generator and a linked list with multiple levels. Redis uses skip lists for sorted sets because they're simpler to implement and more concurrent-friendly than red-black trees.
From Linked List to Skip List
A sorted linked list has O(n) search. A skip list adds "express lanes" — levels of linked lists that skip over elements:
Level 3: 1 ──────────────────────────→ 9 ───────→ NIL
Level 2: 1 ────────→ 4 ──────────────→ 9 → 12 → NIL
Level 1: 1 → 2 → 3 → 4 → 5 → 7 → 9 → 12 → 15 → NIL
Search for 7:
Level 3: 1 → 9 (too far, drop down)
Level 2: 1 → 4 → 9 (too far, drop down)
Level 1: 4 → 5 → 7 (found!)import random
class SkipListNode:
def __init__(self, key, level):
self.key = key
self.forward = [None] * (level + 1)
class SkipList:
def __init__(self, max_level: int = 16, p: float = 0.5):
self.max_level = max_level
self.p = p
self.header = SkipListNode(-1, max_level)
self.level = 0
def random_level(self) -> int:
"""Generate random level with geometric distribution."""
lvl = 0
while random.random() < self.p and lvl < self.max_level:
lvl += 1
return lvl
def search(self, key: int) -> bool:
current = self.header
for i in range(self.level, -1, -1):
while (current.forward[i] and
current.forward[i].key < key):
current = current.forward[i]
current = current.forward[0]
return current is not None and current.key == key
def insert(self, key: int):
update = [None] * (self.max_level + 1)
current = self.header
for i in range(self.level, -1, -1):
while (current.forward[i] and
current.forward[i].key < key):
current = current.forward[i]
update[i] = current
new_level = self.random_level()
if new_level > self.level:
for i in range(self.level + 1, new_level + 1):
update[i] = self.header
self.level = new_level
new_node = SkipListNode(key, new_level)
for i in range(new_level + 1):
new_node.forward[i] = update[i].forward[i]
update[i].forward[i] = new_nodeExpected Complexity Analysis
def expected_search_cost(n: int, p: float = 0.5) -> float:
"""Expected number of comparisons for search."""
# At each level, we skip over ~1/p elements
# Number of levels: log_{1/p}(n)
# Comparisons per level: O(1)
import math
levels = math.log(n) / math.log(1 / p)
return levels * (1 / p) # ≈ 2 × log₂(n)
def expected_space(n: int, p: float = 0.5) -> float:
"""Expected total pointers (space overhead)."""
# Each element appears on level i with probability p^i
# Expected pointers per element: sum(p^i for i=0..∞) = 1/(1-p) = 2
return n / (1 - p) # ≈ 2n pointers total
# n = 1,000,000:
# Expected search comparisons: ~40
# Expected space: ~2M pointers (16 MB with 8-byte pointers)Comparison to Balanced Trees
# Skip List vs Red-Black Tree vs AVL Tree:
#
# Skip List Red-Black AVL
# Search (expected) O(log n) O(log n) O(log n)
# Search (worst) O(n) O(log n) O(log n)
# Insert (expected) O(log n) O(log n) O(log n)
# Space ~2n ptrs n ptrs + n ptrs +
# 1 bit color height int
# Concurrent Easy Hard Hard
# Implementation Simple Complex ComplexRedis Sorted Sets
Redis uses skip lists for its Sorted Set (ZSET) data structure:
# Redis ZSET operations (implemented with skip list):
import redis
r = redis.Redis()
r.zadd("leaderboard", {"alice": 1500, "bob": 1200, "carol": 1800})
# O(log n) rank query
rank = r.zrank("leaderboard", "alice") # 1 (0-indexed from lowest)
# O(log n) range query
top = r.zrange("leaderboard", 0, 2, withscores=True)
# O(log n) score update
r.zadd("leaderboard", {"alice": 1600})
# Under the hood:
# - Skip list for O(log n) ordered operations
# - Hash table for O(1) key→score lookup
# - Both structures updated atomicallytradeoff / Skip List vs Balanced Tree
Skip lists are the pragmatic choice for ordered concurrent data structures. They sacrifice worst-case guarantees for implementation simplicity and natural concurrency — a tradeoff that Redis, LevelDB, and RocksDB all make.
Choose skip lists when implementation simplicity or concurrent access matters. Choose balanced trees when you need worst-case guarantees or minimal memory overhead. Most real-world systems use skip lists for ordered concurrent data.
Synthesis
Skip lists achieve O(log n) expected time through probabilistic level assignment, avoiding the complex rebalancing of deterministic trees. They're simpler to implement, easier to make concurrent, and cache-friendly for sequential access. Redis, LevelDB, and many real-time systems use skip lists as their primary ordered data structure.