这是Bella酱的第88期分享
作者
范瑞
跳表是一种神奇的数据结构，因为几乎所有版本的大学本科教材上都没有跳表这种数据结构，而且神书《算法导论》、《算法第四版》这两本书中也没有介绍跳表。但是跳表插入、删除、查找元素的时间复杂度跟红黑树都是一样量级的，时间复杂度都是O(logn)，而且跳表有一个特性是红黑树无法匹敌的（具体什么特性后面会提到）。所以在工业中，跳表也会经常被用到。废话不多说了，开始今天的跳表学习。
通过本文，你能get到以下知识：
什么是跳表？
跳表的查找、插入、删除元素的流程
跳表查找、插入、删除元素的时间复杂度
跳表插入元素时，如何动态维护索引？
为什么Redis选择使用跳表而不是红黑树来实现有序集合？
工业上其他使用跳表的场景
友情提示：下文在跳表插入数据时，会讲述如何动态维护索引，实现比较简单，逻辑比较绕，不要放弃，加油！！！如果一遍看不懂没关系，可以选择暂时性的跳过，毕竟这块偏向于源码。但是读者必须知道跳表的查找、插入、删除的时间复杂度都是O(logn)，而且可以按照范围区间查找元素，当工作中遇到某些场景时，需要想到可以使用跳表解决问题即可。毕竟平时的工作都是直接使用封装好的跳表，例如：java.util.concurrent下的ConcurrentSkipListMap()。
理解跳表，从单链表开始说起下图是一个简单的有序单链表，单链表的特性就是每个元素存放下一个元素的引用。即：通过第一个元素可以找到第二个元素，通过第二个元素可以找到第三个元素，依次类推，直到找到最后一个元素。
现在我们有个场景，想快速找到上图链表中的10这个元素，只能从头开始遍历链表，直到找到我们需要找的元素。查找路径：1、3、4、5、7、8、9、10。这样的查找效率很低，平均时间复杂度很高O(n)。那有没有办法提高链表的查找速度呢？如下图所示，我们从链表中每两个元素抽出来，加一级索引，一级索引指向了原始链表，即：通过一级索引7的down指针可以找到原始链表的7。那现在怎么查找10这个元素呢？
先在索引找1、4、7、9，遍历到一级索引的9时，发现9的后继节点是13，比10大，于是不往后找了，而是通过9找到原始链表的9，然后再往后遍历找到了我们要找的10，遍历结束。有没有发现，加了一级索引后，查找路径：1、4、7、9、10，查找节点需要遍历的元素相对少了，我们不需要对10之前的所有数据都遍历，查找的效率提升了。
那如果加二级索引呢？如下图所示，查找路径：1、7、9、10。是不是找10的效率更高了？这就是跳表的思想，用“空间换时间”，通过给链表建立索引，提高了查找的效率。
可能同学们会想，从上面案例来看，提升的效率并不明显，本来需要遍历8个元素，优化了半天，还需要遍历4个元素，其实是因为我们的数据量太少了，当数据量足够大时，效率提升会很大。如下图所示，假如有序单链表现在有1万个元素，分别是0~。现在我们建了很多级索引，最高级的索引，就两个元素0、，次高级索引四个元素0、、、，依次类推，当我们查找这个元素时，查找路径为0、、...，通过最高级索引直接跳过了个元素，次高层索引直接跳过了个元素，从而使得链表能够实现二分查找。由此可以看出，当元素数量较多时，索引提高的效率比较大，近似于二分查找。
到这里大家应该已经明白了什么是跳表。跳表是可以实现二分查找的有序链表。
查找的时间复杂度既然跳表可以提升链表查找元素的效率，那查找一个元素的时间复杂度到底是多少呢？查找元素的过程是从最高级索引开始，一层一层遍历最后下沉到原始链表。所以，时间复杂度=索引的高度*每层索引遍历元素的个数。
先来求跳表的索引高度。如下图所示，假设每两个结点会抽出一个结点作为上一级索引的结点，原始的链表有n个元素，则一级索引有n/2个元素、二级索引有n/4个元素、k级索引就有n/2k个元素。最高级索引一般有2个元素，即：最高级索引h满足2=n/2h，即h=log2n-1，最高级索引h为索引层的高度加上原始数据一层，跳表的总高度h=log2n。
我们看上图中加粗的箭头，表示查找元素x的路径，那查找过程中每一层索引最多遍历几个元素呢？
图中所示，现在到达第k级索引，我们发现要查找的元素x比y大比z小，所以，我们需要从y处下降到k-1级索引继续查找，k-1级索引中比y大比z小的只有一个w，所以在k-1级索引中，我们遍历的元素最多就是y、w、z，发现x比w大比z小之后，再下降到k-2级索引。所以，k-2级索引最多遍历的元素为w、u、z。其实每级索引都是类似的道理，每级索引中都是两个结点抽出一个结点作为上一级索引的结点。现在我们得出结论：当每级索引都是两个结点抽出一个结点作为上一级索引的结点时，每一层最多遍历3个结点。
跳表的索引高度h=log2n，且每层索引最多遍历3个元素。所以跳表中查找一个元素的时间复杂度为O(3*logn)，省略常数即：O(logn)。
空间复杂度跳表通过建立索引，来提高查找元素的效率，就是典型的“空间换时间”的思想，所以在空间上做了一些牺牲，那空间复杂度到底是多少呢？
假如原始链表包含n个元素，则一级索引元素个数为n/2、二级索引元素个数为n/4、三级索引元素个数为n/8以此类推。所以，索引节点的总和是：n/2+n/4+n/8+…+8+4+2=n-2，空间复杂度是O(n)。
如下图所示：如果每三个结点抽一个结点做为索引，索引总和数就是n/3+n/9+n/27+…+9+3+1=n/2，减少了一半。所以我们可以通过较少索引数来减少空间复杂度，但是相应的肯定会造成查找效率有一定下降，我们可以根据我们的应用场景来控制这个阈值，看我们更注重时间还是空间。
But，索引结点往往只需要存储key和几个指针，并不需要存储完整的对象，所以当对象比索引结点大很多时，索引占用的额外空间就可以忽略了。举个例子：我们现在需要用跳表来给所有学生建索引，学生有很多属性：学号、姓名、性别、身份证号、年龄、家庭住址、身高、体重等。学生的各种属性只需要在原始链表中存储一份即可，我们只需要用学生的学号（int类型的数据）建立索引，所以索引相对原始数据而言，占用的空间可以忽略。
插入数据插入数据看起来也很简单，跳表的原始链表需要保持有序，所以我们会向查找元素一样，找到元素应该插入的位置。如下图所示，要插入数据6，整个过程类似于查找6，整个的查找路径为1、1、1、4、4、5。查找到第底层原始链表的元素5时，发现5小于6但是后继节点7大于6，所以应该把6插入到5之后7之前。整个时间复杂度为查找元素的时间复杂度O(logn)。
如下图所示，假如一直往原始列表中添加数据，但是不更新索引，就可能出现两个索引节点之间数据非常多的情况，极端情况，跳表退化为单链表，从而使得查找效率从O(logn)退化为O(n)。那这种问题该怎么解决呢？我们需要在插入数据的时候，索引节点也需要相应的增加、或者重建索引，来避免查找效率的退化。那我们该如何去维护这个索引呢？
比较容易理解的做法就是完全重建索引，我们每次插入数据后，都把这个跳表的索引删掉全部重建，重建索引的时间复杂度是多少呢？因为索引的空间复杂度是O(n)，即：索引节点的个数是O(n)级别，每次完全重新建一个O(n)级别的索引，时间复杂度也是O(n)。造成的后果是：为了维护索引，导致每次插入数据的时间复杂度变成了O(n)。
那有没有其他效率比较高的方式来维护索引呢？假如跳表每一层的晋升概率是1/2，最理想的索引就是在原始链表中每隔一个元素抽取一个元素做为一级索引。换种说法，我们在原始链表中随机的选n/2个元素做为一级索引是不是也能通过索引提高查找的效率呢？当然可以了，因为一般随机选的元素相对来说都是比较均匀的。如下图所示，随机选择了n/2个元素做为一级索引，虽然不是每隔一个元素抽取一个，但是对于查找效率来讲，影响不大，比如我们想找元素16，仍然可以通过一级索引，使得遍历路径较少了将近一半。如果抽取的一级索引的元素恰好是前一半的元素1、3、4、5、7、8，那么查找效率确实没有提升，但是这样的概率太小了。我们可以认为：当原始链表中元素数量足够大，且抽取足够随机的话，我们得到的索引是均匀的。我们要清楚设计良好的数据结构都是为了应对大数据量的场景，如果原始链表只有5个元素，那么依次遍历5个元素也没有关系，因为数据量太少了。所以，我们可以维护一个这样的索引：随机选n/2个元素做为一级索引、随机选n/4个元素做为二级索引、随机选n/8个元素做为三级索引，依次类推，一直到最顶层索引。这里每层索引的元素个数已经确定，且每层索引元素选取的足够随机，所以可以通过索引来提升跳表的查找效率。
那代码该如何实现，才能使跳表满足上述这个样子呢？可以在每次新插入元素的时候，尽量让该元素有1/2的几率建立一级索引、1/4的几率建立二级索引、1/8的几率建立三级索引，以此类推，就能满足我们上面的条件。现在我们就需要一个概率算法帮我们把控这个1/2、1/4、1/8...，当每次有数据要插入时，先通过概率算法告诉我们这个元素需要插入到几级索引中，然后开始维护索引并把数据插入到原始链表中。下面开始讲解这个概率算法代码如何实现。
我们可以实现一个randomLevel()方法，该方法会随机生成1~MAXLEVEL之间的数（MAXLEVEL表示索引的最高层数），且该方法有1/2的概率返回1、1/4的概率返回2、1/8的概率返回3，以此类推。
randomLevel()方法返回1表示当前插入的该元素不需要建索引，只需要存储数据到原始链表即可（概率1/2）
randomLevel()方法返回2表示当前插入的该元素需要建一级索引（概率1/4）
randomLevel()方法返回3表示当前插入的该元素需要建二级索引（概率1/8）
randomLevel()方法返回4表示当前插入的该元素需要建三级索引（概率1/16）
。。。以此类推
所以，通过randomLevel()方法，我们可以控制整个跳表各级索引中元素的个数。重点来了：randomLevel()方法返回2的时候会建立一级索引，我们想要一级索引中元素个数占原始数据的1/2，但是randomLevel()方法返回2的概率为1/4，那是不是有矛盾呢？明明说好的1/2，结果一级索引元素个数怎么变成了原始链表的1/4？我们先看下图，应该就明白了。
假设我们在插入元素6的时候，randomLevel()方法返回1，则我们不会为6建立索引。插入7的时候，randomLevel()方法返回3，所以我们需要为元素7建立二级索引。这里我们发现了一个特点：当建立二级索引的时候，同时也会建立一级索引；当建立三级索引时，同时也会建立一级、二级索引。所以，一级索引中元素的个数等于[原始链表元素个数]*[randomLevel()方法返回值1的概率]。因为randomLevel()方法返回值1就会建索引，凡是建索引，无论几级索引必然有一级索引，所以一级索引中元素个数占原始数据个数的比率为randomLevel()方法返回值1的概率。那randomLevel()方法返回值1的概率是多少呢？因为randomLevel()方法随机生成1~MAX_LEVEL的数字，且randomLevel()方法返回值1的概率为1/2，则randomLevel()方法返回值1的概率为1-1/2=1/2。即通过上述流程实现了一级索引中元素个数占原始数据个数的1/2。
同理，当randomLevel()方法返回值2时，会建立二级或二级以上索引，都会在二级索引中增加元素，因此二级索引中元素个数占原始数据的比率为randomLevel()方法返回值2的概率。randomLevel()方法返回值2的概率为1减去randomLevel()=1或=2的概率，即1-1/2-1/4=1/4。OK，达到了我们设计的目标：二级索引中元素个数占原始数据的1/4。
以此类推，可以得出，遵守以下两个条件：
randomLevel()方法，随机生成1~MAXLEVEL之间的数（MAXLEVEL表示索引的最高层数），且有1/2的概率返回1、1/4的概率返回2、1/8的概率返回3...
randomLevel()方法返回1不建索引、返回2建一级索引、返回3建二级索引、返回4建三级索引...
就可以满足我们想要的结果，即：一级索引中元素个数应该占原始数据的1/2，二级索引中元素个数占原始数据的1/4，三级索引中元素个数占原始数据的1/8，依次类推，一直到最顶层索引。
但是问题又来了，怎么设计这么一个randomLevel()方法呢？直接撸代码：
//该randomLevel方法会随机生成1~MAX_LEVEL之间的数，且：
//1/2的概率返回1
//1/4的概率返回2
//1/8的概率返回3以此类推
privateintrandomLevel(){
intlevel=1;
//当levelMAX_LEVEL，且随机数小于设定的晋升概率时，level+1
while(Math.random()SKIPLIST_PlevelMAX_LEVEL)
level+=1;
returnlevel;
}
上述代码可以实现我们的功能，而且，我们的案例中晋升概率SKIPLISTP设置的1/2，即：每两个结点抽出一个结点作为上一级索引的结点。如果我们想节省空间利用率，可以适当的降低代码中的SKIPLISTP，从而减少索引元素个数，Redis的zset中SKIPLISTP设定的0.25。下图所示，是Redistzset.c中zslRandomLevel函数的实现：
Redis源码中(random()0xFFFF)(ZSKIPLIST_P*0xFFFF)在功能上等价于我代码中的Math.random()SKIPLIST_P，只不过Redis作者antirez使用位运算来提高浮点数比较的效率。
整体思路大家应该明白了，那插入数据时维护索引的时间复杂度是多少呢？元素插入到单链表的时间复杂度为O(1)，我们索引的高度最多为logn，当插入一个元素x时，最坏的情况就是元素x需要插入到每层索引中，所以插入数据到各层索引中，最坏时间复杂度是O(logn)。
过程大概理解了，再通过一个例子描述一下跳表插入数据的全流程。现在我们要插入数据6到跳表中，首先randomLevel()返回3，表示需要建二级索引，即：一级索引和二级索引需要增加元素6。该跳表目前最高三级索引，首先找到三级索引的1，发现6比1大比13小，所以，从1下沉到二级索引。
下沉到二级索引后，发现6比1大比7小，此时需要在二级索引中1和7之间加一个元素6，并从元素1继续下沉到一级索引。
下沉到一级索引后，发现6比1大比4大，所以往后查找，发现6比4大比7小，此时需要在一级索引中4和7之间加一个元素6，并把二级索引的6指向一级索引的6，最后，从元素4继续下沉到原始链表。
下沉到原始链表后，就比较简单了，发现4、5比6小，7比6大，所以将6插入到5和7之间即可，整个插入过程结束。
整个插入过程的路径与查找元素路径类似，每层索引中插入元素的时间复杂度O(1)，所以整个插入的时间复杂度是O(logn)。
删除数据跳表删除数据时，要把索引中对应节点也要删掉。如下图所示，如果要删除元素9，需要把原始链表中的9和第一级索引的9都删除掉。
跳表中，删除元素的时间复杂度是多少呢？
删除元素的过程跟查找元素的过程类似，只不过在查找的路径上如果发现了要删除的元素x，则执行删除操作。跳表中，每一层索引其实都是一个有序的单链表，单链表删除元素的时间复杂度为O(1)，索引层数为logn表示最多需要删除logn个元素，所以删除元素的总时间包含查找元素的时间加删除logn个元素的时间为O(logn)+O(logn)=2O(logn)，忽略常数部分，删除元素的时间复杂度为O(logn)。
总结跳表是可以实现二分查找的有序链表；
每个元素插入时随机生成它的level；
最底层包含所有的元素；
如果一个元素出现在level(x)，那么它肯定出现在x以下的level中；
每个索引节点包含两个指针，一个向下，一个向右；（笔记目前看过的各种跳表源码实现包括Redis的zset都没有向下的指针，那怎么从二级索引跳到一级索引呢？留个悬念，看源码吧，文末有跳表实现源码）
跳表查询、插入、删除的时间复杂度为O(logn)，与平衡二叉树接近；
为什么Redis选择使用跳表而不是红黑树来实现有序集合？Redis中的有序集合(zset)支持的操作：
插入一个元素
删除一个元素
查找一个元素
有序输出所有元素
按照范围区间查找元素（比如查找值在[,]之间的数据）
其中，前四个操作红黑树也可以完成，且时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。按照区间查找数据时，跳表可以做到O(logn)的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了，非常高效。
工业上其他使用跳表的场景在博客上从来没有见过有同学讲述HBaseMemStore的数据结构，其实HBaseMemStore内部存储数据就使用的跳表。为什么呢？HBase属于LSMTree结构的数据库，LSMTree结构的数据库有个特点，实时写入的数据先写入到内存，内存达到阈值往磁盘flush的时候，会生成类似于StoreFile的有序文件，而跳表恰好就是天然有序的，所以在flush的时候效率很高，而且跳表查找、插入、删除性能都很高，这应该是HBaseMemStore内部存储数据使用跳表的原因之一。HBase使用的是java.util.concurrent下的ConcurrentSkipListMap()。
Google开源的key/value存储引擎LevelDB以及Facebook基于LevelDB优化的RocksDB都是LSMTree结构的数据库，他们内部的MemTable都是使用了跳表这种数据结构。
后期笔者还会输出一篇深入剖析LSMTree的博客，到时候再结合场景分析为什么使用跳表。
参考：
Rediszset源码(