浅谈跳跃链表的基本原理

0.前言

通过本文将了解到以下内容：

• 跳跃链表的基本概念
• 跳跃链表的实现原理
• 跳跃链表的应用简介

注：以下简称跳跃链表为 跳表，由于跳表内容较多，分为2-3次写完。跳表的实现可以是单链表和双链表，本文主要基于单链表阐述。

1.跳跃链表的基本概念

• 初识跳表

跳跃列表是一种数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(log n)，优于普通队列的O(n)。 
跳跃列表由威廉·普发明，发明者对跳跃列表的评价：跳跃列表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。
跳跃列表的算法有同平衡树一样的渐进的预期时间边界，并且更简单、更快速和使用更少的空间。

这种数据结构是由William Pugh(音译为威廉·普)发明的，最早出现于他在1990年发表的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》，在谷歌上想进一步查一下这个大佬的履历，信息并不多，不过找到一篇作者关于跳表的论文，感兴趣强烈建议下载阅读：

https://epaperpress.com/sortsearchhttps://img.qb5200.com/download-x/download/skiplist.pdfWillliam 

看下这篇论文的摘要部分：

用我2009年考过的六级给翻译一下：

跳跃链表是一种可以用来代替平衡树的数据结构。跳表使用概率平衡而非严格平衡，因此基于跳表实现的算法在插入和删除操作上比平衡树更简单且明显更快。

从中我们获取到的信息是：

跳表在动态查找过程中使用了一种非严格的平衡机制来让插入和删除都更加便利和快捷，这种非严格平衡是基于概率的，而不是平衡树的严格平衡。

说到非严格平衡，首先想到的是红黑树RbTree，它同样采用非严格平衡来避免像AVL那样调整树的结构，这里就不展开讲红黑树了，不过后面一定讲一下红黑树，看来跳表也是一样的路子，但是是基于概率实现的。

• 动态查找的数据结构

所谓动态查找就是查找的过程中存在元素的删除和插入，这样就对实现查找的数据结构有一定的挑战，因为在每次删除和插入时都要调整数据结构，来保持秩序。可以作为查找数据结构的包括：

1. 线性结构：数组、链表
2. 非线性结构：平衡树

来分析一下各种数据结构在应对动态查找时的优劣：

• 数组结构

数组结构简单内存连续，可以实现二分查找等基于下标的操作，我一直认为数组的杀手锏就是下标，连续的内存也带来了问题。当进行插入和删除时就面临着整体的调整，就像在火车站排队买票，队头走一个整个队伍向前挪一步，有加塞的后面的又整体向后挪一步，这种整体移动操作在数组结构中性能损耗很大，并且在大数据量时对连续内存要求很高，当然这个在大内存机器上可能没有什么问题。

如图演示插入6和删除5时 数组元素的移动：

• 链表结构

链表结构也比较简单，但是不要求内存连续，不连续也就没有下标可以加速，但是链表在执行删除和插入时影响的只是插入删除点的前后元素，影响非常小。但是每次查找元素是需要进行遍历，就算我知道某个元素一定在大致的什么位置，也只能一步步走过去，看到这里要觉得有优化的空间，那你也蛮厉害的了，说不定早几年跳表就是你的发明了。

如图演示了删除元素5和插入元素49时的处理：

• 平衡树

平衡树也是处理动态查找问题的一把好手，树一般是基于链表实现的，只不过树的节点之间并不是链表简单的线性关系，会有兄弟姐妹父亲等节点，并且各个层级有数量的限制，可以看到树其实还是蛮复杂的。节点需要存储的信息很多，各个指针指来指去，复杂的结构增加了调整平衡性的难度，不同情况下的左旋右旋，所以出现了红黑树这种工程版本的AVL，但是在实际场景中可能并不需要这些兄弟姐妹父亲关系，有种杀鸡宰牛刀的意味了。

红黑树的节点结构定义：

 1 #define COLOR_RED  0x0
 2 #define COLOR_BLACK 0x1
 3 
 4 typedef struct RBNode{
 5    int key;
 6    unsigned char color;
 7    struct RBNode *left;
 8    struct RBNode *right;
 9    struct RBNode *parent;
10 }rb_node_t, *rb_tree_t;

另外红黑树调整属性过程中插入分为3种情况，删除分为4种情况，还是比较难以理解的。

• 三种结构对比

从上面的对比可以看到：数组并不能很好满足要求，链表在搜索过程又显得更笨拙，平衡树又有点复杂，到底该怎么办？

• 跳表的雏形

有条件要上，没有条件创造条件也要上。

没有条件，那么就创造条件。上面的三类结构都存在一些问题，所以要进行改造，可以看到数组和平衡树的某些特性决定了它们不容易被改造(数组内存连续性、平衡树节点多指针和层级关系)，相反链表最有潜力被改造优化。

• 不要一步步走 我要跳起来

在有序链表中插入和删除都比较简单，搜索时无法依靠下标只能遍历，但是明明知道要走两步可以到达目的地，偏偏只能一步步走，这就是痛点。

如图演示了O(n)遍历元素35和跳跃搜索元素35的过程：

貌似看到了曙光，那么如何实现跳跃呢？

没错！给链表加索引，让索引告诉我们下一步该跳到哪里。

