Redis笔记-结构篇-跳跃列表

注意：本系列文章分析的 Redis 源码版本：https://github.com/Sidfate/redis ，是文章发布时间的最新版。

大家知道 redis 五种常用的数据结构有：字符串（string）， 散列（hash）， 列表（list）， 集合（set）和有序集合（sorted set） 。相对而言 sorted set（以下简称为zset） 用的相对较少，它他的实现结构却很有趣，这种结构被称为 跳跃列表 skiplist ，后面我还会结合一个日常生活的例子来解释它。

首先简单介绍下 zset 是个啥有什么用，已经了解的童鞋可以直接到下一章节。

有序集合的数据类型，类似于集合（set）和散列表（hash）之间的混合。有序集合和集合一样，元素是唯一的。并且有序集合中的每个元素都可以对应一个score值，所以它也像一个散列表。另外，有序集合中的元素可以根据score值进行排序遍历。

zset

看了上面的介绍，你可能已经猜到了，zset 是 2 种数据结构的结合，在源码的注释中是这么解释的：

Zset 是使用了 2 个数据结构来保存相同元素的有序集合，同时还能保证复杂度为 O(log(N)) 的插入和删除操作。Zset 中的元素被添加到一个散列表中，保存着 Redis对象 - score 的映射关系。同时，这些元素被添加到一个跳跃列表 skiplist 中，将 score 映射到 Redis对象(对象根据 score 排序)。

注意下这句： “同时还能保证复杂度为 O(log(N)) 的插入和删除操作”，有没有一种婆婆介绍儿子的赶脚，言语间透露的自豪感，请记住它，下面我还会提到。散列表（hash），在之前的文章中已经分析过了，具体可以查看我的文章《【最完整系列】Redis-结构篇-字典》，所以不再说明了，接下来着重分析下 skiplist。

skiplist

跳跃列表在很早之前就已经被发明了，有兴趣的可以看下[它的历史](Skip Lists: A Probabilistic Alternative to Balanced Trees)。首先从名字上看它是一个 list，并且我们之前说过它还是有序的。一般来说，有序链表长这个样子：

最左侧节点为空的头节点，a 是我自己取得名字，方便做区分。

思考下，我们插入一个新的元素 “23” 需要怎么做，首先要遍历链表，比较节点元素直到找到一个大于 “23” 的元素，所以复杂度为 O(N)，删除某个元素也是一个道理，你们发现没，其实添加和删除后就是一个查询的过程。

为此，如果我们稍做优化，小小地改变一下链表的结构，为相邻的节点增加一个指针，指向下下个节点：

上图中可以发现形成了一个新链表 b（7 - 19 - 26），节点个数为原先链表，这时候我们重新去查询 “23” ：

1. 遍历链表 b，查询到第一个大于 23 的元素 “26”
2. 回到链表 a，发现 21 比 23 小，所以插入到 “21” 和 “26” 节点之间。

你们有没有发现，是不是很类似于二分查找，最终我们减少了查询的次数，我们甚至还可以再分一次创建一个新链表 c：

这时候的查询步骤变成了：

1. 遍历链表 c，只有一个元素 “19“，发现 23 大于 19，所以在 “19“ 后面找。
2. 回到链表 b，查询到第一个大于 23 的元素 “26” 。
3. 回到链表 a，发现 21 比 23 小，所以插入到 “21” 和 “26” 节点之间。

可以发现我们遍历的元素个数在逐渐减少，可想而知如果包含的元素个数足够大，查询的效率也会大幅提升。下面我举一个日常生活的例子来说明这种做法的优势：

我们在有序链表中查询一个元素的过程就好比在酒店里坐电梯。假如酒店有10层楼高，1-5层是普通套房，住的人多；6-10层是高级套房，住的人少。我住在9楼（嘿嘿嘿），那么我坐电梯下去 1 层的时候很可能在各个低层会停留（因低层住的人多），这对于高层客人肯定不爽。后面酒店改了，新造了电梯，分成了单双停靠，对我来说肯定是比之前更快了，但是1、3、5层还是会经常停靠，高层客人还是不满意。在之后酒店做绝了，直接造了一个1-5层不停留直达高层的电梯，这下舒服了，客户评价马上上去了。

如果你看懂了上面的例子，其实也发现了这个做法的一个劣势：需要造更多的 “电梯“，也就是需要创建更多的链表，黑话叫 “空间换时间”。

