跳跃表

跳跃表（skiplist）是一种随机化的数据， 由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出， 跳跃表以有序的方式在层次化的链表中保存元素， 效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成， 并且比起平衡树来说， 跳跃表的实现要简单直观得多。

以下是个典型的跳跃表例子（图片来自维基百科）：

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

• 表头（head）：负责维护跳跃表的节点指针。

• 跳跃表节点：保存着元素值，以及多个层。

• 层：保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针，为了提高查找的效率，程序总是从高层先开始访问，然后随着元素值范围的缩小，慢慢降低层次。

• 表尾：全部由 NULL 组成，表示跳跃表的末尾。

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

跳跃表的实现

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

1. 允许重复的 score 值：多个不同的 member 的 score 值可以相同。

2. 进行对比操作时，不仅要检查 score 值，还要检查 member ：当 score 值可以重复时，单靠 score 值无法判断一个元素的身份，所以需要连 member 域都一并检查才行。

3. 每个节点都带有一个高度为 1 层的后退指针，用于从表尾方向向表头方向迭代：当执行 zrevrange 或 zrevrangebyscore 这类以逆序处理有序集的命令时，就会用到这个属性。

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

typedef struct zskiplist {

    // 头节点，尾节点
    struct zskiplistNode *header, *tail;

    // 节点数量
    unsigned long length;

    // 目前表内节点的最大层数
    int level;

} zskiplist;

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

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)\)
zslFreeNode	释放给定的跳跃表节点	最坏 \(O(1)\)
zslCreate	创建并初始化一个新的跳跃表	最坏 \(O(1)\)
zslFree	释放给定的跳跃表	最坏 \(O(N)\)
zslInsert	将一个包含给定 score 和 member 的新节点添加到跳跃表中	最坏 \(O(N)\) 平均 \(O(\log N)\)
zslDeleteNode	删除给定的跳跃表节点	最坏 \(O(N)\)
zslDelete	删除匹配给定 member 和 score 的元素	最坏 \(O(N)\) 平均 \(O(\log N)\)
zslFirstInRange	找到跳跃表中第一个符合给定范围的元素	最坏 \(O(N)\) 平均 \(O(\log N)\)
zslLastInRange	找到跳跃表中最后一个符合给定范围的元素	最坏 \(O(N)\) 平均 \(O(\log N)\)
zslDeleteRangeByScore	删除 score 值在给定范围内的所有节点	最坏 \(O(N^2)\)
zslDeleteRangeByRank	删除给定排序范围内的所有节点	最坏 \(O(N^2)\)
zslGetRank	返回目标元素在有序集中的排位	最坏 \(O(N)\) 平均 \(O(\log N)\)
zslGetElementByRank	根据给定排位，返回该排位上的元素节点	最坏 \(O(N)\) 平均 \(O(\log N)\)

跳跃表的应用

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

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

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

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 ， 然后用跳跃表将这些指针有序地保存起来， 形成这样一个跳跃表：

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

小结

• 跳跃表是一种随机化数据结构，查找、添加、删除操作都可以在对数期望时间下完成。

• 跳跃表目前在 Redis 的唯一作用，就是作为有序集类型的底层数据结构（之一，另一个构成有序集的结构是字典）。

• 为了满足自身的需求，Redis 基于 William Pugh 论文中描述的跳跃表进行了修改，包括：

  1. score 值可重复。

  2. 对比一个元素需要同时检查它的 score 和 memeber 。

  3. 每个节点带有高度为 1 层的后退指针，用于从表尾方向向表头方向迭代。