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.
See also: Meta Interview Guide 2026: Facebook, Instagram, WhatsApp Engineering
See also: Uber Interview Guide 2026: Dispatch Systems, Geospatial Algorithms, and Marketplace Engineering
See also: Scale AI Interview Guide 2026: Data Infrastructure, RLHF Pipelines, and ML Engineering
See also: Airbnb Interview Guide 2026: Search Systems, Trust and Safety, and Full-Stack Engineering
See also: Databricks Interview Guide 2026: Spark Internals, Delta Lake, and Lakehouse Architecture
See also: Anthropic Interview Guide 2026: Process, Questions, and AI Safety
See also: Atlassian Interview Guide
See also: Coinbase Interview Guide
See also: Shopify Interview Guide
See also: Snap Interview Guide
See also: Lyft Interview Guide 2026: Rideshare Engineering, Real-Time Dispatch, and Safety Systems
See also: Stripe Interview Guide 2026: Process, Bug Bash Round, and Payment Systems