Skip List (Redis ZSet)

What is it: A probabilistic data structure providing O(log n) insert, delete, search, and range queries using multiple levels of sorted linked lists.

Why: A sorted array supports O(log n) binary search but O(n) insert/delete (shift). A balanced BST (red-black tree) supports O(log n) all operations but is complex to implement, especially for concurrent access. A skip list achieves O(log n) with simpler implementation and better cache locality for range scans.

Structure: Level 0 contains all nodes (a sorted linked list). Higher levels are increasingly sparse subsets. Each node has forward pointers at each level it participates in. Level assignment is random: node gets level k with probability p^k (p=0.25 in Redis). Expected height = O(log n).

graph LR subgraph L2["Level 2 (sparse)"] h2["head"] --> n30_2["30"] --> n70_2["70"] end subgraph L1["Level 1"] h1["head"] --> n10_1["10"] --> n30_1["30"] --> n50_1["50"] --> n70_1["70"] end subgraph L0["Level 0 (every element)"] h0["head"] --> n10["10"] --> n20["20"] --> n30["30"] --> n40["40"] --> n50["50"] --> n60["60"] --> n70["70"] end

Searching for 60: start at the top level's head, follow forward pointers while the next node's key is <= 60. Level 2: head -> 30 (30<=60, keep going) -> 70 (70>60, stop, drop down a level from 30). Level 1: 30 -> 50 (<=60) -> 70 (>60, stop, drop to level 0 from 50). Level 0: 50 -> 60 — found. Three hops across levels instead of scanning 10,20,30,40,50,60 one at a time — the sparser upper levels let the search skip large chunks of the full list, which is exactly what gives this structure its name.

Range query: traverse to the first matching key in O(log n), then follow level-0 forward pointers in O(k) for k results. The level-0 traversal is sequential in memory (cache-friendly) unlike tree traversal (pointer-chasing, cache-unfriendly).

Trade-offs: O(log n) average, not worst case (rare degenerate inputs can make it O(n) — extremely unlikely with random levels). More memory per node than BST (multiple forward pointers). Simpler lock-free implementation than red-black trees.

Real-world usage: Redis ZSet (sorted set): ZADD, ZRANGE, ZRANGEBYSCORE, ZRANK all use the skip list + hash map combination. Proxel's proxy scoring system used a Redis ZSet for ranking proxies by score — ZRANGEBYSCORE returned the top N proxies by score in O(log n + N).

Common pitfall

Redis ZSet is actually two structures kept in sync: the skip list (for ordered range queries) and a hash map (member → score, for O(1) ZSCORE lookups by name). Forgetting this and expecting ZRANK or ZSCORE-style member lookups to be O(log n) instead of O(1) leads to underestimating how cheap "look up this specific member's score" is compared to "give me the elements ranked 100-110" — both are fast, but via genuinely different underlying paths.