Redis为什么用跳表实现有序集合？

Redis为什么用跳表实现有序集合？

Redis 之所以用 跳表（Skip List） 而不是 平衡树（如红黑树） 来实现有序集合（Sorted Set，zset），主要是基于以下几个考虑：

1. 跳表在范围查询上的优势

有序集合经常需要执行范围查询（如 ZRANGE、ZREVRANGE、ZRANGEBYSCORE）。跳表的结构使得它能够高效地：

• 按分值（score）范围查找：跳表的层级索引能够快速跳跃到目标范围，然后依次遍历，时间复杂度为 O(log N) + O(m)（m 是结果数量）。
• 按字典序遍历（分值相同时）：跳表的节点是双向链表结构，范围遍历时很高效。

相比之下，红黑树等平衡树结构虽然 查找单个元素的时间复杂度也是 O(log N)，但在 范围查询 时，遍历多个节点的成本较高，额外的指针操作可能导致性能下降。

2. 跳表实现简单，插入/删除操作更稳定

• 跳表的插入/删除：平均时间复杂度是 O(log N)，最坏情况下仍然是 O(log N)，且实现比红黑树更简单。
• 红黑树的插入/删除：虽然最坏情况下的时间复杂度也是 O(log N)，但维护平衡（涉及旋转操作）带来额外的复杂度。

跳表的插入/删除只需要调整少量指针，不涉及复杂的旋转，容易实现，也降低了调试和维护成本。

3. 跳表在并发场景下更友好

• Redis 是单线程的，但在某些场景下，跳表比红黑树更容易扩展到 多线程环境，因为它的结构更适合 无锁并发（Redis 本身是单线程的，所以这里的优势主要是对于扩展性和其他类似的应用）。

4. 空间占用：跳表 vs. 红黑树

• 跳表的额外空间开销 是 每个元素需要存多个索引层级的指针，但它并不比红黑树的父子关系指针消耗更多。
• 红黑树每个节点通常需要存储颜色信息、父指针、左右子树指针等，对小数据量的开销更大。

Redis 通过合理的随机层级设计，使跳表的空间开销不会太高，并且跳表的结构使得它在 节省 CPU 指令 上比红黑树更高效。

5. Redis 并没有完全放弃平衡树

Redis 的 zset 结构实际上是 跳表（skiplist）+ 哈希表（dict）的组合：

• 哈希表（dict） 用于 O(1) 时间复杂度的查找，适用于 ZSCORE、ZINCRBY 等操作。
• 跳表（skiplist） 用于 范围查询、排序 等操作。

总结

由于 Redis 需要高效的范围查询、插入和删除，同时希望实现尽可能简单，跳表是 比红黑树更合适的选择。