Redis sorted sets support O(log N) insert, O(log N) rank lookup, and O(log N + M) range queries. A balanced BST like a red-black tree could also do this. Redis uses a skip list instead. For years I just accepted that without understanding why.

How a Skip List Works#

A skip list is a linked list with express lanes. The base level is a sorted linked list of all elements. Above it are increasingly sparse “express lanes”: level 2 has every 2nd element, level 3 every 4th, and so on, each determined probabilistically at insert time.

To find an element, start at the top lane. Move forward until the next element is too large, then drop down a lane. Repeat until you reach the base level. Expected time: O(log N).

Level 3:  1 ---------> 25 ---------> 75
Level 2:  1 --> 10 --> 25 --> 50 --> 75
Level 1:  1  5  10  15  25  30  50  60  75  90

Searching for 60: Level 3 sees 1, then 75 (too big), drop. Level 2 sees 50, then 75 (too big), drop. Level 1 sees 60. Found in O(log N) steps.

Why Not a Balanced BST?#

Balanced BSTs (red-black trees, AVL trees) require rotations to stay balanced. Rotations touch multiple nodes and are tricky to implement correctly, especially with concurrent access. A skip list achieves the same asymptotic complexity with simpler insert and delete operations: just update the nodes at each level, no rotations.

For range queries, skip lists win clearly. Finding all elements between scores 50 and 80 means: jump to score 50 in O(log N), then walk forward in the base linked list until you exceed 80. Natural sequential access. A BST range query needs an in-order traversal, which is less cache-friendly.

graph TD A[ZADD leaderboard score member] --> B[Find Insert Position: O log N] B --> C[Insert at Base Level] C --> D[Probabilistically Promote to Upper Levels] D --> E[ZRANK query: O log N] D --> F[ZRANGE by score: O log N + M] style A fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style B fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style C fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style D fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style E fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style F fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff

Redis Sorted Set in Practice#

ZADD leaderboard 9500 "player:1001"
ZADD leaderboard 8800 "player:2034"
ZRANK leaderboard "player:1001"     -- returns rank (0-indexed from lowest)
ZREVRANK leaderboard "player:1001"  -- returns rank from highest
ZRANGE leaderboard 0 9 WITHSCORES REV  -- top 10

Redis actually uses both a skip list and a hash table internally for sorted sets: the hash table for O(1) score lookup by member, the skip list for O(log N) rank operations. Two data structures, two guarantees.

At Oracle#

We needed ordered lookups for network slice priority queues: find all slices with QoS score above a threshold. We used a MySQL indexed column and WHERE score > threshold ORDER BY score LIMIT N. Fine for thousands of rows. At millions of rows the range query got slow. A skip list would have been the right in-memory structure. We ended up keeping a Redis sorted set as a secondary index for fast range queries, with MySQL as the source of truth.

What I’m Learning#

The choice of skip list over BST in Redis was intentional: simpler locking, better cache behavior on range scans, easier concurrent implementation. The data structure choice matters as much as the API.

Have you used Redis sorted sets for problems beyond simple leaderboards?