Redis 的底层数据结构（跳跃表）

我们都知道单链表有一个致命的弱点，查找任一节点都至少 O(n) 的时间复杂度，它需要遍历一遍整个链表，那么有没有办法提升链表的搜索效率？

跳跃表（）这种数据结构使用空间换时间的策略，通过给链表建立多层索引来加快搜索效率，我们先介绍跳跃表的基本理论，再来看看 redis 中的实现情况。

一、跳跃表（）

这是一条带哨兵的双端链表，大部分场景下的链表都是这种结构，它的好处是，无论是头插法还是尾插法，插入操作都是常量级别的时间复杂度，删除也是一样。但缺点就是，如果想要查询某个节点，则需要 O(n)。

那如果我们给链表加一层索引呢？当然前提是最底层的链表是有序的，不然索引也没有意义了。

让 HEAD 头指针指向最高索引，我抽出来一层索引，这样即便你查找节点 2222 三次比较。

第一次：与 2019 节点比较，发现大于 2019，往后继续

第二次：与 2100 节点比较，发现依然大于，往后继续

第三次：本层索引到头了，指向低层索引的下一个节点，继续比较，找到节点

而无索引的链表需要四次，效率看起来不是很明显，但是随着链表节点数量增多，索引层级增多，效率差距会很明显。图就不自己画了，取自极客时间王争老师的一张图。

你看，原本需要 62 次比较操作，通过五层索引，只需要 4 次比较，跳跃表的效率可见一瞥。

想要知道具体跳跃表与链表差距多少，我们接下来进行它们各个操作的时间复杂度分析对比。

1、插入节点操作

双端链表（以下我们简称链表）的原本插入操作是 O(1) 的时间复杂度，但是这里我们讨论的是有序链表，所以插入一个节点至少还要找到它该插入的位置，然后才能执行插入操作，所以链表的插入效率是 O(n)。

跳跃表（以下我们简称跳表）也依然是需要两个步骤才能完成插入操作，先找到该插入的位置，再进行插入操作。我们设定一个具有 N 个节点的链表，它建有 K 层索引并假设每两个节点间隔就向上分裂一层索引。

k 层两个节点，k-1 层 4 个节点，k-2 层 8 个节点 … 第一层 n 个节点，

1：n
2：1/2 * n
3：1/2^2 * n
.....
.....
k：1/2^(k-1) * n

1/2^(k-1) * n 表示第 k 层节点数，1/2^(k-1) * n=2 可以得到，k 等于 logn，也就是说 ，N 个节点构建跳表将需要 logn 层索引，包括自身那层链表层。

而当我们要搜索某个节点时，需要从最高层索引开始，按照我们的构建方式，某个节点必然位于两个索引节点之间，所以每一层都最多访问三个节点。这一点你可能需要理解理解，因为每一层索引的搜索都是基于上一层索引的，从上一层索引下来，要么是大于（小于）当前的索引节点，但不会大于（小于）其往后两个位置的节点，也就是当前索引节点的上一层后一索引节点，所以它最多访问三个节点。

有了这一结论，我们向跳表中插入一个元素的时间复杂度就为：O(logn)。这个时间复杂度等于二分查找的时间复杂度，所有有时我们又称跳表是实现了二分查找的链表。

很明显，插入操作，跳表完胜链表。

2、修改删除查询

这三个节点操作其实没什么可比性，修改删除操作，链表等效于跳表。而查询，我们上面也说了，链表至少 O(n)，跳表在 O(logn)。

除此之外，我们都知道红黑树在每次插入节点后会自旋来进行树的平衡，那么跳表其实也会有这么一个问题，就是不断的插入，会导致底层链表节点疯狂增长，而索引层依然那么多，极端情况所有节点都新增到最后一级索引节点的右边，进而使跳表退化成链表。

简单一句话来说，就是大量的节点插入之后，而不更新索引的话，跳表将无法一如既往的保证效率。解决办法也很简单，就是每一次节点的插入，触发索引节点的更新，我们具体来看一下更新策略。

一般跳表会使用一个随机函数，这个随机函数会在跳表新增了一个节点后，根据跳表的目前结构生成一个随机数，这个数值当然要小于最大的索引层值，假定这个值等于 m，那么跳表会生成从 1 到 m 层的索引。所以这个随机函数的选择或者说实现就显得很重要了，关于它我们这里不做讨论，大家可以看看各种跳表的实现中是如何实现这个随机函数的，典型的就是 Java 中 p 内部实现的 结构，当然还有我们马上要介绍的 redis 中的实现。

以上就是跳表这种数据结构的基本理论内容，接下来我们看 redis 中的实现情况。

二、Redis 中的跳跃表

说在前面的是，redis 自己实现了跳表，但目的是为它的有序集合等高层抽象数据结构提供服务，所以等下我们分析源代码的时候其中必然会涉及到一些看似无用的结构和代码逻辑，但那些也是非常重要的，我们也会提及有序集合相关的内容，但不会拆分细致，重点还是看跳表的实现。

跳表的数据结构定义如下：

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

跳表中的每个节点用数据结构 表示，head 和 tail 分别指向最底层链表的头尾节点。 表示当前跳表最底层链表有多少个节点，level 记录当前跳表最高索引层数。

结构如下：

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

我这里摘取的 redis 源码是 4.0 版本的，以前版本 ele 属性是一个 类型，现在是一个字符串类型，也即表示跳表现在只用于存储字符串数据。

score 记录当前节点的一个分值，最底层的链表就是按照分值大小有序的串联的，并且我们查询一个节点，一般也会传入该节点的 score 值，毕竟数值类型比较起来方便。

指针指向前一个节点，为什么是倒着往前，我们待会会说。

level 是比较关键的一个点，这里面是一个 level 数组，而每个元素又都是一个 类型的结构， 类型包括一个 前向指针，一个 span 跨度值，具体是什么意思，我们一点点说。

跳表理论上在最底层是一条双端链表，然后基于此建立了多层索引节点以实现的，但在实际的代码实现上，这种结构是不好表述的，所以你要打破既有的惯性思维，然后才能好理解 redis 中的实现。实际上正如我们上述介绍的 结构一样，每个节点除了存储节点自身的数据外，还通过 level 数组保存了该节点在整个跳表各个索引层的节点引用，具体结构就是这样的：

而整张跳表基本就是这样的结构：