如果您对 跳跃表不太了了解请先阅读 🔖 跳跃表
跳跃表（skiplist）是一种有序数据结构， 它通过在每个节点中维持多个指向其他节点的指针， 从而达到快速访问节点的目的。
跳跃表支持平均 O(\log N) 最坏 O(N) 复杂度的节点查找， 还可以通过顺序性操作来批量处理节点。
在大部分情况下， 跳跃表的效率可以和平衡树相媲美， 并且因为跳跃表的实现比平衡树要来得更为简单， 所以有不少程序都使用跳跃表来代替平衡树。
Redis 使用跳跃表作为有序集合键的底层实现之一： 如果一个有序集合包含的元素数量比较多， 又或者有序集合中元素的成员（member）是比较长的字符串时， Redis 就会使用跳跃表来作为有序集合键的底层实现。
举个例子， fruit-price 是一个有序集合键， 这个有序集合以水果名为成员， 水果价钱为分值， 保存了 130 款水果的价钱：
redis> ZRANGE fruit-price 0 2 WITHSCORES
1) "banana"
2) "5"
3) "cherry"
4) "6.5"
5) "apple"
6) "8"
redis> ZCARD fruit-price
(integer) 130
fruit-price 有序集合的所有数据都保存在一个跳跃表里面， 其中每个跳跃表节点（node）都保存了一款水果的价钱信息， 所有水果按价钱的高低从低到高在跳跃表里面排序：
- 跳跃表的第一个元素的成员为
"banana"， 它的分值为5； - 跳跃表的第二个元素的成员为
"cherry"， 它的分值为6.5； - 跳跃表的第三个元素的成员为
"apple"， 它的分值为8；
诸如此类。
和链表、字典等数据结构被广泛地应用在 Redis 内部不同， Redis 只在两个地方用到了跳跃表， 一个是实现有序集合键， 另一个是在集群节点中用作内部数据结构， 除此之外， 跳跃表在 Redis 里面没有其他用途。
表 5-1 列出了跳跃表的所有操作 API 。
表 5-1 跳跃表 API
| 函数 | 作用 | 时间复杂度 |
|---|---|---|
zslCreate |
创建一个新的跳跃表。 | O(1) |
zslFree |
释放给定跳跃表，以及表中包含的所有节点。 | O(N) ， N 为跳跃表的长度。 |
zslInsert |
将包含给定成员和分值的新节点添加到跳跃表中。 | 平均 O(\log N) ，最坏 O(N) ， N 为跳跃表长度。 |
zslDelete |
删除跳跃表中包含给定成员和分值的节点。 | 平均 O(\log N) ，最坏 O(N) ， N 为跳跃表长度。 |
zslGetRank |
返回包含给定成员和分值的节点在跳跃表中的排位。 | 平均 O(\log N) ，最坏 O(N) ， N 为跳跃表长度。 |
zslGetElementByRank |
返回跳跃表在给定排位上的节点。 | 平均 O(\log N) ，最坏 O(N) ， N 为跳跃表长度。 |
zslIsInRange |
给定一个分值范围（range）， 比如 0 到 15 ， 20 到 28 ，诸如此类， 如果给定的分值范围包含在跳跃表的分值范围之内， 那么返回 1 ，否则返回 0 。 |
通过跳跃表的表头节点和表尾节点， 这个检测可以用 O(1) 复杂度完成。 |
zslFirstInRange |
给定一个分值范围， 返回跳跃表中第一个符合这个范围的节点。 | 平均 O(\log N) ，最坏 O(N) 。 N 为跳跃表长度。 |
zslLastInRange |
给定一个分值范围， 返回跳跃表中最后一个符合这个范围的节点。 | 平均 O(\log N) ，最坏 O(N) 。 N 为跳跃表长度。 |
zslDeleteRangeByScore |
给定一个分值范围， 删除跳跃表中所有在这个范围之内的节点。 | O(N) ， N 为被删除节点数量。 |
zslDeleteRangeByRank |
给定一个排位范围， 删除跳跃表中所有在这个范围之内的节点。 | O(N) ， N 为被删除节点数量。 |
- 跳跃表是有序集合的底层实现之一， 除此之外它在 Redis 中没有其他应用。
- Redis 的跳跃表实现由
zskiplist和zskiplistNode两个结构组成， 其中zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度）， 而zskiplistNode则用于表示跳跃表节点。 - 每个跳跃表节点的层高都是
1至32之间的随机数。 - 在同一个跳跃表中， 多个节点可以包含相同的分值， 但每个节点的成员对象必须是唯一的。
- 跳跃表中的节点按照分值大小进行排序， 当分值相同时， 节点按照成员对象的大小进行排序。