Redis为什么要使用跳跃表

发表于 | 更新于: | 分类于

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

跳跃表支持平均O（logN）、最坏O（N）复杂度的节点查找，还可以通过顺序性操作来批量处理节点。在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。

Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员（member）是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。

以下是个典型的跳跃表例子

http://static.cyblogs.com/skiplist.png

从图中可以看到， 跳跃表主要由以下部分构成：

  • 表头（head）：负责维护跳跃表的节点指针。
  • 跳跃表节点：保存着元素值，以及多个层。
  • 层：保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针，为了提高查找的效率，程序总是从高层先开始访问，然后随着元素值范围的缩小，慢慢降低层次。
  • 表尾：全部由 NULL 组成，表示跳跃表的末尾。

因为跳跃表的定义可以在任何一本算法或数据结构的书中找到， 所以本章不介绍跳跃表的具体实现方式或者具体的算法， 而只介绍跳跃表在 Redis 的应用、核心数据结构和 API 。

跳跃表的实现

为了满足自身的功能需要， Redis 基于 William Pugh 论文中描述的跳跃表进行了以下修改：

  1. 允许重复的 score 值：多个不同的 member 的 score 值可以相同。
  2. 进行对比操作时，不仅要检查 score 值，还要检查 member ：当 score 值可以重复时，单靠 score 值无法判断一个元素的身份，所以需要连 member 域都一并检查才行。
  3. 每个节点都带有一个高度为 1 层的后退指针，用于从表尾方向向表头方向迭代：当执行 ZREVRANGE 或 ZREVRANGEBYSCORE 这类以逆序处理有序集的命令时，就会用到这个属性。

这个修改版的跳跃表由 redis.h/zskiplist 结构定义：

1
2
3
4
5
6
7
8
typedef struct zskiplist {
    // 头节点，尾节点
    struct zskiplistNode *header, *tail;
    // 节点数量
    unsigned long length;
    // 目前表内节点的最大层数
    int level;
} zskiplist;

跳跃表的节点由 redis.h/zskiplistNode 定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct zskiplistNode {
    // member 对象
    robj *obj;
    // 分值
    double score;
    // 后退指针
    struct zskiplistNode *backward;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 这个层跨越的节点数量
        unsigned int span;
    } level[];
} 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(log⁡N)
zslDeleteNode 删除给定的跳跃表节点 最坏 O(N)O(N)
zslDelete 删除匹配给定 member 和 score 的元素 最坏 O(N)O(N) 平均 O(logN)O(log⁡N)
zslFirstInRange 找到跳跃表中第一个符合给定范围的元素 最坏 O(N)O(N) 平均 O(logN)O(log⁡N)
zslLastInRange 找到跳跃表中最后一个符合给定范围的元素 最坏 O(N)O(N) 平均 O(logN)O(log⁡N)
zslDeleteRangeByScore 删除 score 值在给定范围内的所有节点 最坏 O(N2)O(N2)
zslDeleteRangeByRank 删除给定排序范围内的所有节点 最坏 O(N2)O(N2)
zslGetRank 返回目标元素在有序集中的排位 最坏 O(N)O(N) 平均 O(logN)O(log⁡N)
zslGetElementByRank 根据给定排位，返回该排位上的元素节点 最坏 O(N)O(N) 平均 O(logN)O(log⁡N)

跳跃表的应用

和字典、链表或者字符串这几种在 Redis 中大量使用的数据结构不同， 跳跃表在 Redis 的唯一作用， 就是实现有序集数据类型。

跳跃表将指向有序集的 score 值和 member 域的指针作为元素， 并以 score 值为索引， 对有序集元素进行排序。

举个例子， 以下代码创建了一个带有 3 个元素的有序集：

1
2
3
4
5
6
7
8
9
10
redis> ZADD s 6 x 10 y 15 z
(integer) 3

redis> ZRANGE s 0 -1 WITHSCORES
1) "x"
2) "6"
3) "y"
4) "10"
5) "z"
6) "15"

在底层实现中， Redis 为 x 、 y 和 z 三个 member 分别创建了三个字符串， 值分别为 double 类型的 6 、 10 和 15 ， 然后用跳跃表将这些指针有序地保存起来， 形成这样一个跳跃表：

http://static.cyblogs.com/QQ20200329-225534@2x.jpg

为了方便展示， 在图片中我们直接将 member 和 score 值包含在表节点中， 但是在实际的定义中， 因为跳跃表要和另一个实现有序集的结构（字典）分享 member 和 score 值， 所以跳跃表只保存指向 member 和 score 的指针。 更详细的信息，请参考《有序集》章节。

小结

❑跳跃表是有序集合的底层实现之一。

❑Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度），而zskiplistNode则用于表示跳跃表节点。

❑每个跳跃表节点的层高都是1至32之间的随机数。

❑在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。

❑跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。

参考地址

如果大家喜欢我的文章，可以关注个人订阅号。欢迎随时留言、交流。如果想加入微信群的话一起讨论的话，请加管理员简栈文化-小助手（lastpass4u），他会拉你们进群。

简栈文化服务订阅号