提到 Redis 的 ZSet（有序集合），稍微看过一点底层原理的同学大概都能脱口而出：它的底层使用了跳表（Skip List）。

如果你去面试，面试官紧接着问：“那你能通俗地解释一下什么是跳表吗？为什么 Redis 的作者没有选择红黑树或者 B+ 树来实现它？” 此时往往就是分水岭了。

其实跳表并没有名字听起来那么高深，它的本质非常简单。今天我们就抛开枯燥的源码，用最通俗的语言，把跳表的演进过程和核心原理盘一遍。

1. 从普通的链表说起

要理解跳表，我们得先看普通的单向链表。

假设我们要存储一组有序的数字，存在一个单向链表里：
1 -> 3 -> 4 -> 5 -> 7 -> 8 -> 9 -> 10 -> 13

大家都知道，链表的优势在于插入和删除非常快，只要改变指针就行。但是它的查找极其龟速。
假设我要找数字 10，我只能从头节点 1 开始，一个一个往后顺藤摸瓜，时间复杂度是 O(N)。当数据量达到百万级别时，这种查询速度是不可接受的。

有什么办法能像数组那样，实现类似二分查找的快速定位呢？这就引出了跳表的核心思想：加索引。

2. 给链表修“快车道”

既然挨个遍历太慢，我们能不能每隔一个节点，就抽出一个节点来，形成一个“上层链表”？

就像这样：

​索引层： 1 ---->   4 ---->   7 ---->        10 --->
        |         |         |               |
底层链： 1 -> 3 -> 4 -> 5 -> 7 -> 8 -> 9 -> 10 -> 13

​

现在，如果我们再想找 10：

1. 我们先在索引层找：1 -> 4 -> 7 -> 10，找到了！

2. 然后通过向下的指针，直接定位到具体节点。

原来在底层需要查找 8 次，现在在索引层只需要查找 4 次。

如果数据量很大，一层索引可能还是不够快。那我们就在索引层的基础上，再抽出一层“超级索引”（快车道的快车道）：

​
第二层： 1 ---------->       7 ---------->
        |                   |
第一层： 1 ---->   4 ---->   7 ---->        10 --->
        |         |         |              |
底层链： 1 -> 3 -> 4 -> 5 -> 7 -> 8 -> 9 -> 10 -> 13

​

这时候查找 10 的路径变成了：
从第二层找，1 到 7；发现下一个节点是空的或者比 10 大，就降级到第一层；
在第一层从 7 走到 10，定位成功。

这种**“链表 + 多级索引”的数据结构，就是传说中的跳表（Skip List）**。它利用空间换时间的策略，让链表的查找时间复杂度从 O(N) 骤降到了 O(log N)，这已经和二分查找或者平衡二叉树的效率一样了。

3. 跳表的精髓：随机层数

看起来跳表很完美，但只要仔细一想就会发现一个致命问题：动态更新的灾难。

假设我们严格按照“每两个节点抽出一个索引”的规则，当我们频繁地插入和删除数据时，为了维持这种完美的比例，整个跳表的索引节点都需要重新调整。这就像排队时中间突然插进一个人，后面所有人的位置都要动，时间复杂度又退化了。

跳表的发明者非常聪明，他引入了一个绝妙的机制：抛硬币（随机化）。

当我们向跳表中插入一个新节点时，不再去死板地计算它应该在哪一层，而是靠“随机函数”来决定它的层数。

可以简单理解为这样一套流程：

1. 节点插入底层链表。

2. 抛硬币，如果是正面，这个节点就长高一层（提取到第一层索引）。

3. 继续抛，如果是正面，再长高一层。

4. 直到抛出反面，停止长高。

通过这种纯随机的方式，跳表巧妙地避开了索引结构重建的开销。虽然局部的索引分布可能不太均匀，但只要数据量足够大，整体的索引分布就会趋近于完美的概率分布，依然能保证 O(log N) 的查询效率。

注：Redis 实际实现中，长高一层的概率不是 50%，而是 25%（1/4）。这样可以减少索引节点占用的内存，也是 Redis 为了极致压榨内存做出的权衡。Redis 甚至限制了跳表的最高层数为 32 层（或者 64 层，视版本而定）。

4. Redis 中的跳表有什么特别之处？

理解了标准的跳表，我们再来看看 Redis 对跳表做了哪些魔改，让它完美契合 ZSet 的业务需求。

第一，支持反向遍历
标准的跳表是单向的，但 ZSet 经常需要倒序排行（比如 ZREVRANGE 命令获取从大到小的排行榜）。所以 Redis 把最底层的单向链表改造成了双向链表。每个节点不仅有向前的指针，还有一个向后的指针。

第二，跨度（Span）的概念
ZSet 有一个极高频的操作：查询某个元素的排名（ZRANK）。
如果单纯顺着跳表找，即便找到了元素，你也不知道它排第几。所以 Redis 在跳表的每个索引指针上，额外记录了一个数据叫 span（跨度），表示这个指针跨越了多少个底层节点。
这样一来，在查找节点的过程中，只要把经过的指针的 span 值累加起来，自然就得到了该元素的排名，效率极高。

5. 经典面试题：为什么不用红黑树或 B+ 树？

这是很多大厂特别爱问的题。其实 Redis 作者本人也正面回答过这个问题，主要有三个核心原因：

1. 内存占用更小
   红黑树的每个节点需要存放左右子节点和颜色等指针，开销固定。而跳表可以通过调整前面提到的“随机长高概率”（Redis 设置为 25%）来有效控制索引占用的内存空间，相比之下跳表更省内存。

2. 范围查询极度友好
   在 ZSet 中进行范围查询（比如获取积分在 80 到 100 之间的用户，ZRANGEBYSCORE）非常频繁。
   如果是红黑树，你需要先找到最小值，然后还得通过中序遍历去寻找剩余的值，逻辑相当复杂。
   而在跳表中，只需要像查找单个数据一样找到 80 分的节点，然后顺着底层链表一直往后遍历，直到遇到大于 100 的节点即可，极其顺滑。

3. 实现极其简单
   看一看红黑树的插入和删除逻辑，那复杂的左旋、右旋、变色操作，堪称脑力杀手。而跳表的逻辑非常直观，底层的 C 语言代码实现起来更清爽，后期的维护和 debug 也容易得多。在达到相同性能的前提下，程序员当然倾向于更简单的结构。

结语

其实很多底层的技术组件，一旦你扒开它的外衣，就会发现其核心思想往往源于生活中非常简单的常识。跳表就是这样一个将“索引”和“概率”结合到极致的艺术品。下次再遇到 ZSet 的排序和查询，你的脑海中应该就能浮现出那个抛硬币建楼层、底层双向相连的立体链表结构了。