跳跃表(skiplist)是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。
跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点。在大部分情况下,跳跃表的效率可以和平衡树相媲美,并且因为跳跃表的实现比平衡树要来得更为简单,所以有不少程序都使用跳跃表来代替平衡树。
Redis使用跳跃表作为有序集合键的底层实现之一,如果一个有序集合包含的元素数量比较多,又或者有序集合中元素的成员(member)是比较长的字符串时,Redis就会使用跳跃表来作为有序集合键的底层实现。
以下是个典型的跳跃表例子
从图中可以看到, 跳跃表主要由以下部分构成:
- 表头(head):负责维护跳跃表的节点指针。
- 跳跃表节点:保存着元素值,以及多个层。
- 层:保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针,为了提高查找的效率,程序总是从高层先开始访问,然后随着元素值范围的缩小,慢慢降低层次。
- 表尾:全部由
NULL
组成,表示跳跃表的末尾。
因为跳跃表的定义可以在任何一本算法或数据结构的书中找到, 所以本章不介绍跳跃表的具体实现方式或者具体的算法, 而只介绍跳跃表在 Redis 的应用、核心数据结构和 API 。
跳跃表的实现
为了满足自身的功能需要, Redis 基于 William Pugh 论文中描述的跳跃表进行了以下修改:
- 允许重复的
score
值:多个不同的member
的score
值可以相同。 - 进行对比操作时,不仅要检查
score
值,还要检查member
:当score
值可以重复时,单靠score
值无法判断一个元素的身份,所以需要连member
域都一并检查才行。 - 每个节点都带有一个高度为 1 层的后退指针,用于从表尾方向向表头方向迭代:当执行 ZREVRANGE 或 ZREVRANGEBYSCORE 这类以逆序处理有序集的命令时,就会用到这个属性。
这个修改版的跳跃表由 redis.h/zskiplist
结构定义:
1 | typedef struct zskiplist { |
跳跃表的节点由 redis.h/zskiplistNode
定义:
1 | typedef struct zskiplistNode { |
以下是操作这两个数据结构的 API ,API 的用途与相应的算法复杂度:
函数 | 作用 | 复杂度 |
---|---|---|
zslCreateNode |
创建并返回一个新的跳跃表节点 | 最坏 O(1)O(1) |
zslFreeNode |
释放给定的跳跃表节点 | 最坏 O(1)O(1) |
zslCreate |
创建并初始化一个新的跳跃表 | 最坏 O(1)O(1) |
zslFree |
释放给定的跳跃表 | 最坏 O(N)O(N) |
zslInsert |
将一个包含给定 score 和 member 的新节点添加到跳跃表中 |
最坏 O(N)O(N) 平均 O(logN)O(logN) |
zslDeleteNode |
删除给定的跳跃表节点 | 最坏 O(N)O(N) |
zslDelete |
删除匹配给定 member 和 score 的元素 |
最坏 O(N)O(N) 平均 O(logN)O(logN) |
zslFirstInRange |
找到跳跃表中第一个符合给定范围的元素 | 最坏 O(N)O(N) 平均 O(logN)O(logN) |
zslLastInRange |
找到跳跃表中最后一个符合给定范围的元素 | 最坏 O(N)O(N) 平均 O(logN)O(logN) |
zslDeleteRangeByScore |
删除 score 值在给定范围内的所有节点 |
最坏 O(N2)O(N2) |
zslDeleteRangeByRank |
删除给定排序范围内的所有节点 | 最坏 O(N2)O(N2) |
zslGetRank |
返回目标元素在有序集中的排位 | 最坏 O(N)O(N) 平均 O(logN)O(logN) |
zslGetElementByRank |
根据给定排位,返回该排位上的元素节点 | 最坏 O(N)O(N) 平均 O(logN)O(logN) |
跳跃表的应用
和字典、链表或者字符串这几种在 Redis 中大量使用的数据结构不同, 跳跃表在 Redis 的唯一作用, 就是实现有序集数据类型。
跳跃表将指向有序集的 score
值和 member
域的指针作为元素, 并以 score
值为索引, 对有序集元素进行排序。
举个例子, 以下代码创建了一个带有 3 个元素的有序集:
1 | ZADD s 6 x 10 y 15 z |
在底层实现中, Redis 为 x
、 y
和 z
三个 member
分别创建了三个字符串, 值分别为 double
类型的 6
、 10
和 15
, 然后用跳跃表将这些指针有序地保存起来, 形成这样一个跳跃表:
为了方便展示, 在图片中我们直接将 member
和 score
值包含在表节点中, 但是在实际的定义中, 因为跳跃表要和另一个实现有序集的结构(字典)分享 member
和 score
值, 所以跳跃表只保存指向 member
和 score
的指针。 更详细的信息,请参考《有序集》章节。
小结
❑跳跃表是有序集合的底层实现之一。
❑Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成,其中zskiplist用于保存跳跃表信息(比如表头节点、表尾节点、长度),而zskiplistNode则用于表示跳跃表节点。
❑每个跳跃表节点的层高都是1至32之间的随机数。
❑在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的成员对象必须是唯一的。
❑跳跃表中的节点按照分值大小进行排序,当分值相同时,节点按照成员对象的大小进行排序。
参考地址
如果大家喜欢我的文章,可以关注个人订阅号。欢迎随时留言、交流。如果想加入微信群的话一起讨论的话,请加管理员简栈文化-小助手(lastpass4u),他会拉你们进群。