A sorted set is a collection of unique members, each with an associated floating point score, kept in score order. It is the most capable type Redis offers and the one whose implementation is worth understanding in the most detail, because its cost model is less obvious than the others and more of its misuses are expensive.

Why one structure is not enough

Consider what a sorted set has to do quickly. Given a member, return its score, which is a lookup by name. Given a score range, return the members in it in order, which is an ordered traversal. Given a member, return its position in the ordering, which is a rank query. And insert or update a member, which must keep both the naming and the ordering correct.

No single structure does all of those well. A hash table gives the lookup and no ordering at all. An ordered structure gives the traversal and the rank but makes lookup by member a scan. So Redis keeps both, and every write updates both.

The two halves

The first half is an ordinary dictionary mapping member to score, the same hash table used for the keyspace itself. This is what makes ZSCORE constant time: it is one hash lookup, with no reference to the ordering at all.

The second half is a skiplist ordered by score, with the member as a tiebreaker. This is what makes ZRANGE, ZRANGEBYSCORE, ZRANK and the pop commands possible. The two halves hold the same members, each member's string being shared between them rather than stored twice, so the duplication is of structure rather than of data.

What a skiplist is

A skiplist is a sorted linked list with extra forward pointers that skip ahead. The bottom level links every node in order. Each node is also present at some number of higher levels, where the links skip over the nodes absent from that level, so a search starts at the top level, moves forward until the next node would overshoot, drops a level, and repeats.

The number of levels a node occupies is chosen at random when the node is inserted. Redis uses a probability of one quarter, so a node is at level one with probability three quarters, at level two with probability three sixteenths, and so on, with a hard ceiling of 32 levels. The result is that the expected number of levels per node is about one and a third, and the expected search cost is logarithmic.

Why random rather than balanced

The randomness is the point. A balanced tree achieves the same logarithmic bound by rebalancing on insert and delete, which requires rotation logic, careful handling of several cases, and attention to invariants. A skiplist achieves it by coin flips, with insert being a search followed by pointer updates at each level the new node occupies, and delete being the same in reverse.

The code is dramatically simpler, which in a single-threaded server maintained over fifteen years is worth more than it sounds. The bound is probabilistic rather than guaranteed, but the probability of a badly shaped skiplist falls off so fast that it does not happen: the levels are chosen by the server's own random number generator rather than from the data, so there is no input an adversary can supply to force a bad shape, which is the usual objection to randomised structures.

The two properties a tree would not give as easily

Two more reasons the skiplist suits this particular job. Range iteration is a plain walk along the bottom level once the start has been found, with no traversal state and no successor logic, which is exactly what ZRANGEBYSCORE needs and what makes it cost the found range rather than a logarithm per element.

And rank queries work by storing, with each forward pointer, the number of bottom-level nodes it skips. Summing those spans along a search path gives the rank directly, so ZRANK is logarithmic rather than linear, and ZRANGE by index can locate its start without walking to it. A balanced tree can do the same with subtree sizes, but the skiplist version is a single integer per pointer and no rebalancing to maintain it through.

The listpack form, and when it applies

As with hashes, a small sorted set skips all of this and is stored as a listpack holding member and score pairs in score order, controlled by zset-max-listpack-entries, defaulting to 128, and zset-max-listpack-value, defaulting to 64 bytes for a member.

Every operation on the listpack form is a scan, which for a sorted set means more than it does for a hash: finding a score boundary means walking from one end comparing scores, where the skiplist descends to it. The entries are in score order, so the scan can stop early, but there is no skipping. This makes the threshold for a sorted set one I am less willing to raise than the hash equivalent, because ordered range access is the sorted set's whole purpose and the listpack serves it worst.

What a member costs

In the skiplist form, a member costs a dictionary entry of 24 bytes, a skiplist node with a score and a backward pointer and an average of about one and a third forward pointer and span pairs, and the member string itself with its allocation. That is in the region of 70 to 100 bytes of structure per member before the member's own bytes.

This is the figure to use when sizing. A sorted set of ten million members with short member strings is roughly a gigabyte, almost all of it structure, and the memory cannot be reduced by any configuration because the structures are what make the operations work. A sorted set is therefore the most expensive type per element, and that cost buys ordering, rank and range access that nothing else provides.

What the two halves mean for a delete

Removal is the operation where the two structures are most visible. ZREM looks the member up in the dictionary to find its score, which is the only way to know where in the skiplist it lives, then searches the skiplist to that score and member, unlinks the node at every level it occupies, and adjusts the spans along the search path so ranks stay correct.

So a delete is a hash lookup plus a logarithmic search plus pointer and span updates, and it cannot be done from the skiplist alone without the score. This is why there is no command to remove a member by position cheaply in isolation: ZREMRANGEBYRANK works because it finds a contiguous run and unlinks it in one traversal, which is much better than one ZREM per member.

The practical consequence is that bulk removal should use the range commands rather than a loop. Trimming a thousand members with ZREMRANGEBYRANK key 0 999 is one traversal; the same work as a thousand ZREM calls is a thousand dictionary lookups and a thousand skiplist searches, which is both slower on the server and a thousand round trips.

Reading the encoding, and sizing a set deliberately

OBJECT ENCODING reports listpack or skiplist, and the same one-way promotion rule applies: a sorted set that once exceeded a threshold stays in the expensive encoding until the key is rewritten or the instance reloads from a snapshot.

The practical sizing advice follows the arithmetic above. A sorted set used as an index should hold identifiers and nothing else, because the member string is stored once but the structure around it is paid per member regardless, so making members short is the one lever available. And a sorted set that is going to hold millions of members should be designed with that gigabyte in mind rather than discovered to need it, which usually means asking whether the full ordering is needed or whether bucketing, covered in the last section, would serve.