我们的 skiplist 正是在上面这种多层链表基础上设计而来的。实际上，按照上面生成链表的方式，上面每一层链表的节点个数，是下面一层的节点个数的一半，类似于一个二分查找，使得查找的时间复杂度可以降低到 O(log n) （还记得我之前让你记住的那个复杂度吗？）。但是，这种方法在插入数据的时候有很大的问题。新插入一个节点之后，就会破坏了上下相邻两层链表上节点个数 2:1 的比例关系。要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度又降低成了 O(n)，删除节点也一样。

shiplist 当然也考虑到这个问题，为此，它不要求上下相邻两层链表之间的节点个数有严格的比例关系，而是每个节点随机一个层数 level 。比如，一个节点随机出的层数是 3，那么就把它链入到第 1 层到第 3 层这三层链表中。为了表达清楚，下图展示了如何通过一步步的插入操作从而形成一个skiplist的过程：

为了减少一部分童鞋的疑惑，我先总结一下上图过程的 3 个特点：

• 第一层链表永远保存着最完整的元素数据。
• 位于第n层的元素，也肯定在 1~n-1层 之中。
• 新插入一个元素不会影响其它元素的层数。

前方高晕预警，以下内容涉及一些概率学和数学知识，摘自发明者的论文。可以直接跳过查看下一章节。

比较有意思的一点是元素的层数随机，这意味着 skiplist 是一个 “概率型” 的数据结构。实际上决定层数的随机计算对跳表的查找性能有着很大影响，这并不是一个普通的服从均匀分布的随机数，它的计算过程如下：

1. 指定一个节点最大的层数 MaxLevel，指定一个概率 p， 层数 level 默认为 1 。
2. 生成一个 0~1 的随机数 r，若 r < p，且 level < MaxLevel ，则执行 level++。
3. 重复第 2 步，直至生成的 r > p 为止，此时的 level 就是要插入的层数。

伪代码如下：

randomLevel()
    level = 1
    // random()返回一个[0...1)的随机数
    while random() < p and level < MaxLevel do
        level := level + 1
    return level

在 Redis 的 skiplist 实现中，p=1/4 ，MaxLevel=64。

源码结构

Redis 在 skiplist 的基础结构上做了一些变化来满足自己的需求，首先 show you source code：

#define ZSKIPLIST_MAXLEVEL 64 /* Should be enough for 2^64 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

ZSKIPLIST_MAXLEVEL 和 ZSKIPLIST_P 2个常量就是我们上一章节最后提到的部分。

为什么 zskiplistNode 的前向指针 backward 只有一个？

我发现基本上没有文章提到这一点，但是我觉得还是有必要解释下的。首先节点只有一个后向指针，也就意味着只有第一层的链表是一个双向链表，之前我们的例子里的链表都是单向的，为什么要把第一层变成双向呢？原因之一是第一层的数据最完整，原因之二是：试想一下，我们有一个元素的 score 为 8，其第一层的相邻节点 score 为 7 和 10，现在我们想要更新这个元素的 score 为 9，理论上我们要删除在插入，但其实这个元素的位置根本不需要改动，这种情况下可以先判断第一层相邻节点的大小，如果还是在区间内，就直接更新值，省去了删除插入的步骤。

level 中 span 的意义？

解释这个问题需要图片帮助，首先放一个 skiplist 的图：

箭头中上的数字就是 span 的值，span有很多好处，例如我们要找score为 3 的排名，直接取头指针中 L5 的span = 3 就行了，如果存在需要多层查询的情况就是累加的过程，反之还可以通过长度-累加值的操作计算逆序的排名。

总结下 redis 针对 skiplist 做出的 3 点调整：

• 数据不允许重复。
• 在比较时，不仅比较分数（相当于 skiplist 的 key），还比较数据本身。在 Redis 的 skiplist 实现中，数据本身的内容唯一标识这份数据，而不是由 key 来唯一标识。另外，当多个元素分数相同的时候，还需要根据数据内容来进字典排序。
• 有一个后向指针，所有第一层链表是一个双向链表。

Redis Zset 采用 skiplist 而不是平衡树的原因

扩展一下，看看作者是怎么说的：

They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.

也不是非常耗费内存，实际上取决于生成层数函数里的概率 p，取决得当的话其实和平衡树差不多。

A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.

因为有序集合经常会进行 ZRANGE 或 ZREVRANGE 这样的范围查找操作，跳表里面的双向链表可以十分方便地进行这类操作。

They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

实现简单，ZRANK 操作还能达到 O(logN) 的时间复杂度。