播面 Redis 有序集合(ZSET)为何选用跳表
Redis有序集合使用跳表，因其实现比红黑树更简单，易于维护。同时，它提供了接近的 O(log N) 高性能，且对范围查询十分高效，是性能与实现复杂度的最佳平衡。
这是一个非常经典且重要的问题。Redis 选择使用跳表（Skip List）来实现有序集合（Sorted Set / ZSET），而不是更常见的平衡树（如红黑树），是基于多方面权衡的结果。
简单来说，核心原因在于：跳表在实现简单性、性能表现和易于扩展等方面，提供了一个优于平衡树的综合方案。
下面我们从几个维度来详细拆解这个原因。
1. 什么是 Redis 的有序集合（ZSET）？
首先，我们要明白 ZSET 的需求是什么。它是一个集合，需要保证元素的唯一性，同时每个元素都有一个与之关联的浮点数分数（score）。ZSET 的核心功能是根据这个分数进行排序。
它需要高效地支持以下操作：
- 添加/更新元素 (
ZADD):O(log N) - 删除元素 (
ZREM):O(log N) - 通过成员查找分数 (
ZSCORE):O(1) - 通过排名范围查找成员 (
ZRANGE):O(log N + M)，其中 M 是返回的元素数量 - 通过分数范围查找成员 (
ZRANGEBYSCORE):O(log N + M) - 获取成员的排名 (
ZRANK):O(log N)
2. Redis 的实际实现：跳表 + 哈希表
在深入比较之前，必须了解 Redis 的 ZSET 并非单独由跳表实现。它是一个复合结构，由一个哈希表（Hash Table）和一个跳表（Skip List）共同构成。
- 哈希表 (dict)：存储了从
成员（member）到分数（score）的映射。这使得ZSCORE这类通过成员查找分数的操作，时间复杂度可以达到 O(1)。如果没有哈希表，单纯在跳表中查找一个成员需要O(log N)。 - 跳表 (zskiplist)：存储了从
分数（score）到成员（member）的映射，并按照分数进行排序。这使得所有和排序、范围相关的操作（如ZRANGE,ZRANGEBYSCORE）都能高效执行。
这两个结构通过指针共享成员和分数的数据，避免了数据冗余。
现在，我们来分析为什么在需要排序的部分，Redis 选择了跳表而不是平衡树。
3. 跳表 vs. 平衡树（如红黑树）
| 特性 | 跳表 (Skip List) | 平衡二叉搜索树 (如红黑树) | 在 Redis 场景下的优劣分析 |
|---|---|---|---|
| 实现复杂度 | 更简单 | 非常复杂 | [跳表胜出] 这是最关键的优势之一。跳表的插入和删除逻辑比红黑树的旋转和颜色翻转等再平衡（rebalancing）操作要简单得多。代码更简洁，意味着更易于理解、维护和调试，也更不容易出错。 |
| 性能 (时间复杂度) | 查找、插入、删除的平均复杂度为 O(log N) | 查找、插入、删除的严格最坏复杂度为 O(log N) | 理论上，红黑树的性能更稳定，没有“最坏情况”。但跳表的概率性保证了其性能在实践中极少退化，其 O(log N) 的表现已经足够优秀和稳定。对于 Redis 这种工程项目，常数项和实现效率同样重要。 |
| 范围查询效率 | 非常高效 | 高效 | [跳表略胜] ZRANGEBYSCORE 这类操作，在跳表中找到起始节点后，只需在最底层的链表上进行一次线性遍历即可。这种遍历方式对 CPU 缓存非常友好。而红黑树需要进行中序遍历，这涉及到指针在树中的上下移动，缓存命中率可能不如跳表。 |
| 内存占用 | 相对较高 | 相对较低 | [红黑树略胜] 跳表的每个节点包含多个指针（层数是随机的），平均指针数比红黑树节点（通常是父、左、右子节点指针）要多，因此内存占用会稍高一些。但对于现代服务器来说，这点内存开销通常在可接受范围内。 |
| 并发控制 | 更容易 | 更困难 | [跳表胜出] 尽管 Redis 核心命令处理是单线程的，但数据结构的设计仍然会考虑并发友好性。跳表的更新操作通常只影响局部节点，锁的粒度可以很小。而红黑树的再平衡操作可能涉及从叶节点到根节点的路径，需要锁住更大范围的节点，并发性能较差。 |
4. 总结：为什么是跳表？
综合以上对比，Redis 选择跳表的原因可以归结为以下几点：
- 实现简单，易于维护：这是最主要的原因。相比红黑树复杂精妙的平衡操作，跳表的实现更加直观和简洁，大大降低了开发和维护成本。
- 性能优秀且足够稳定：虽然跳表的性能是概率性的
O(log N)，但实践证明其性能非常稳定，与红黑树在同一量级，完全能满足 Redis 的高性能需求。 - 范围查询友好：跳表的链式结构使得范围查询（如
ZRANGE）的实现天然高效，且对 CPU 缓存友好。 - 易于扩展和实现额外功能：跳表的结构使其很容易实现
ZRANK（获取排名）功能。每个节点的跨度（span）信息记录了到下一个节点的距离，通过累加跨度可以快速计算出排名。
最终，Redis 的作者 Antirez 在设计时做出了一个非常务实的工程决策：选择一个实现简单、性能优异、且能完美满足业务需求的数据结构。跳表正是在这个权衡下的最佳选择。
补充：Ziplist / Listpack 优化
值得一提的是，当有序集合的元素数量较少且每个元素的值不大时，Redis 并不会直接使用“哈希表+跳表”的结构，因为这样太耗费内存。
在这种情况下，Redis 会使用一种叫做 Ziplist（在较新的版本中被 Listpack 替代）的紧凑列表结构来存储。Ziplist/Listpack 是一块连续的内存，它将所有元素（成员和分数）紧凑地排列在一起，极大地节省了内存。
当 ZSET 中的元素数量或元素大小超过预设的阈值时，Redis 会自动将其内部编码从 ziplist/listpack 转换为 skiplist（即哈希表+跳表）。这种根据数据规模自动转换底层实现的优化策略，体现了 Redis 对性能和内存效率的极致追求。