我们来说说 Redis 中 Zset 的底层实现

核心概括

Redis 的 Zset 同时具备两个核心特性：

1. 有序性：元素按分值（score）从小到大排列。
2. 唯一性：集合中的成员（member）是唯一的，但分值可以相同（分值相同时，按成员字典序排列）。

为了实现这种高效的、兼具“集合”和“有序”特性的数据结构，Redis 采用了两种底层数据结构相结合的方案：

• ziplist（压缩列表）或 listpack（紧凑列表）：用于元素数量少、元素体积小的场景，以节省内存。
• skiplist（跳跃表） + dict（哈希表）：用于通用场景，以提供高效的查询和范围操作。

这种根据条件动态切换底层结构的设计，体现了 Redis 在性能与内存之间做出的精妙权衡。

一、两种编码方式

在 Redis 内部，Zset 有两种编码方式，通过配置项 zset-max-ziplist-entries 和 zset-max-ziplist-value 来控制。

1.ziplist / listpack 编码

在 Redis 早期版本使用 ziplist，新版本（7.0+）逐渐用listpack替代 ziplist。我们以 listpack 为例讲解。

适用条件（同时满足）：

• 有序集合保存的元素数量小于 zset-max-ziplist-entries （默认 128）。
• 每个成员（member）的字符串长度小于 zset-max-ziplist-value （默认 64 字节）。

内存布局：
listpack 是一个紧凑的、连续内存块，它按 [member1, score1, member2, score2, ...] 的顺序，成对存储成员和分值。

• 按分值排序：所有元素在 listpack 内部就是严格按照分值升序排列的。
• 查找方式：由于是紧凑数组，查找需要线性遍历。但因为元素少，且内存连续，缓存友好，效率仍然可以接受。
• 插入/删除：需要移动后续元素，时间复杂度 O(N)。同样因为元素少，成本可控。

目的：在元素少且小的场景下，这种结构避免了额外的指针开销，极大地节约了内存。

2.skiplist 编码

当不满足上述任一条件时，Zset 会自动转换为 skiplist 编码。这才是 Zset 的“完全体”和核心实现。

它实际上是一个复合结构，包含一个跳跃表（skiplist）和一个字典（dict）。

arduino

