Skip List（跳表）
跳表(Skip List)，也称为跳跃表，是一种不怎么熟悉，但是听起来很腻害的数据结构，Redis有序集合的实现好像跟这个家伙也有关系呢，今天我们就来一起学习下吧。
先举个例子，看看在实际场景中，哪些地方用得到它。
一、需求：道具拍卖系统
1、几个要点
1）道具
用来查阅和出售游戏中的道具
2）支持四种排序方式
按价格、等级、剩余时间、出售者ID排序
3）时间性能要求
要尽可能快地展现给玩家
查询：支持输入道具名称的精确查询和不输入名称的全量查询
4）数据量
拍卖行的商品总数量有几十万件，对应数据库商品表的几十万条记录
- 按照商品名称精确查询，可以直接从数据库查出来，最多也就上百条记录
- 不输入名称的全量查询
实现：提前在内存中存储有序的全量商品集合，每一种排序方式都保存成独立的集合，每次请求的时候按照请求的排序种类，返回对应的集合
比如按照价格字段排序的集合
比如按照等级字段排序的集合
需要注意的是，当时还没有Redis这样的内存数据库，所以只能自己实现一套合适的数据结构来存储。
二、选择什么样的数据结构？
比如插入商品等级
1. 考虑用数组用来实现
数组：查找时间复杂度logN（二分查找），插入时间复杂度为0(N)
总体时间复杂度为O(N)
2. 考虑用链表来实现
链表：查找时间复杂度O(N)（无法使用二分查找，只能和原链表中的节点逐一比较大小来确定位置），插入时间复杂度为O(1)
总体时间复杂度为O(N)
总结：这对于拥有几十万商品的集合来说，这两种方法显然都太慢了。
三、使用跳表来实现
1. 什么是跳表？
跳跃表(skiplist)是一种基于有序链表的扩展，简称跳表。
思考：怎样能更快查找到一个有序链表的某一节点呢？
可以利用类似索引的思想，提取出链表中的部分关键节点。
提取的极限：同一层只有两个节点的时候，因为一个节点没有比较多意义。这样的多层链表结构，就是所谓的【跳跃表】。
2. 理解跳表，从单链表开始说起
1）单链表
单链表的特性就是每个元素存放下一个元素的引用
2）场景
这里有一个原始链表：1->3->4->5->7->8->10->13->16->17->18
现在有这样一个场景：需要从上面链表中快速找到10这个元素
分析：我们知道，在线性表的顺序存储结构中，我们要计算任意一个元素的存储位置是很容易的。但是在单链表中，由于第 i 个元素到底在哪？没办法一开始就知道，必须得从头开始找，直到找到我们需要找点元素。
因此，这里查找路径为：1->3->4->5->7->8->10
3）那么，如何提高链表的查找速度呢？
我们从链表中每两个元素抽出来，加一级索引，一级索引指向了原始链表，如下图：
第一级索引： 1->4->7->9->13->17
查找顺序：先在索引中遍历查找，1->4->7->9,发现 9 的后继节点是 13，比 10 大，于是不往后找了，而是通过 9 找到原始链表的 9，然后再往后遍历找到了我们要找的 10，遍历结束。
优点：加了一级索引之后，查找路径为：1->4->7->9->10，查找节点需要遍历的元素相对少了，不需要对10之前对所有数据都遍历，查找的效率提升了。
那如果加二级索引呢？
第二级索引：1->7->13
查找路径：1->7->9->10 这样一来查找效率更高了。
分析：有了二级索引之后，新的节点可以看和二级索引比较，确定大体范围，然后再和一级索引比较，最后在回到原链表，找到并插入对应位置。当节点很多的时候，比较次数会减少到原来的四分之一！近似于二分查找。
这就是跳表的思想，用空间换时间，通过给链表建立索引，提高了查找的效率。
3. 如何应对大量新节点插入到原链表的场景？
1）可能会产生的问题
当大量的新节点通过逐层比较，最终插入到原链表之后，但是不更新索引，就可能出现两个索引节点之间数据非常多的情况，极端情况就是跳表退化为单链表，从而使得查找效率从O(logn)退化为O(n)。
2）如何解决？
我们需要在插入数据的时候，索引节点也需要相应的增加、或者重建索引，来避免查找效率的退化。这时候需要从新节点当中选取一部分提到上一层。可是究竟应该提拔谁，忽略谁呢？该如何去维护这个索引呢？
比较容易理解的做法就是完全重建索引，我们每次插入数据后，都把这个跳表的索引删掉全部重建，重建索引的时间复杂度是多少呢？因为索引的空间复杂度是 O(n)，即：索引节点的个数是 O(n) 级别，每次完全重新建一个 O(n) 级别的索引，时间复杂度也是 O(n) 。造成的后果是：为了维护索引，导致每次插入数据的时间复杂度变成了 O(n)。所以这种办法实际中不可取。
3）解决办法：抛硬币
跳跃表的设计者采用了一种有趣的办法：【抛硬币】。也就是随机决定新节点是否提拔，每向上提拔一层的几率是50%。
采用抛硬币这个办法的理由：
1）因为跳跃表删除和添加的节点是不可预测的，很难用一种有效的算法来保证跳表的索引分布始终均匀。
2）随机抛硬币的方法虽然不能保证索引绝对均匀分布，却可以让大体趋于均匀。
四、跳表的进一步认识
从上面的描述可以看出，跳表是可以实现二分查找的有序链表。下面来进一步认识跳表。
1. 查找的时间复杂度
查找元素的过程是从*索引开始，一层一层遍历最后下沉到原始链表。所以，时间复杂度 = 索引的高度 * 每层索引遍历元素的个数。
推算：
原始链表有n个元素，则一级索引有n/2个元素，二级索引有n/4个元素...k级索引就有n/(2的k次方)个元素。
*索引一般有2个元素，即：*索引h满足2=n/(2的h次方)，即h=log2n-1
*索引h为索引层的高度，加上原始数据一层，跳表的总高度为log2n。
跳表的索引高度 h = log2n，且每层索引最多遍历 3 个元素。所以跳表中查找一个元素的时间复杂度为 O(3*logn)，省略常数即：O(logn)。
2. 空间复杂度
跳表通过建立索引，来提高查找元素的效率，就是典型的“空间换时间”的思想，所以在空间上做了一些牺牲，那空间复杂度到底是多少呢？ O(n)
3. 跳跃表的添加操作
1）新节点和各层索引节点逐一比较，确定原链表的插入位置。O（logN）
2）把索引插入到原链表。O（1）
3）利用抛硬币的随机方式，决定新节点是否提升为上一级索引。结果为“正”则提升并继续抛硬币，结果为“负”则停止。O（logN）
总体上，跳跃表插入操作的时间复杂度是O（logN），而这种数据结构所占空间是2N，既空间复杂度是 O（N）。
4. 跳跃表的删除操作
删除操作比较简单，只要在索引层找到要删除的节点，然后顺藤摸瓜，删除每一层的相同节点即可。
如果某一层索引在删除后只剩下一个节点，那么整个一层就可以干掉了。还用原来的例子，如果要删除的节点值是5。
总结：跳跃表删除节点的操作
1）自上而下，查找第一次出现节点的索引，并逐层找到每一层对应的节点。O（logN）
2）删除每一层查找到的节点，如果该层只剩下1个节点，删除整个一层（原链表除外）。O（logN）
总体上，跳跃表删除操作的时间复杂度是O（logN）
五、跳跃表和二叉查找树的区别是什么？
跳跃表的优点是维持结构平衡的成本比较低，完全依靠随机。而二叉查找树在多次插入删除后，需要Rebalance来重新调整结构平衡。所以说没有绝对优劣的数据结构，关键还要看应用场景。
小灰和大黄并不知道，他们的这一解决方案和若干年后Redis当中的Sorted-set不谋而合。而Sorted-set这种有序集合，正是对于跳跃表的改进和应用。
参考链接：
https://zhuanlan.zhihu.com/p/53975333
https://www.jianshu.com/p/9d8296562806