谈谈 ZSet 底层实现？
结论：ZSet 在元素少且值小时用 listpack（连续内存、省空间）；超过阈值后转为 skiplist + dict 双结构——dict 负责
member → score的 O(1) 定位，skiplist 负责按 score 有序的范围查询与排名。两套结构共享同一份 member/score 数据，用内存换"既快又能排序"。
一、编码与阈值
| 编码 | 触发条件 | 结构 | 适用 |
|---|---|---|---|
| listpack | 元素数 ≤ zset-max-listpack-entries（默认 128）且每个元素 ≤ zset-max-listpack-value（默认 64 字节） | 连续数组，按 score 升序排列 | 小集合，省内存、缓存友好 |
| skiplist + dict | 任一阈值超出 | 跳表 + 哈希表 | 大集合，O(log N) 增删查 |
转换是单向的：一旦升级为 skiplist 就不会退回 listpack。这解释了为什么"压测时先写小数据再放大"会导致内存表现与预期不符。
二、双结构如何协作
┌──────────────────────────────────────────┐
ZADD key 90 memberA │
│ │
┌───────▼────────┐ ┌────────────────▼───────┐
│ dict │ │ skiplist │
│ memberA → 90 │ │ level3: head ─────────►│
│ memberB → 85 │ │ level2: head ──► 90 ──►│
└────────────────┘ │ level1: head ►85►90►95 │
└────────────────────────┘
ZSCORE → 查 dict，O(1)
ZRANGE → 走 skiplist 底层链表，O(log N + M)
ZRANK → 走 skiplist 的 span（跨度），O(log N)
跳表节点关键字段：ele（成员）、score（分值）、backward（后退指针，支持逆序遍历）、level[]（每层含 forward 前进指针与 span 跨度）。span 让"第几名"可以在查找路径上累加得到，无需遍历。
三、层数与复杂度
// 随机层数：每层以 1/4 概率继续向上，最高 32 层
int zslRandomLevel(void) {
int level = 1;
while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) // P = 0.25
level += 1;
return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
| 操作 | 平均复杂度 | 说明 |
|---|---|---|
| ZADD | O(log N) | 先查 dict 判断是否存在，再插入跳表 |
| ZSCORE | O(1) | 只查 dict |
| ZINCRBY | O(log N) | 需要删除旧节点再按新 score 插入 |
| ZRANGE start stop | O(log N + M) | M 为返回元素数 |
| ZRANK / ZREVRANK | O(log N) | 靠 span 累加 |
| ZRANGEBYSCORE | O(log N + M) | 跳表按 score 定位起点后顺序取 |
| ZUNIONSTORE | O(N) + O(M log M) | 聚合后重建 |
平均层数期望为 1/(1-P) = 1.33，所以每个节点的指针开销并不夸张；这也是它比平衡树更省内存的原因之一。
四、为什么用跳表而不是红黑树
- 实现简单：插入删除只需改指针，不需要旋转与变色，代码量小、易维护；
- 范围查询天然友好：底层是链表，找到起点后顺序遍历即可，红黑树需要中序遍历或额外的线索；
- 并发友好：跳表的局部修改只影响相邻节点，便于做无锁化改造（Redis 未用，但这是跳表的通用优势）；
- 内存可控：平均 1.33 层指针，比每个节点存左右子指针 + 颜色位的红黑树更省。
代价是查询常数略大（多层指针跳转），但 O(log N) 量级一致，工程上更划算。
五、常见追问
- 问：ZSet 的 score 相同怎么排序？答：score 相同时按 member 的字典序升序，因此
ZRANGE的结果是确定的，不会因内部结构变化而抖动。 - 问：ZINCRBY 为什么是 O(log N) 而不是 O(1)？答：dict 里更新 score 是 O(1)，但 skiplist 中节点位置由 score 决定，分值变化必须删除旧位置再插入新位置。
- 问：listpack 里的 ZSet 怎么保证有序？答：插入时按 score 找到位置后整体搬移（memmove），元素少时成本可接受；元素一多就升级为跳表。
- 问：ZSet 能存多少元素？答：理论上限 2^32-1，实际受内存限制；百万级成员的跳表内存约几十 MB，要评估是否该用其他存储。
- 问：ZRANGEBYSCORE 与 ZRANGE 的差别？答：前者按分值区间，后者按下标区间；前者常用于"取某时间段内的数据"，后者常用于"取前 N 名"。
- 问：排行榜分页为什么慢？答：
ZRANGE start stop在 start 很大时仍要沿链表走 start 步；深度分页应改用"按上一页最后一个 score 继续查"的游标方式。 - 问：ZSet 与 List 都能做队列，为什么延时队列选 ZSet？答：ZSet 按 score 有序，可以一次取出"所有已到期的任务"，List 只能按插入顺序取，无法按时间筛选。
小结
- 小集合用 listpack 省内存，大集合用 dict + skiplist 兼顾定位与排序。
- 两个阈值（128 个元素 / 64 字节）决定编码，升级后不可逆。
- 跳表胜在实现简单、范围查询与排名高效，这正是排行榜、延时队列都基于 ZSet 的原因。