面试题：Redis Zset 的实现原理是什么？

Redis 的 ZSet（有序集合） 是 Redis 提供的一种高性能数据结构，既能保证元素的 唯一性，又能通过 分数（Score）进行排序。其底层实现结合了 跳表（Skip List） 和 哈希表（Hash Table），在数据量较小时使用 压缩列表（Ziplist）。以下是其核心实现原理：

一、ZSet 的核心特性

唯一性
成员（Member）不可重复，类似 Set。
有序性
按分数（Score）排序，支持范围查询（如 ZRANGE、ZRANGEBYSCORE）。
高效操作
- 插入、删除、查找：平均时间复杂度为 O(log N)。
- 范围查询：时间复杂度为 O(log N + M)（M 为返回元素数量）。

二、底层实现：跳表 + 哈希表

1. 跳表（Skip List）

作用：按分数排序存储成员，支持高效的 范围查询 和 排名操作。

结构特点：

多层级链表：每一层是一个升序链表，最底层包含所有元素，上层是索引层（概率性构建）。

节点结构：

typedef struct zskiplistNode {
    sds ele;                // 成员（Member）
    double score;           // 分数（Score）
    struct zskiplistNode *backward; // 后退指针（指向底层前驱节点）
    struct zskiplistLevel { // 层级结构
        struct zskiplistNode *forward; // 前进指针
        unsigned int span;             // 跨度（当前层跨越的节点数）
    } level[];
} zskiplistNode;

操作复杂度：插入、删除、查找为 O(log N)，范围查询为 O(log N + M)。

优势：
- 实现简单，无需像红黑树那样复杂的平衡调整。
- 插入/删除操作仅需修改相邻节点的指针，无需全局重构。
- 天然支持范围查询（如 ZRANGEBYSCORE），通过链表顺序遍历即可。

2. 哈希表（Hash Table）

作用：存储 成员到分数的映射，实现 O(1) 的分数查询。
结构特点：
- Key 为成员（Member），Value 为分数（Score）。
- 解决冲突方式：链地址法（Redis 6.0 后使用渐进式 Rehash）。
操作复杂度：查找、插入、删除为 O(1)。
优势：
- 快速判断成员是否存在，并获取其分数。
- 结合跳表，实现快速的排名和范围操作。

3. 小数据量时的压缩列表（Ziplist）

适用场景：当 ZSet 的元素数量和大小较小时（默认配置：元素数量 ≤ 128 且每个成员长度 ≤ 64 字节），Redis 使用 压缩列表 节省内存。
结构特点：
- 连续的内存块，减少指针开销。
- 插入/查找性能为 O(N)，适合小数据量。
缺点：随着数据量增长，性能下降，因此 Redis 会自动升级为跳表 + 哈希表结构。

三、ZSet 的操作逻辑

1. 插入元素（ZADD）

检查唯一性：通过哈希表判断成员是否已存在。
- 若存在，更新其分数并调整跳表位置。
- 若不存在，执行插入操作。
插入跳表：
- 从最高层开始查找插入位置。
- 随机生成层高（1~32），创建新节点并链接到各层。
更新哈希表：添加或更新成员到分数的映射。

2. 查询分数（ZSCORE）

通过哈希表：直接获取成员对应的分数（O(1) 时间复杂度）。

3. 范围查询（ZRANGEBYSCORE）

通过跳表：按分数区间遍历节点，返回结果（O(log N + M) 时间复杂度）。

4. 删除元素（ZREM）

通过哈希表：定位成员并删除其映射。
通过跳表：移除对应节点，并维护层级指针。

四、为什么选择跳表而不是其他结构？

1. 与红黑树的对比

实现复杂度：跳表的插入/删除操作无需旋转或再平衡，代码实现更简单。
范围查询：跳表天然支持顺序遍历，而红黑树需要中序遍历，实现复杂。
内存占用：跳表的层级通过概率性生成，平均空间冗余较少；红黑树需要额外存储颜色和父/子指针。

2. 与 B+ 树的对比

磁盘友好性：B+ 树适合磁盘存储的顺序读取，但在内存场景下冗余较高。
动态扩展性：B+ 树的节点分裂/合并操作需要全局调整，性能开销大。

3. 与压缩列表的对比

小数据优化：压缩列表节省内存，但插入/查找性能为 O(N)，适合小数据量。
自动升级：当数据量超过阈值时，Redis 会自动升级为跳表 + 哈希表结构。

五、典型应用场景

排行榜
- 利用 ZRANGE 快速获取 TOP N 用户，结合 ZSCORE 实时更新分数。
延迟队列
- 以时间戳为分数，通过 ZRANGEBYSCORE 获取到期任务。
范围统计
- 统计某时间段内的活跃用户（分数为时间戳）。

六、总结

Redis 的 ZSet 通过 跳表 + 哈希表 的组合，兼顾了 高效查询 和 排序操作 的需求：

跳表：解决排序和范围查询的高效性。
哈希表：提供成员到分数的快速映射。
压缩列表：在小数据量时节省内存。

这种设计使得 ZSet 在插入、删除、查找和范围查询等操作上均表现出色，成为 Redis 中功能强大的有序集合实现。

THE END

Redis 面试题