看到这里又让我想起来那个经典的中间层理论，遇到问题，试着加个中间层试试，或许就完美解决了。

2.跳跃链表的实现原理

前面说了可以给普通链表加索引来解决，但是具体该怎么操作，以及其中有什么难点？一步步来分析。在工程中对跳表索引层数和结点是否作为索引结点，是其很重要的属性，后面就详细讲一下，现在先看一种简单场景，说明索引带来的便利性。

• 简单的索引

选择每隔1个结点为索引结点，并且索引为一层，虽然在工程中这种形式比较标准化，不过足以说明索引带来的加速。

可以将链表中的偶数序号节点增加一层指针，让其指向下一个偶数节点，如图所示：

搜索过程：加入要搜索值为55的节点，则先在上层进行搜索，由16跳到38，在38的下一跳将到达72，因此向下降一级继续类似的搜索，则找到55。

• 我要一步一步向上爬

基于偶数节点增加索引并且只有两层的情况下，最高层的节点数是n/2，整体来看搜索的复杂度降低为O(n/2)，并不要小看这个1/2的系数，看到这里会想 增加索引层数到k，那么复杂度将指数降低为O(n/2^k)。

索引层数不是无休止增加的，取决于该层索引的节点数量，如果该层的索引的节点数量等于2了，那么再往上加层也就没有意义了，

画个图看一下：

这个非常好理解，如果所在层索引结点只有1个，比如4层索引的结点16，只能顺着16向下遍历，无法向后跳到4层其他结点，

因此当所在层索引结点数量等于2，则到达最高索引层，这个约束在分析跳表复杂度时很重要。

• 索引层数和索引结点密度

跳表的复杂度和索引层数、索引结点的稀疏程度有很大关系。索引层数我们从上面也看到了，稀疏程度相当于索引结点的数量比例，如果跳表的索引结点数量很少，那么将接近退化为普通链表，这种情况在数据量是较大时非常明显，画图看下(蓝色部分表示有很多结点)：

图中可以看到虽然有索引层，但是索引结点数量相对全部数据比例较低，这种情况下搜索35相比无索引情况优势并不明显。

所以跳表的效率和索引层数和索引结点的密度有密切的关系，当然索引结点太多也就等于没有索引了。太少的索引结点和太多的索引结点都是一样的低效。

• 复杂度分析

从前面的分析可知，跳表的复杂度和索引层数m以及索引结点间隙d有直接关系，其中索引结点间隙理解为相隔几个结点出现索引结点，体现了对应层索引结点的稀疏程度，在无索引结点时只能遍历无法跳跃。

推导过程：

如何确定最高索引层数m呢？

如果一个链表有 n 个结点，如果每两个结点取出一个结点建立索引，那么第一级索引的结点数是 n/2，

第二级索引的结点数是n/4，以此类推第 m 级索引的结点数为 n/(2^m)，前面说过最高层结点数为2，因此存在关系：

算上最底层的原始链表，整个跳表的高度为h=logn(底数为2)，每一层需要遍历的结点数是d，那么整个过程的复杂度为:O(d*logn)。

d表明了层间结点的稀疏程度，也就是每隔2个结点选取索引结点、或者每隔3个结点选取索引结点，每个4个结点选取索引结点......最密集的情况下d=2，

借用知乎某大佬的文章的图片：

但是索引结点密集也意味着存储空间的增加，跳表相比较普通链表就是典型的用空间换时间的数据结构，这样就达到了AVL的复杂度O(logn)。

• 跳表的空间存储

以d=2的最密集情况为例，计算跳表的索引结点总数：

2+4+8+......n/8+n/4+n/2=n-2

由等比数列求和公式得d=2的跳表额外空间为O(n-2)。

• 跳表的插入和删除

工程中的跳表并不严格要求索引层结点数量遵循2:1的关系，因为这种要求将导致插入和删除数据时的调整，成本很大，因此跳表的每个插入的结点在插入时进行选择是否作为索引结点，如果作为索引结点则随机出层数，整个过程都是基于概率的，但是在大数据量时却能很好地解决索引层数和结点数的权衡。

• 跳表元素17插入：

链表的插入和删除是结合搜索过程完成的，贴一张William Pugh在论文中给出的在跳表中插入元素17的过程图(暂时忽略结点17是否作为索引结点以及索引层数，后面会详细说明)：

• 跳表元素1删除：

跳表元素的删除与普通链表相比增加了索引层的判断，如果结点是非索引结点则正常处理，如果结点是索引结点那边需要进行索引层结点的处理。

3.跳跃链表的应用简介

一般讨论查找问题时首先想到的是平衡树和哈希表，但是跳表这种数据结构也非常犀利，性能和实现复杂度都可以和红黑树媲美，甚至某些场景由于红黑树，从1990年被发明目前广泛应用于多种场景中，包括Redis、LevelDB等数据存储引擎中，后续将详细介绍。

4.小结

本文主要讲述了跳表的基本概念和简单原理、以及索引结点层级、时间和空间复杂度等相关部分，并没有涉及概率平衡以及工程实现部分，后续将陆续推出。

5.参考资料

• http://zhangtielei.com/posts/blog-redis-skiplist.html
• ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf
• https://zhuanlan.zhihu.com/p/68516038
• https://www.cnblogs.com/tong-yuan/p/skiplist.html