面试题：为什么 Redis Zset 用跳表实现而不是红黑树？B+树？

Redis 的 有序集合（ZSet） 选择使用 跳表（Skip List） 而不是 红黑树（Red-Black Tree） 或 B+树，主要是基于以下多维度的权衡和优化需求。以下是详细分析：

一、跳表 vs 红黑树 vs B+树的核心对比

对比维度	跳表	红黑树	B+树
实现复杂度	简单（无旋转/再平衡操作）	复杂（需维护平衡因子、旋转逻辑）	复杂（节点分裂/合并操作）
范围查询效率	高效（链表顺序遍历，O(logN + M)）	需中序遍历（效率较低）	适合磁盘顺序读，内存场景冗余
内存占用	较低（概率性生成层数，平均空间冗余少）	较高（每个节点需存储父/子指针及颜色）	高（节点分裂导致额外空间消耗）
动态扩展性	插入/删除时无需全局重构结构，局部调整即可	插入/删除需旋转和颜色调整，逻辑复杂	节点分裂/合并需全局调整，性能开销大
并发优化潜力	易实现无锁（CAS 操作）	需复杂锁机制	锁粒度大，扩展性差
内存局部性	链表结构，内存局部性较好（适合缓存预取）	树结构，节点分布分散，缓存命中率较低	顺序存储，适合磁盘读取，内存场景冗余

二、跳表的优势详解

1. 实现简单，维护成本低

跳表的插入、删除和查找操作通过 随机生成层级 和 逐层更新指针 实现，无需复杂的旋转或再平衡操作。
红黑树 需要维护颜色属性、父/子指针，并处理多种旋转和染色逻辑（如左旋、右旋、颜色翻转），代码实现复杂且容易出错。
B+树 的节点分裂/合并操作需要全局调整，逻辑更为复杂。

2. 高效的范围查询

跳表的多级索引结构天然支持 顺序遍历，例如 ZRANGE、ZRANGEBYSCORE 等操作可通过跳表的底层链表直接遍历结果（时间复杂度为 O(logN + M)，M 为结果数量）。
红黑树 的范围查询需依赖 中序遍历，实现复杂且效率较低。
B+树 虽然支持范围查询，但其设计更偏向 磁盘存储优化（如顺序读取），在内存场景下冗余较高。

3. 内存占用更低

跳表的层级通过 概率性生成（如 1/2 概率升层），平均空间冗余较少。
红黑树 每个节点需存储 父/子指针 和 颜色属性，内存开销较大。
B+树 的节点分裂/合并操作会导致额外的空间消耗，尤其在内存场景下效率较低。

4. 动态扩展性与并发性能

跳表的插入和删除操作 局部调整即可完成，无需全局重构结构，适合高并发场景。
红黑树 和 B+树 的插入/删除操作可能引发 全局结构调整（如旋转、分裂/合并），性能开销大。

5. 工程友好性

跳表的代码实现简洁，调试和维护成本低，符合 Redis 的 高性能、高稳定性 设计理念。
红黑树 和 B+树 的实现复杂，维护成本高，且容易引入 Bug。

三、Redis ZSet 的实际实现

Redis 的 ZSet 采用 跳表 + 哈希表 的混合结构：

哈希表（dict）：用于通过成员名快速定位分数（O(1) 时间复杂度）。
跳表（skiplist）：用于按分数排序，支持范围查询和按排名查找（平均 O(logN) 复杂度）。

1. 小数据优化：压缩列表（ziplist）

当元素数量或大小较小时，Redis 使用 压缩列表 存储 ZSet，节省内存开销。
当数据量增长时，自动升级为 跳表 + 哈希表 结构。

2. 跳表节点结构

typedef struct zskiplistNode {
    sds ele;                // 成员对象
    double score;           // 分数
    struct zskiplistNode *backward; // 后向指针
    struct zskiplistLevel { // 多级索引
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

四、典型应用场景

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

五、总结

Redis 选择跳表而不是红黑树或 B+树，核心原因在于：

跳表实现简单，代码维护成本低，适合 Redis 的高性能需求。
跳表范围查询高效，天然支持 ZSet 的 ZRANGE、ZRANGEBYSCORE 等操作。
跳表内存占用较低，概率性生成层级减少冗余，适合内存数据库。
跳表动态扩展性强，插入/删除操作局部调整即可完成，适合高并发场景。

相比之下，红黑树和 B+树在 实现复杂度、内存占用、动态扩展性 方面存在劣势，难以满足 Redis 对 高性能、低延迟、易维护 的核心需求。

THE END

Redis 面试题