Redis 中 ZSet（有序集合）的底层实现，是 Java 开发同学面试/源码阅读时的高频知识点。今天我们来系统、清晰地说透它（基于 Redis 最新 unstable 主干代码，2026 年当前版本已全面使用 listpack 替换 ziplist）。
1. 两种编码方式（Encoding）—— 动态切换，内存与性能的完美平衡
Redis ZSet 不是固定用一种数据结构，而是根据数据规模自动选择：
| 编码类型 | 触发条件（默认配置） | 适用场景 | 优点 | 缺点 |
|---|---|---|---|---|
| OBJ_ENCODING_LISTPACK | 元素个数 ≤ zset-max-listpack-entries（默认 128）每个元素长度 ≤ zset-max-listpack-value（默认 64 字节） | 小型 ZSet | 极致内存节省（连续内存，无指针开销） | 查找/插入 O(N) |
| OBJ_ENCODING_SKIPLIST | 超过上面任意一个阈值，或手动转换 | 中大型 ZSet | 查找/插入/范围查询 O(log N) | 内存占用更高（约 5~6 倍于 listpack） |
- 创建时：
zsetTypeCreate(size_hint, val_len_hint)根据 hint 判断用 listpack 还是 skiplist。 - 运行时：添加元素后若超限，
zsetConvert()自动从 listpack → skiplist（不可逆，除非手动调用 ZSET 命令让它变小）。 - Redis 7.0+ 彻底抛弃了老的 ziplist，用 listpack 取代（原因：ziplist 中间插入/删除会导致“级联更新”（cascading re-encoding），listpack 彻底解决这个问题，结构更简单、性能更好）。
2. 小型 ZSet：Listpack 编码（连续内存，超级省）
Listpack 是一个紧凑的字节数组，专为小数据设计。
- 存储格式（简化后）：
[element1][score1 (double)][element2][score2]...
元素和分数交替存储，按 score 从小到大排序（ZSet 语义保证）。 - 每个 entry 有自己的长度编码（varint），无需额外指针。
- 操作：
zzlInsert()、zzlGetScore()等在 listpack 上直接二分或线性扫描。 - 为什么快省？连续内存，CPU 缓存友好，128 个元素以内几乎感觉不到性能损失。
一旦超过 128 个元素或某个 member 超 64 字节，瞬间转为 skiplist。
3. 大型 ZSet：dict + skiplist 双结构（核心！）
这就是大家常说的“ZSet = HashTable + SkipList”。
typedef struct zset {
dict *dict; // 元素 → zskiplistNode* （O(1) 查找 member）
zskiplist *zsl; // 按 score 排序的跳表
} zset;(1) dict（哈希表）
- key：member（SDS 字符串）
- value：指向 skiplist 中对应节点的指针（不存 score）
- 作用：
ZSCORE、ZREM、ZADD（已存在时更新）都是 O(1) - 特殊设计：字典的
keyFromStoredKey函数直接从 skiplist node 里取嵌入的 SDS，实现零拷贝共享。
(2) zskiplist（跳表）—— Redis 最优雅的数据结构之一
跳表是概率型平衡结构，Redis 选择它而不是红黑树，原因很实在（Salvatore 本人说的）：
- 实现简单（代码量少，容易 debug）
- 范围查询（ZRANGE）超级友好：找到起点后，底层链表线性遍历即可（红黑树要做中序遍历）
- 缓存友好，插入时不需要大量旋转
- 平均 O(log N)，最坏也极少退化（P=1/4，最大层级 32）
关键结构体（来自最新 server.h）：
#define ZSKIPLIST_MAXLEVEL 32 /* 2^64 个元素也够用 */
#define ZSKIPLIST_P 0.25 /* 每层向上晋升概率 25% */
typedef struct zskiplistNode {
double score; // 分数
struct zskiplistNode *backward; // 反向指针（支持 ZREVRANGE）
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned long span; // 本层跳过多少节点（rank 计算用）
} level[]; // 变长数组，实际层数随机
// SDS ele 嵌入在 level[] 之后（zslGetNodeElement 取）
} zskiplistNode;
typedef struct zskiplist {
zskiplistNode *header, *tail;
unsigned long length;
int level; // 当前最高层
size_t alloc_size;
} zskiplist;- 节点创建时随机决定层数（几何分布）。
- 插入
zslInsert()：从最高层开始“往下找、往前跳”，找到位置后插入所有层。 - 范围查询
zslNthInRange、zslFirstInRange极快。 - 每个 node 的 SDS 是嵌入存储，dict 和 skiplist 共享同一块内存，节省指针。
4. 典型命令底层调用路径（举例 ZADD）
- 判断当前 encoding。
- 如果是 listpack →
zzlInsert()，插入后检查是否超阈值 → 转 skiplist。 - 如果是 skiplist：
- 先 dict 查是否存在（O(1)）
- 存在 → 更新 score（从 skiplist 删除旧节点，插入新节点）
- 不存在 →
zslInsert()+ dict 插入
- 所有操作后更新长度、可能触发 rehash 等。
5. 为什么 Redis 这么设计？（面试必问）
- 内存 vs 性能：小数据用 listpack 能省 5~10 倍内存（排行榜初始阶段常见）。
- 范围查询强：跳表天生适合 ZRANGE/ZREVRANGE/ZRANK。
- 简单可靠：比红黑树代码少 2~3 倍，维护成本低。
- 双端口：dict 保证唯一性 + O(1) 点查，skiplist 保证有序 + 范围查。
6. 实战建议（Java 开发视角）
- 业务中排行榜、延迟队列、带权消息队列 → 直接用 ZSet，放心。
- 元素超 128 个后性能几乎无感知（log(10万)≈17）。
- 想看源码：
src/t_zset.c（核心）、src/server.h（结构体）、src/listpack.c（小集合）。 - 调优参数：生产环境可根据业务把
zset-max-listpack-entries调到 256~512，内存敏感场景再调大。
一句话总结：
Redis ZSet = 小数据用 listpack（省内存） + 大数据用 dict（O(1) 查） + skiplist（O(log N) 有序 + 范围），动态转换，兼顾极致内存与高性能。
这就是 Redis 作者在工程实践中做出的最优雅选择。
如果你想看具体跳表随机层级生成代码、listpack 插入细节、或者用 Java 手写一个迷你版跳表，随时告诉我，我继续往下写！🚀
（本文所有结构体和逻辑均来自 Redis unstable 主干源码，2026 年最新设计）
