为什么 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]区间内的所有元素，必须：
1. 找到第一个 ≥ score1 的节点（O(log N)）
2. 从中序遍历开始，逐个访问后续节点，直到 > 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）
范围查询	⭐️⭐️⭐️ 极其高效（线性遍历）	⭐️ 需中序遍历，效率低
代码复杂度	⭐️⭐️⭐️ 简单，易维护	⭐️ 旋转逻辑复杂
内存开销	略高（指针多）	较低
并发扩展性	⭐️⭐️ 易加锁	⭐️ 旋转操作难并发
缓存友好性	⭐️⭐️ 底层链表连续	⭐️ 节点分散