跳跃表 Redis 的底层数据结构( 二 ) _节点

简单一句话来说，就是大量的节点插入之后，而不更新索引的话，跳表将无法一如既往的保证效率。解决办法也很简单，就是每一次节点的插入，触发索引节点的更新，我们具体来看一下更新策略。
一般跳表会使用一个随机函数，这个随机函数会在跳表新增了一个节点后，根据跳表的目前结构生成一个随机数，这个数值当然要小于最大的索引层值，假定这个值等于 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 数组保存了该节点在整个跳表各个索引层的节点引用，具体结构就是这样的：
而整张跳表基本就是这样的结构：