Skip List: Design and Applications – Tech Interview Dot Org

A skip list is a probabilistic data structure that provides O(log n) average time for search, insertion, and deletion — the same asymptotic complexity as a balanced BST, but with simpler implementation and better cache behavior. It achieves this by layering multiple linked lists, where higher layers contain fewer elements, creating “express lanes” that skip over most elements during traversal. Redis uses skip lists as the underlying data structure for sorted sets.

Structure

A skip list consists of multiple levels of linked lists. Level 0 contains all elements in sorted order — the base linked list. Level 1 contains roughly half the elements (every other element from level 0). Level 2 contains roughly half the elements from level 1. And so on, up to a maximum level (typically log₂(n)). Each element has a tower of forward pointers — one per level it participates in. A sentinel head node points to the first element at each level; a sentinel tail marks the end.

Search

To search for a target: start at the highest level of the head node. At each level, advance forward as long as the next node’s key is less than the target. When advancing further would overshoot (next key >= target) or reach the end, drop down one level. Repeat until level 0. Check if the current node’s key equals the target. This traversal visits O(log n) nodes on average — the higher levels skip over large portions of the list, narrowing the search range geometrically.

Insertion and Level Randomization

When inserting a new element: find the correct position using the search algorithm (track the rightmost node at each level that is less than the new element). Randomly determine the new node’s level: flip a coin; if heads, increment the level; repeat until tails or the maximum level is reached. This gives level 1 with probability 1, level 2 with probability 1/2, level 3 with probability 1/4, and so on. Link the new node into the list at each of its levels, updating the tracked predecessor nodes’ forward pointers. No rebalancing is ever required — the probabilistic level assignment maintains expected O(log n) height.

Why Redis Uses Skip Lists for Sorted Sets

Redis sorted sets (ZADD, ZRANGE, ZRANK, ZRANGEBYSCORE) require: insertion with O(log n) time, rank queries (“what position is this element?”), and range queries (“return all elements between score 100 and 200”). Skip lists support all of these efficiently. Unlike a BST, skip lists are simpler to implement in C without tree rotations. Skip lists also support O(log n) rank queries by augmenting each forward pointer with a span count — the number of nodes it skips. Redis’s skip list implementation stores each element in both a hash table (for O(1) key lookup) and a skip list (for score-ordered operations).

Range Queries

To retrieve all elements with score between lo and hi: search for lo using the standard search; this lands on the first element with score >= lo. Traverse level 0 forward, collecting elements until score > hi. This is O(log n + k) where k is the number of results — optimal for range queries. This is why ZRANGEBYSCORE in Redis is efficient: the skip list’s sorted structure makes range scans a simple level-0 traversal after finding the start position.

Skip List vs. Balanced BST

Same asymptotic complexity (O(log n) search, insert, delete). Skip lists win on: simpler implementation (no rotations, no rebalancing logic), better concurrent access (updating a skip list node only requires modifying predecessor pointers, making lock-free implementations viable), and cache efficiency for traversal (level-0 traversal is a linked list scan). BSTs win on: deterministic worst-case performance (skip lists have O(n) worst case with low probability), smaller constant factor for small n, and sorted order traversal without a separate level-0 scan. Choose skip lists when concurrency matters and O(log n) average is sufficient; choose BSTs when worst-case guarantees are required.

{ “@context”: “https://schema.org”, “@type”: “FAQPage”, “mainEntity”: [ { “@type”: “Question”, “name”: “How does a skip list achieve O(log n) search without tree rotations?”, “acceptedAnswer”: {“@type”: “Answer”, “text”: “A skip list maintains multiple levels of linked lists. Level 0 contains all elements sorted. Level 1 contains roughly half the elements (every other one). Level 2 contains half of level 1, and so on up to O(log n) levels. Search starts at the highest level: advance forward as long as the next node’s key is less than the target; when it would overshoot, drop down one level; repeat until level 0. This traverses O(log n) nodes on average because higher levels skip over large portions of the list geometrically, narrowing the search range without any tree rotations or rebalancing. The expected height is O(log n) because each level is built probabilistically by randomly promoting elements with probability 1/2.”} }, { “@type”: “Question”, “name”: “How does probabilistic level assignment work in a skip list?”, “acceptedAnswer”: {“@type”: “Answer”, “text”: “When inserting a new element, its level is determined by flipping a biased coin: start at level 1 (always), then flip; if heads (probability p, typically 0.5), increment the level and flip again; stop when tails or the maximum level (log_1/p(n)) is reached. This assigns level 1 with probability 1, level 2 with probability p, level 3 with probability p^2, etc. The expected number of nodes at level k is n * p^(k-1). This creates a geometric distribution of node heights that mirrors a balanced tree structure on average — without requiring rotations. No rebalancing is ever needed because the probabilistic assignment maintains the expected O(log n) structure.”} }, { “@type”: “Question”, “name”: “Why does Redis use skip lists for sorted sets instead of a balanced BST?”, “acceptedAnswer”: {“@type”: “Answer”, “text”: “Redis sorted sets need: O(log n) insertion and deletion, O(log n) rank queries (what position is this element?), and O(log n + k) range queries (return elements between score 100 and 200). Skip lists support all of these. Redis chooses skip lists over balanced BSTs because: (1) simpler C implementation — no rotations or rebalancing code; (2) efficient range traversal — after finding the start position, level-0 is a simple linked list scan; (3) rank queries are supported by augmenting each forward pointer with a span count (nodes skipped); (4) concurrent access is easier — modifying a skip list only updates predecessor pointers, making lock-free implementations viable. Each sorted set element is stored in both a hash table (O(1) key lookup) and a skip list (score-ordered operations).”} }, { “@type”: “Question”, “name”: “How does a skip list compare to a balanced BST?”, “acceptedAnswer”: {“@type”: “Answer”, “text”: “Both provide O(log n) average for search, insert, and delete. Skip lists win on: simpler implementation (no rotation or rebalancing logic), better concurrent access (only predecessor pointers need updating, enabling lock-free CAS operations), cache-friendly level-0 traversal for range scans. BSTs win on: deterministic O(log n) worst case (skip lists have O(n) worst case with negligible probability), smaller memory overhead for small n (skip lists store multiple forward pointers per node), and exact rank queries without augmentation. Choose skip lists when concurrent writes are frequent and O(log n) average is sufficient; choose red-black trees or AVL trees when worst-case guarantees matter (real-time systems, security-critical applications).”} } ] }