刺猬快递公司
86.27M · 2026-04-09
ziplist / listpack + skiplist）以及各自的触发条件。ziplist 替换为 listpack，以及为什么要换。Redis ZSet（有序集合）底层使用 两种数据结构 实现，根据元素数量和大小自动切换：
| 条件 | 底层结构 | 特点 |
|---|---|---|
| 元素数量 ≤ 128 且每个元素 ≤ 64 字节 | ziplist（Redis 7.0 前）/ listpack（Redis 7.0+） | 紧凑存储，省内存，适合小数据量 |
| 元素数量 > 128 或有元素 > 64 字节 | skiplist（跳表）+ dict（字典） | O(logN) 查找，适合大数据量 |
一句话结论：ZSet 的核心是 跳表 + 字典 的组合结构。跳表负责按分数范围查询（O(logN)），字典负责按成员查分数（O(1)），两者配合实现了 ZSet 的所有操作。
img
上图展示了 ZSet 的核心架构 —— 跳表 + 字典的组合：
ZSCORE 命令时，直接通过字典查找，不需要遍历。ZRANGEBYSCORE、ZRANK 等命令时，跳表能快速定位。跳表是 ZSet 最核心的数据结构，面试必问。
img
上图展示了跳表的核心结构：
跳表节点的源码结构（Redis 7.x） ：
// 跳表节点定义（源码 t_zset.c）
typedef struct zskiplistNode {
sds ele; // 成员对象（member）
double score; // 分值
struct zskiplistNode *backward; // 后退指针（Level 1 的前驱）
struct zskiplistLevel {
struct zskiplistNode *forward; // 前进指针
unsigned long span; // 跨度（到下一个节点的距离）
} level[]; // 层数组，柔性数组
} zskiplistNode;
// 跳表定义
typedef struct zskiplist {
struct zskiplistNode *header, *tail; // 头尾节点
unsigned long length; // 节点数量
int level; // 最大层数
} zskiplist;
关键字段解释：
ele：存储 member（如 "张三"）。score：存储分值（如 85.5），跳表按此字段排序。backward：后退指针，只在最底层（Level 1）使用，支持从尾向头遍历（如 ZREVRANGE）。level[]：柔性数组，每个元素包含 forward（前进指针）和 span（跨度）。span 用于计算排名，ZRANK 命令就是通过累加 span 得到的。header：跳表有一个特殊的头节点，不存储数据，它的层数始终等于跳表的最大层数。img
上图总结了跳表的四种核心操作：
ZSCORE、ZRANK 等命令的基础。这是面试中 最常被追问 的问题。
img
上图对比了跳表和红黑树的核心差异：
ZRANGE、ZRANGEBYSCORE），跳表在这方面有天然优势。span 字段可以 O(logN) 计算排名，而红黑树需要额外维护子树大小信息（类似 Order Statistic Tree），增加实现复杂度。img
上图展示了 ZSet 在元素较少时的紧凑存储方式：
ziplist 的每个元素头部存储了前一个元素的长度（prevlen），当前一个元素大小变化时，可能引发后续所有元素的 prevlen 字段连锁更新，最坏 O(N²)。prevlen，每个元素只记录自己的长度，彻底消除了级联更新问题。zset-max-listpack-entries 控制最大元素数量，zset-max-listpack-value 控制最大元素大小。超过任一阈值就会转换为跳表。| 命令 | 功能 | 底层操作 | 复杂度 |
|---|---|---|---|
ZADD | 添加元素 | dict 插入 + skiplist 插入 | O(logN) |
ZSCORE | 查分数 | 直接查 dict | O(1) |
ZRANK | 查排名 | skiplist 累加 span | O(logN) |
ZRANGE | 按排名范围查 | skiplist 遍历 | O(logN + M) |
ZRANGEBYSCORE | 按分数范围查 | skiplist 定位 + 遍历 | O(logN + M) |
ZREM | 删除元素 | dict 删除 + skiplist 删除 | O(logN) |
ZCARD | 元素总数 | 直接读 length | O(1) |
ZCOUNT | 分数范围内数量 | skiplist 定位两端 | O(logN) |
关键点：
ZSCORE 和 ZCARD 是 O(1)，因为字典直接查、length 字段直接读。追问一：跳表的层数是怎么确定的？
每次插入新节点时，通过随机算法决定层数。Redis 使用的是 幂次定律（power law） ：每个节点有 25% 的概率再往上一层延伸，最多 32 层。这意味着大约 75% 的节点只有 1 层，25% 有 2 层，6.25% 有 3 层……层数越高节点越稀疏，从而保证查找效率接近 O(logN)。
追问二：ZSet 中 member 相同、score 不同会怎样？
ZSet 中每个 member 是唯一的。如果 ZADD 一个已存在的 member 但 score 不同，Redis 会 更新 score（先从跳表旧位置删除，再按新 score 插入新位置），同时更新字典中的 score。
追问三：ziplist 和 listpack 的区别？为什么要替换？
核心区别在于 prevlen 字段。ziplist 每个元素头部存储了前一个元素的长度，当前一个元素从 < 254 字节变为 ≥ 254 字节时，prevlen 从 1 字节变为 5 字节，可能引发后续所有元素的连锁更新（级联更新），最坏 O(N²)。listpack 去掉了 prevlen，每个元素只记录自身长度，彻底消除了这个问题。Redis 7.0 将所有使用 ziplist 的地方都替换成了 listpack。
ZSet 底层：小数据用 listpack（省内存），大数据用 skiplist + dict（高性能）。
跳表核心：多层索引 + 随机层数，O(logN) 查找，范围查询天然友好。
选跳表不选红黑树：范围查询快、实现简单、排名方便、内存可调。
两个结构各司其职：dict 管 O(1) 按 member 查 score，skiplist 管 O(logN) 按 score 范围查询。
Redis ZSet 底层采用 跳表 + 字典 的组合结构（元素少时用 listpack）。字典实现 O(1) 按 member 查 score，跳表实现 O(logN) 的范围查询和排名计算。Redis 选择跳表而非红黑树，是因为跳表在范围查询、实现复杂度、排名计算等方面都有优势。Redis 7.0 用 listpack 替换了 ziplist，彻底解决了级联更新问题。
