When a Redis sorted set grows past its compact threshold, OBJECT ENCODING reports "skiplist". What two structures does that encoding actually maintain, and why does it need both?

## What a sorted set has to support A Redis sorted set holds unique members, each with a floating-point score, and its command set demands two very different access patterns: - **By member**: `ZSCORE key member`, `ZADD` updating an existing member, `ZREM`, `ZINCRBY`. These want a dictionary. - **By order**: `ZRANGE`, `ZRANGEBYSCORE`, `ZRANK`, `ZCOUNT`, `ZPOPMIN`, leaderboard slices. These want the data kept in score order with efficient rank arithmetic. No single classical structure gives both cheaply, so the `skiplist` encoding maintains two, kept in sync on every write. ## The skiplist A skiplist is a sorted linked list with extra forward pointers. Each node is assigned a random height; level 0 links every node in order, level 1 links roughly every second node, level 2 roughly every fourth, and so on. Searching starts at the top level and drops down whenever the next pointer would overshoot, so it skips exponentially decreasing distances — expected O(log n) for search, insert and delete, with no rebalancing logic. Ordering is by score, with the member string as tiebreaker, which is why members with equal scores come back in lexicographic order and why `ZRANGEBYLEX` is meaningful only when all scores are equal. Redis's variant adds a **span** to each forward pointer: the number of level-0 nodes it jumps over. Summing spans along a search path yields the element's rank without walking every node, giving O(log n) `ZRANK` and O(log n + m) range queries returning m elements. Why a skiplist rather than a balanced tree? It is simpler to implement correctly, its nodes are easy to traverse in both directions for range queries, the probabilistic balance needs no rotations, and the memory layout suits Redis's allocation patterns. The Redis author has said explicitly that simplicity and range-friendliness drove the choice; the asymptotics match a balanced tree. ## The dict Alongside it sits an ordinary hash table mapping member → score. Its job is O(1) answers to "is this member present and what is its score": - `ZSCORE` is a single dict lookup. - `ZADD` on an existing member must find the old score to remove the correct skiplist node before inserting the new one — without the dict, that lookup would be O(n). - `ZREM` and `ZINCRBY` likewise. The two structures share the member string object rather than duplicating the bytes, but the node and bucket overhead is genuinely paid twice. That makes large sorted sets the heaviest of the core types per element — a relevant fact when a leaderboard of tens of millions of entries is on the table. ## The compact alternative Below `zset-max-listpack-entries` (default 128) and `zset-max-listpack-value` (default 64 bytes for any member), Redis skips both structures and stores the sorted set as a **listpack**: one contiguous blob holding member, score, member, score, … in score order. Lookups and range queries are linear scans, but with at most 128 pairs in contiguous memory that is fast, and the memory saved is large — no skiplist nodes, no hash buckets, no per-element allocation headers. Crossing either threshold converts the value to the `skiplist` encoding, and as with all Redis encoding conversions it is **one-way**: shrinking the sorted set back below 128 members leaves it in the expensive encoding until the key is recreated. ## Practical consequences 1. **Memory planning.** If you hold many small sorted sets (per-user recent items, per-entity scores), keeping each under the listpack thresholds is worth real money. Design bucket sizes accordingly, and cap member length — one long member name flips the whole value. 2. **Big-O awareness on the single thread.** `ZADD`/`ZSCORE` are cheap at any size, but `ZRANGE key 0 -1` on a million-member sorted set returns a million elements and blocks the event loop for the duration. The skiplist makes the *seek* logarithmic; it does nothing about the size of the reply. Use bounded ranges, or `ZSCAN` for iteration. 3. **Diagnosis.** `OBJECT ENCODING` plus `ZCARD` plus `MEMORY USAGE` tells you immediately whether a sorted set's memory is dominated by structure overhead (skiplist, many small members) or by payload (few, long members).