How a Redis Sorted Set Is Stored

The idea: one type, two encodings

A Redis sorted set (zset) maps each member to a score and keeps the members ordered by score. A game leaderboard is the classic use: ZADD leaderboard 120 alice, then ask for a player's score, rank, or the top 10. Redis stores a small zset as one compact listpack. Once it grows, it switches to a skiplist for the order plus a dict (hash table) for direct lookups. The commands stay the same; only the cost of each one changes.

Small: the listpack

A listpack is one block of memory: a 6-byte header (tot-bytes, num-elements), the entries back to back, and an end byte FF. A zset puts each member and its score in two neighbouring entries, sorted by score (equal scores by member). A short string costs 1 byte of header plus its bytes; a small integer score costs 1–3 bytes; each entry ends with a 1-byte back-length so the list can be read backwards. There are no pointers at all.

Every command scans: ZSCORE compares members pair by pair, ZADD finds the first larger score and moves the bytes after it (memmove). That is O(N), but with N ≤ 128 the whole listpack sits in a cache line or two, so it is faster than chasing pointers (Demo: small zset in a listpack).

When it converts

Two settings in redis.conf decide it. Before an add, Redis checks both:

Setting	Default	On this page	Converts when
zset-max-listpack-entries	128	4 (scaled down so it fits)	the count would pass it
zset-max-listpack-value	64 bytes	64 bytes	a member is longer

zsetConvert walks the listpack in order, inserts each pair into a new skiplist and dict, and frees the listpack (Demo: 5th member → skiplist + dict). Pick heidi, whose name is 70 bytes, to see the second rule fire on a set of only three. The conversion is one-way: removing members never turns a skiplist back into a listpack. Only when the zset becomes empty does Redis delete the key, and a later ZADD starts again with a listpack. OBJECT ENCODING leaderboard tells you which one you have.

Large: a skiplist plus a dict

Each structure does what the other can't do cheaply. The dict maps member → score, so ZSCORE and the "does this member exist?" check inside ZADD are O(1) instead of a scan. The skiplist keeps the members in score order, so ranks and ranges take O(log N). The member string is stored once and shared: the dict entry and the skiplist node point at the same sds.

Levels, spans and the backward pointer

A skiplist is a sorted linked list with express lanes. Each node gets a random level when it is created: level 1 always, level 2 with probability 1/4, level 3 with 1/16, and so on, up to 32 (zslRandomLevel). On level i a node points to the next node that is at least as tall. A search starts on the highest level of the header node, moves right while the next node is still smaller, and drops a level when it would overshoot. That gives O(log N) steps on average. The page uses a fixed sequence of levels (2, 1, 3, 1, 2, 3, 1, 4, …) so every run looks the same, and draws only 4 levels.

Redis adds two things to the textbook skiplist. Every forward pointer stores a span: how many nodes it jumps over. Every node also has a backward pointer to the previous node on level 0. The zskiplist struct keeps header, tail, length and the current level.

ZADD step by step

zslInsert walks down from the top level. On each level i it records update[i], the last node before the new one, and rank[i], that node's position (the sum of the spans followed so far). Then:

1. It picks the new node's level. If it is taller than the list, the header becomes update[i] on the new levels.
2. On every level of the new node, it links it in after update[i]. The new node's span is update[i].span − (rank[0] − rank[i]), and update[i].span becomes rank[0] − rank[i] + 1.
3. On the higher levels, update[i]'s pointer now jumps over one more node: span + 1.
4. It sets the backward pointers, the tail if needed, and length + 1.

The page shows the update[] and rank[] table as the search runs (Demo: ZADD: search path and spans). ZREM runs the same search, then undoes the links: where update[i] pointed at the node it inherits the node's pointer and span − 1; elsewhere its span drops by 1. If the top level ends up empty, the list's level shrinks.

ZRANK, ranges and a top N

ZRANK gets the score from the dict, then searches for (score, member) and adds the span of every pointer it follows. When it lands on the member, the sum is its 1-based rank. It reads a handful of spans instead of counting nodes (Demo: ZRANK adds up the spans). The same spans let ZRANGE leaderboard 1000 1009 jump straight to rank 1000.

ZRANGEBYSCORE leaderboard 100 +inf uses the levels to find the first node with a score ≥ 100 (zslFirstInRange), then walks level 0 one node per result. A leaderboard wants the highest scores first: ZREVRANGEBYSCORE leaderboard +inf -inf LIMIT 0 3 finds the last node in range (the tail here) and follows the backward pointers (Demo: ZRANGEBYSCORE and a top 3). Since Redis 6.2 you can also write it as ZRANGE leaderboard +inf -inf BYSCORE REV LIMIT 0 3.

ZINCRBY: in place or move

When a score changes, zslUpdateScore finds the node. If the new score still sits between the previous node's and the next node's, it updates the score in place and no pointer changes. Otherwise it deletes the node and inserts a new one, which gets a new random level. The dict entry is updated either way (Demo: ZINCRBY in place, then a move). In a listpack, any score change is a delete plus an insert.

Command	listpack	skiplist + dict
ZADD (new member)	O(N) scan + memmove	O(1) dict check + O(log N) insert
ZSCORE	O(N) scan	O(1) dict lookup
ZRANK	O(N) scan	O(log N), sum of spans
ZRANGEBYSCORE	O(N) scan	O(log N + M) for M results
ZINCRBY	delete + insert	in place, or delete + insert
ZREM	O(N) scan + memmove	O(log N) + dict delete

See also how Redis serves many connections with one thread, the other Redis internals pages: the Redis dict and incremental rehashing, Redis object encodings, expiry and eviction, RDB and AOF persistence, replication, streams and transactions, plus Redis Cluster. For the hash table and ordered-tree ideas behind the two structures, see hashing with chaining, Java's HashMap, binary search trees and red-black trees.

For a plain skip list step by step (search, coin-flip insert, delete), see Skip List.

What the page leaves out

• Real levels are random (p = 1/4) and go up to 32; the page uses a fixed sequence and draws 4.
• The dict's real hashing (SipHash), its power-of-two sizes and incremental rehashing. The bucket numbers here are made up.
• Scores are doubles in Redis (with -inf/+inf); the listpack stores integral ones as integers. The page uses small integers.
• ZADD flags (NX, XX, GT, LT, CH, INCR), WITHSCORES, LIMIT offsets, lexicographic ranges (ZRANGEBYLEX), ZPOPMIN/BZPOPMAX, and set operations such as ZUNIONSTORE.
• Memory details: node allocation sizes, the listpack's multi-byte back-lengths, and how ZRANGESTORE and ZRANDMEMBER use the structures.

References

Redis documentation: sorted sets

Redis source: t_zset.c (zslInsert, zslUpdateScore, zslGetRank, zsetConvert)

Redis source: listpack.c (entry encodings)

redis.conf: zset-max-listpack-entries and zset-max-listpack-value