Redis源码学习之跳表

• 跳跃链表

跳跃链表简称为跳表（SkipList），它维护了一个多层级的链表，且第i+1层链表中的节点是第i层链表中的节点的子集。跳表作为一种平衡数据结构，经常和平衡树进行比较，在大多数场景下，跳表都可以达到平衡树的效率（查询节点支持平均O（lgN），最坏O（N）的复杂度），但实现和维护起来却比平衡树简单很多。（跳跃列表由 William Pugh 发明。他在 Communications of the ACM发表了《Skip lists: a probabilistic alternative to balanced trees》，在其中详细描述了他的工作）

640?wx_fmt=png

• 跳表在Redis中的使用

1. 有序集合对象（SortedSet）底层实现之一
2. 集群节点内部数据结构

• 跳表在Redis中的实现

1. 数据结构 跳表节点，包含了节点中存储的数据obj和对应的分值score，以及每个节点的层数结构，每层都包含着前进指针与跨度；除此之外，每个节点还包含一个后退指针，假设跳表只有一层，那么整个跳表将退化为双端链表。

640?wx_fmt=png

这里需要明确一下跨度的定义：从前驱节点到自身经历的节点数（包含前驱节点在内），如下图连接线上数字即为箭头指向节点的在对应层的跨度。

640?wx_fmt=png

跳表，持有跳表的结构包括指向跳表表头和表尾的指针，以及整个跳表的长度（即第一层的节点数，但不包含头结点），还有整个跳表最高层的层数。这里需要指出的是，表头节点是一个包含了所有层的虚拟节点（不包含任何数据），每一层中表头节点的forward都指向该层的第一个真实节点。

640?wx_fmt=png

最终，Redis中的一个长度为2，层高为2的跳表如下图所示

640?wx_fmt=png

1. 插入节点 当进行插入操作的时候，程序会维护两个数组，rank数组保存每层中插入节点前驱前驱节点的排行值，update数组保存每层插入节点的前驱节点，以下图为例：

640?wx_fmt=png

在一个长度为4，高度为5的跳表中插入score为20，值为字符串c的节点，首先由上至下遍历每层查找插入位置，同时维护每层的rank值和update节点，遍历完之后，rank和update数组如图中所示，我们将其中的4层（即i=3）拿出来分析一下。在插入节点之前，update[3]指向头结点,rank[3]=0，rank[0]=2，第三层左边节点到右边节点的跨度是4，那么从图中可以看出，新节点的跨度=左边节点（即插入节点的前驱）跨度-（rank[0]-rank[3]），这里的rank[0]-rank[3]可以进一步模型化为rank[0]-rank[i]，从上文中可以看出来，实际上rank[0]-rank[i]就表示，插入节点与插入节点前驱节点之间的节点数（不包含前驱节点自身），所以在原跨度中将其减掉，就是插入节点的跨度了。

640?wx_fmt=png

当节点插入后，如下图所示。可以通过图中公式计算出插入节点的前驱节点的跨度。

640?wx_fmt=png

整个例子走下来之后，我们可以通过流程图来回顾一下：

640?wx_fmt=png

代码如下：

640?wx_fmt=png

1. 删除节点（内部函数） 删除节点被多个public方法调用，用于删除某个分值为score，对象为obj的节点。需要外部方法遍历节点各层后，维护update数组作为输入，需要注意这里跨度值的维护，代码实现如下：

640?wx_fmt=png

1. 删除节点（公开方法） 此方法对外公开，首先从上至下遍历各层维护好update数组，再调用内部删除节点方法，代码实现如下：

640?wx_fmt=png

1. 获取指定节点在跳表中的排行值 有了插入代码中排行值的讲解，相信你自己也可以实现这部分代码了，只需要在遍历的同时将跨度进行累加即可，代码实现如下：

640?wx_fmt=png

• 综述 上文中笔者只列出了自认为比较核心的方法，通过这几个方法也基本可以了解Redis中跳表的实现思想，总的来说与常规实现方法差别不大，只是对于排行值的需求定义并维护了每个节点的跨度。另外，值得一提的是，Redis中跳表的最高层数为32，层数越高出现的概率越低。在后面对于有序集合对象的介绍中，还会再次涉及到跳表。