为什么 Redis 的有序集合（Sorted Set）要用跳表（Skip List）实现？深入解析设计哲学与实战对比
视频看了几百小时还迷糊？关注我，几分钟让你秒懂！
在 Redis 中，有序集合（Sorted Set / ZSet）是一个极其重要的数据结构，广泛用于排行榜、延迟任务、带权重的队列等场景。但你有没有想过：为什么 Redis 不用更“经典”的平衡树（如红黑树），而是选择相对冷门的跳表（Skip List）来实现 ZSet？
很多人第一反应是：“跳表性能好？”
——这没错，但只说对了一半。
真正的原因，是Redis 在性能、内存、代码复杂度和并发扩展性之间做出的精妙权衡。本文将从原理、源码、实战三个维度，彻底讲清楚这个问题，并附上Java + Spring Boot 对比案例，让你不仅知其然，更知其所以然。
一、ZSet 的核心需求是什么？
在设计 ZSet 底层结构前，Redis 团队首先明确了它的核心操作需求：
| 操作 | 时间复杂度要求 | 说明 |
|---|---|---|
| 插入元素（ZADD） | O(log N) | 需要按 score 排序 |
| 删除元素（ZREM） | O(log N) | 快速定位并删除 |
| 范围查询（ZRANGE） | O(log N + M) | M 是返回元素个数 |
| 按分值范围查询（ZRANGEBYSCORE） | O(log N + M) | 如查 80~100 分的用户 |
| 获取排名（ZRANK） | O(log N) | 元素在有序序列中的位置 |
✅关键点：不仅要支持快速插入/删除，还要高效支持范围遍历！
二、为什么不选红黑树（Red-Black Tree）？
红黑树是 C++ STLstd::map、JavaTreeMap的底层实现，具备 O(log N) 的增删改查能力。那为什么 Redis 不用它？
❌ 红黑树的致命缺陷：不擅长范围查询！
- 红黑树是二叉搜索树，虽然中序遍历可得有序序列，但遍历时需要递归或栈模拟，无法像链表那样“一路 next”。
- 要获取
[score1, score2]区间内的所有元素，必须：- 找到第一个 ≥ score1 的节点（O(log N)）
- 从中序遍历开始，逐个访问后续节点，直到 > score2
- 问题：中序遍历不是“线性指针跳转”，实现复杂，且缓存局部性差（节点分散在堆内存）。
📌结论：红黑树适合“单点查询”，但不适合 Redis 这种高频范围扫描的场景。
三、跳表（Skip List）的三大优势
跳表由 William Pugh 在 1989 年提出，是一种基于概率的多层链表结构。它完美契合 Redis 的需求。
✅ 优势 1：天然支持高效范围查询
跳表的底层是一条有序双向链表（Redis 实际用的是双向链表 + 层级指针），这意味着：
- 一旦定位到起始节点，后续元素可通过
next指针线性遍历，缓存友好。 ZRANGE、ZRANGEBYSCORE等命令实现极其简单高效。
// Redis 跳表节点定义（简化版） typedef struct zskiplistNode { sds ele; // 元素值（字符串） double score; // 分值 struct zskiplistNode *backward; // 后退指针（用于反向遍历） struct zskiplistLevel { struct zskiplistNode *forward; // 前进指针 unsigned long span; // 跨度（用于快速计算排名） } level[]; // 柔性数组，层级动态 } zskiplistNode;🔍 注意：
backward指针让跳表支持O(1) 反向遍历（如ZREVRANGE），这是普通跳表没有的优化！
✅ 优势 2：实现简单，代码可读性强
- 红黑树：插入/删除需处理5 种旋转 + 颜色翻转，代码复杂，易出错。
- 跳表：插入只需随机决定层数 + 更新指针，逻辑清晰。
Redis 作者Salvatore Sanfilippo（antirez）曾公开表示：
“跳表的代码比红黑树少得多，更容易调试和维护。”
对于一个单线程、追求稳定的系统来说，简单即可靠。
✅ 优势 3：天然支持并发扩展（未来兼容性）
虽然 Redis 主线程是单线程，但跳表在并发场景下更容易加锁优化：
- 可对不同层级或区间加细粒度锁。
- 而红黑树的旋转操作涉及多个节点，锁粒度难控制。
💡 虽然 Redis 目前没用多线程处理命令，但设计时已考虑未来可能性。
四、跳表 vs 其他结构：Redis 的完整选择逻辑
Redis 对 ZSet 的实现其实是混合策略：
| 元素数量 & 大小 | 底层结构 | 原因 |
|---|---|---|
| ≤ 128 个元素，且每个成员 ≤ 64 字节 | ziplist（压缩列表） | 内存紧凑，连续存储，缓存友好 |
| 超出上述阈值 | skiplist + hashtable | 跳表负责排序，哈希表负责 O(1) 查找成员是否存在 |
📌双结构协同：
- 跳表：按 score 排序，支持范围查询。
- 哈希表：通过 member 快速判断是否已存在（避免重复插入）。
五、Spring Boot 实战：排行榜场景对比
✅ 正确使用 ZSet（跳表优势体现）
@RestController public class LeaderboardController { @Autowired private StringRedisTemplate redisTemplate; // 更新玩家分数 public void updateScore(String playerId, double score) { redisTemplate.opsForZSet().add("game:leaderboard", playerId, score); } // 获取 Top 10（高效！O(logN + 10)） public Set<String> getTop10() { return redisTemplate.opsForZSet() .reverseRange("game:leaderboard", 0, 9); // 自动利用跳表有序性 } // 获取分数在 80~100 之间的玩家（范围查询） public Set<String> getPlayersByScore(double min, double max) { return redisTemplate.opsForZSet() .rangeByScore("game:leaderboard", min, max); } }📌性能：即使有 100 万玩家，
getTop10()依然毫秒级响应。
❌ 反例：用 TreeMap 模拟 ZSet（自造轮子）
// 错误：在 Java 内存中维护排行榜（无法分布式，内存爆炸） private final TreeMap<Double, Set<String>> leaderboard = new TreeMap<>(); public void addPlayer(String playerId, double score) { leaderboard.computeIfAbsent(score, k -> new HashSet<>()).add(playerId); } // 获取 Top 10：需要遍历整个 TreeMap！ public List<String> getTop10Manual() { return leaderboard.descendingMap().values().stream() .flatMap(Set::stream) .limit(10) .collect(Collectors.toList()); }⚠️问题：
- 无法跨服务共享
- 内存占用大
- 范围查询效率低（需遍历）
六、常见误区澄清
❓ 误区 1：“跳表性能不如红黑树？”
- 事实：在平均情况下，跳表的查找/插入/删除复杂度也是O(log N)，常数因子略大，但范围查询远胜红黑树。
- Redis 官方测试表明：跳表在 ZSet 场景下综合性能更优。
❓ 误区 2：“Redis 为什么不用 B+ 树？”
- B+ 树适合磁盘存储（减少 I/O），而 Redis 是纯内存系统，不需要考虑磁盘页。
- B+ 树实现更复杂，且内存中跳表的缓存局部性并不差。
七、总结：Redis 选择跳表的核心原因
| 维度 | 跳表（Skip List） | 红黑树（RB-Tree） |
|---|---|---|
| 范围查询 | ⭐️⭐️⭐️ 极其高效（线性遍历） | ⭐️ 需中序遍历，效率低 |
| 代码复杂度 | ⭐️⭐️⭐️ 简单，易维护 | ⭐️ 旋转逻辑复杂 |
| 内存开销 | 略高（指针多） | 较低 |
| 并发扩展性 | ⭐️⭐️ 易加锁 | ⭐️ 旋转操作难并发 |
| 缓存友好性 | ⭐️⭐️ 底层链表连续 | ⭐️ 节点分散 |
✅Redis 的选择逻辑：
“在内存系统中，为高频范围查询场景，牺牲少量内存，换取极致的遍历性能和代码简洁性。”
结语
Redis 的每一个设计决策，都是对实际场景、性能、可维护性的深思熟虑。跳表或许不是“最强大”的数据结构，但它是ZSet 场景下的最优解。
下次当你调用redisTemplate.opsForZSet().rangeByScore()时，不妨想象一下：此刻，Redis 正在用一条优雅的多层链表，为你飞速定位数据！
视频看了几百小时还迷糊？关注我，几分钟让你秒懂！