参考文档：什么是跳跃表？
1. 什么是跳跃表
跳跃表(Skip List)是一种基于有序链表的扩展，简称跳表。
其实就是使用关键节点作为索引的一种结构。
怎样能更快查找到一个有序链表的某一节点呢？
可以利用类似索引的思想，提取出链表中的部分关键节点
比如：
- 给定一个长度是 7 的有序链表，节点值依次是 1->2->3->5->6->7->8, 那么我们可以取出所有值为奇数的节点作为关键点。
- 此时如果要插入一个值是4的新节点，不再需要和原节点8,7,6,5,3逐一比较，只需要比较关键节点7,5,3
- 确定了新节点在关键节点中的位置(3和5之间)，就可以回到原链表，迅速定位到对应的位置插入(同样是3和5之间)
这样一个插入就完成了。
2. 多层索引
当然，既然已经提取出了一层关键节点作为索引，那么可以进一步提取索引，提出一层索引的索引
有了2级索引之后，新的节点可以先和2级索引比较，确定大体范围；
然后再和1级索引比较；
最后再回到原链表，找到并插入对应位置。
层级极限是什么？
当节点足够多的时候，不止能提出2层索引，还可以向更高层次提取，保证每一层是上一层节点数的一半
至于提取的极限，则是：同一层只有两个节点的时候，因为一个节点没有比较的意义。
这样的多层链表结构，就是所谓的跳跃表
3. 怎么从新节点选取一部分提到上一层
当大量的新节点通过逐层比较，最终插入到原链表之后，上层的索引节点会渐渐变得不够用。
这时候需要从新节点当中选取一部分提到上一层。
使用抛硬币。
也就是随机决定新节点是否提拔，每次向上提拔一层的几率是 50%
为什么要用抛硬币
- 因为跳跃表删除和添加的节点是不可预测的，很难用一种有效的算法来保证跳表的索引部分始终均匀。
- 随机抛硬币的方法虽然不能保证索引绝对均匀分布，却可以让大体趋于均匀
4. 插入节点流程
- 新节点和各层索引节点逐一比较，确定原链表的插入位置。O（logN）
- 把新节点插入到原链表。O（1）
- 利用抛硬币的随机方式，决定新节点是否提升为上一级索引。结果为“正”则提升并继续抛硬币，结果为“负”则停止。O（logN）
5. 删除节点流程
删除操作比较简单
- 只要在【索引层】找到【要删除的节点】，然后顺藤摸瓜，【删除每一层的相同节点】即可。
- 如果某一层索引在删除后只剩下一个节点，那么整个一层就可以干掉了。
还用上面的例子，如果要删除的节点值是5:
删除节点的步骤：
- 自上而下，查找第一次出现节点的索引，并逐层找到每一层对应的节点。O(logN)
- 删除每一层查找到的节点，如果该层只剩下1个节点，删除整个一层（原链表除外）。O(logN)
6. 跳跃表和二叉查找树的区别
跳跃表的优点：维持【结构平衡】的成本比较低，完全依靠【随机】
二叉查找树：在多次插入、删除后，需要rebalance来重新调整结构平衡
7. 跳跃表的实际运用
- Redis 当中的 Sorted-set 这种有序集合，正是对跳跃表的改进和应用。
- 对于关系型数据库如何维护有序的记录集合呢？使用的是 B+ 树。