谈谈 Redis ZSet 底层实现？

面试考察点

当面试官问及 “Redis ZSet 底层实现” 时，他不仅仅是在考察你是否听说过 “跳跃表（Skip List）” 这个概念。这道题的核心考察点在于：

对核心数据结构的深入理解：你是否真正理解 ZSet 并非由单一数据结构实现，而是根据场景在 ziplist（压缩列表） 和 skiplist + dict（跳跃表+字典） 两种编码间切换。
对设计权衡的洞察力：面试官想考察你是否理解这种“双编码”设计背后的权衡——即内存效率与操作性能之间的取舍。
对跳跃表原理的掌握：你是否能清晰说明跳跃表的结构、查找/插入的平均时间复杂度（O(log N)），以及它相较于平衡二叉树（如红黑树）在实现上的优势。
理论联系实际的能力：你是否能将底层实现与实际应用场景（如排行榜、延迟队列）关联起来，解释为什么 ZSet 适合这些场景。
对 Redis 配置的认知：你是否了解控制编码切换的关键参数（zset-max-ziplist-entries 和 zset-max-ziplist-value），这体现了你的实战经验。

核心答案

Redis 的有序集合（ZSet）底层采用了两种方式，以适应不同规模的数据，在内存和性能之间取得最佳平衡：

ziplist（压缩列表）：当元素数量较少（默认 ≤ 128 个）且每个元素成员（value）的长度较小（默认 ≤ 64 字节）时使用。它是一种紧凑的、顺序型数据结构，能极大节省内存。
skiplist + dict（跳跃表 + 字典）：当不满足 ziplist 条件时启用。这种组合结构既保证了范围操作（如 ZRANGE）的高效性（通过跳跃表），又保证了单点查询（如 ZSCORE）的 O(1) 时间复杂度（通过字典）。

技术深度解析

1. 原理/机制

ziplist 编码：一个 ZSet 在 ziplist 中，成员（member）和分值（score）会作为两个紧邻的节点顺序存储。所有元素按照分值升序排列。查找需要遍历，因此只适用于小数据集。
- 存储布局示例：[prev-length][encoding][member-data][prev-length][encoding][score-data]...
skiplist + dict 编码：这是 ZSet 的标准形态，由两个数据结构组合而成：
- dict（字典）：存储 member -> score 的映射。这使得根据 member 查找、更新其 score 的操作时间复杂度为 O(1)。
- zskiplist（跳跃表）：存储了所有元素，并按照 score 排序。跳跃表的节点同时保存了 member 和 score。这使得按分值范围查询（如 ZRANGEBYSCORE）和获取排名的操作非常高效，平均时间复杂度为 O(log N)。
为什么要同时使用两者？ 这是一种空间换时间的设计。如果只用 dict，虽然查询快，但无法高效进行范围操作和排序；如果只用 skiplist，按 member 查询 score 会退化为 O(log N)。组合使用则兼顾了二者的优点。

2. 跳跃表（Skip List）精讲

跳跃表是一种多层级的有序链表。它的核心思想是通过建立多级索引来加速查找。

// 参考 Redis 源码（server.h）中的跳跃表节点与结构定义（概念性示意）
typedef struct zskiplistNode {
    sds ele; // 成员对象（SDS 字符串）
    double score; // 分值
    struct zskiplistNode *backward; // 后退指针，用于从表尾向表头遍历
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针，指向该层级的下一个节点
        unsigned long span; // 跨度，记录两个节点之间的距离，用于计算排名（rank）
    } level[]; // 柔性数组，节点的层级（Level），每一层都是一个单向链表
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 头尾节点指针
    unsigned long length; // 节点数量
    int level; // 当前表内最大的层数
} zskiplist;

查找过程：从最高层（header->level[high]）开始，沿着前进指针向右寻找，如果下一个节点的 score 小于目标值（或 score 相等但 member 字典序小），则继续前进；否则，下降一层，在更低层继续寻找。这类似于在有序数组上进行二分查找。
插入过程：插入新节点时，首先通过查找过程确定插入位置。然后，随机生成这个新节点的层高（范围在 1 到 32 之间，越高概率越低）。最后，像普通链表插入一样，调整相关层级的指针。
与平衡树的对比：
- 实现更简单：跳跃表的插入和删除操作，在确定位置后，只需修改相邻节点的指针，不需要像红黑树那样复杂的旋转再平衡。
- 范围查询更友好：跳跃表本身是有序链表，在找到范围起点后，可以直接在底层链表上顺序遍历，非常高效。而平衡树需要进行中序遍历。
- 内存占用：跳跃表每个节点平均有 1.33 个指针（Redis 实现），可能比平衡树的左右孩子指针稍多，但得益于其简单性，综合性能通常更优。

3. 最佳实践与常见误区

最佳实践：
- 理解编码转换：在开发中，如果 ZSet 的元素数量和大小会动态增长，需要预估其规模。如果大部分时候都是大数据集，可以适当调低 zset-max-ziplist-entries 参数，避免频繁的编码转换开销。
- 合理设置参数：对于已知的、固定的小数据集（如存储某个小型的系统配置项及其优先级），可以确保其符合 ziplist 条件，以节省内存。
- 优先使用范围操作：基于其底层是跳跃表，ZRANGE、ZRANGEBYSCORE、ZRANK 等操作非常高效，应优先使用，而非先 ZSCORE 再在客户端排序。
常见误区：
- 误区一：“ZSet 就是跳跃表实现的”。这是不准确的，忽略了 ziplist 这一重要编码和内存优化手段。
- 误区二：“ZSCORE 命令的时间复杂度是 O(log N)”。在 skiplist+dict 编码下，由于 dict 的存在，ZSCORE 是 O(1)。只有单独使用跳跃表时才是 O(log N)。
- 误区三：“跳跃表的层高是固定的”。Redis 中跳跃表节点的层高是随机生成的，这是其算法核心之一，保证了数据分布的随机性和平均性能。

总结

Redis ZSet 是一个设计精妙的数据结构，它通过 ziplist（省内存）和 skiplist+dict（高性能）的双编码策略，以及跳跃表与字典的协作，完美兼顾了排序、范围查询、单点查询的高效性，是实现排行榜、延时任务等场景的理想选择。

发布于2026年01月02日|18:42:18