typedef struct zset { dict *dict; // 哈希字典 zskiplist *zsl; // 跳跃表 } zset;

为什么需要两种结构？

• 跳跃表（zskiplist）：核心作用在于维护元素的有序性，支持高效的范围查询（如 ZRANGE, ZRANK）和插入/删除操作（平均 O(logN)）。
• 字典（dict）：核心作用在于提供O(1) 时间复杂度的成员查询（如 ZSCORE 命令，直接根据 member 获取其 score）。

如果只用跳跃表，查询成员分值需要 O(logN)。
如果只用字典，无法进行高效的范围操作。

因此，这种“空间换时间”的设计，让 Zset 既能快速进行单点查询，又能高效进行范围操作，是工程上的经典取舍。

二、核心数据结构剖析

1.跳跃表（Skip List）详解

跳跃表是一种多层级的有序链表，是平衡树的一种概率替代方案，实现更简单，在并发环境下也更有优势。

结构：

arduino

typedef struct zskiplist { struct zskiplistNode *header, *tail; // 头尾指针 unsigned long length; // 节点总数 int level; // 当前最大层数 } zskiplist; typedef struct zskiplistNode { sds ele; // 成员（SDS字符串） double score; // 分值 struct zskiplistNode *backward; // 后向指针（L0层，用于逆序） struct zskiplistLevel { struct zskiplistNode *forward; // 该层的前进指针 unsigned long span; // 该层到下一个节点的跨度（用于排名） } level[]; // 柔性数组，表示节点的层级 } zskiplistNode;

关键特性：

• 多层链表：每个节点随机一个层高（1-32）。level 数组长度即为层高。
• 有序性：节点首先按 score 排序，score 相同时，按 ele 的字典序排序。
• 查找路径：从最高层（header的最高层）开始，向右遍历找到最后一个 score 小于目标（或 score 相等但 ele 小于目标）的节点，然后下降一层继续。如此反复，直到第0层。这个过程时间复杂度平均 O(logN)。
• 跨度（span）：level[i].span 记录了从当前节点到 level[i].forward 节点之间，跨越了第0层的多少个节点。这是 ZRANK 命令（获取排名）能够 O(logN) 完成的关键。计算排名时，只需将搜索路径上所有符合方向的跨度累加即可。
• 后向指针（backward）：用于从尾到头遍历，支持 ZREVRANGE 等逆序操作。

2.字典（Dict）

就是一个标准的 Redis 哈希表，其作用是：

• 键（Key）：存储成员（member）。
• 值（Value）：存储该成员对应的分值（score，一个 double 类型）。
• 这个字典确保了对任意成员的O(1) 时间复杂度的访问。

三、操作流程示例

假设我们执行 ZADD myzset 10 “alice” 20 “bob” 30 “charlie”。

在 skiplist 编码下，内存结构示意图如下：

sql

zset / \ dict zskiplist (header) | (level=5) "alice" -> 10 | "bob" -> 20 | "charlie"-> 30 V +-------+-------+-------+ | Span | ... | Span | (高层，稀疏指针，快速跳跃) +-------+-------+-------+ | | V V +-------+-------+-------+ | score | ele | level | -> Node(10, "alice") | 10 |"alice"| 2 | +-------+-------+-------+ | | V (L0) V (L1) +-------+-------+-------+-------+-------+-------+ | score | ele | level | score | ele | level | -> Node(20, "bob") | 20 |"bob" | 3 | 20 |"bob" | 3 | +-------+-------+-------+-------+-------+-------+ | | V (L0) V (L1) +-------+-------+-------+-------+-------+-------+ | score | ele | level | score | ele | level | -> Node(30, "charlie") | 30 |"char" | 1 | 30 |"char" | 1 | +-------+-------+-------+-------+-------+-------+ | V (L0) NULL

关键操作如何工作：

1. ZSCORE myzset "bob"：直接在 dict 中查找键 "bob"，立即返回其值 20。O(1)。
2. ZRANGE myzset 1 2：从 zskiplist 的 header 出发，利用高层指针快速定位到起始节点（"bob"），然后沿低层指针遍历输出。O(logN + M)，M为返回元素个数。
3. ZRANK myzset "charlie"：从 zskiplist 的 header 出发，搜索 "charlie" 的路径，同时累加沿途的 span 值。最终得到的累加和就是其排名（从0开始）。O(logN)。
4. ZADD myzset 15 "david"：

• 先在 dict 中检查 "david" 是否存在（保证唯一性）。 然后在 zskiplist 中执行标准的跳表插入操作（O(logN)），找到插入位置。 最后，在 dict 中插入 "david" -> 15 的键值对。 整个操作O(logN)。

四、ZSET ZRANGE 操作序列图

下面这个序列图展示了当执行 ZRANGE myzset 1 3 命令时，Redis 内部不同组件之间的交互流程：

五、总结与要点

1. 双编码策略：Zset 是智能的，小数据用紧凑的 listpack 省内存，大数据用功能强大的“跳表+哈希”组合保性能。
2. 核心复合结构：skiplist + dict 是 Zset 的灵魂。skiplist 负责排序和范围操作，dict 负责快速单点访问。二者通过共享成员和分值的指针来保证数据一致性，没有冗余存储。
3. 跳跃表的角色：它不仅是一个有序链表，其跨度（span）属性是实现 O(logN) 复杂度的排名查询的关键。
4. 时间复杂度：

• 添加/删除/按分值查询：平均O(logN)。 按成员查分值：O(1)。 范围查询（如 ZRANGE）：O(logN + M)。 获取排名（ZRANK）：O(logN)。

1. 选择原因：相比于红黑树等严格平衡树，跳跃表实现简单，区间查询更直观，且在并发环境下更容易实现无锁优化。

面试回答

它的底层实现其实采用了两种数据结构相结合的‘混合’策略，目的是在内存使用和性能之间取得一个平衡。具体来说，它同时使用了：

1. 跳跃表（Skip List）
2. 字典（或哈希表，Hash Table）

这两种结构会共享集合中元素（成员）和分数（分值）的数据，但通过指针引用，所以不会造成双倍的内存开销。

为什么需要两种结构呢？
这主要是为了应对 Zset 不同的操作场景，让它们都能非常高效：

• 跳跃表的核心作用是维持元素的有序性。它的结构像多层链表，上层是“快速通道”，下层是“精确通道”。这使得范围型操作，以及插入、删除的平均时间复杂度都能在O(log N)级别，效率很高。
• 字典的核心作用是提供‘成员 -> 分数’ 的快速映射。当我们执行像去获取某个成员的分数或者更新一个已有成员这类操作时，如果能直接通过成员名（key）在哈希表里O(1)时间复杂度查到它的分数，那就太快了。如果只用跳跃表，这个查询就需要 O(log N)。

所以，简单来讲，可以把 Zset 想象成一个用哈希表做‘索引’，用跳跃表做‘排序清单’的组合体。哈希表保证了点查的极致速度，跳跃表保证了范围操作的效率。

不过，在 Redis 的后续版本中（我记得是 7.0 之后），为了进一步节省内存，还有另一种编码方式，叫 Ziplist（紧凑列表）。

• 当 Zset 同时满足两个条件时：1. 元素数量较少（默认 ≤ 128 个）；2. 每个成员字符串长度较短（默认 ≤ 64 字节），Redis 会使用一块连续内存的 ziplist 来存储。在这个链表里，成员和分数是挨个交替存放的，它因为少了跳跃表和哈希表的结构开销，所以非常节省内存。
• 一旦不满足上述任一条件，它就会自动转换成标准的“跳跃表+字典”结构。这个转换对使用者是无感的。

总结一下，我的理解是：
Zset 的底层会根据数据规模灵活选择：

• 对于小型集合，使用内存紧凑的 ziplist。
• 对于通用集合，使用‘跳跃表 + 字典’的双结构，同时保证高效的范围操作和单点查询。这也是一个在工程上非常经典的，‘用空间换时间’和‘空间时间平衡’的设计思路。