这是发生在很多年以前的故事……
咱们需要做一个拍卖行系统，用来查阅和出售游戏中的道具。
拍卖行的商品总数量有几十万件，对应数据库商品表的几十万条记录。
如果是按照商品名称精确查询还好办，可以直接从数据库查出来，最多也就上百条记录。
如果是没有商品名称的全量查询怎么办？总不可能把数据库里的所有记录全查出来吧，而且还要支持不同字段的排序。
所以，只能提前在内存中存储有序的全量商品集合，每一种排序方式都保存成独立的集合，每次请求的时候按照请求的排序种类，返回对应的集合。
比如按价格字段排序的集合：
比如按等级字段排序的集合：
拍卖行商品列表是线性的，最容易表达线性结构的自然是数组和链表。可是，无论是数组还是链表，在插入新商品的时候，都会存在性能问题。
按照商品等级排序的集合为例，如果使用数组，插入新商品的方式如下：
如果要插入一个等级是3的商品，首先要知道这个商品应该插入的位置。使用二分查找可以最快定位，这一步时间复杂度是O（logN）。
插入过程中，原数组中所有大于3的商品都要右移，这一步时间复杂度是O（N）。所以总体时间复杂度是O（N）。
如果使用链表，插入新商品的方式如下：
如果要插入一个等级是3的商品，首先要知道这个商品应该插入的位置。链表无法使用二分查找，只能和原链表中的节点逐一比较大小来确定位置。这一步的时间复杂度是O（N）。
插入的过程倒是很容易，直接改变节点指针的目标，时间复杂度O（1）。因此总体的时间复杂度也是O（N）。
这对于拥有几十万商品的集合来说，这两种方法显然都太慢了。
什么是跳跃表
这时候，可以用到跳跃表这种数据结构。
跳跃表是一种基于有序链表的扩展，简称跳表。
跳表利用类似索引的思想，提取出链表中的部分关键节点。比如给定一个长度是7的有序链表，节点值依次是
1->2->3->4->5->6->7->8。那么我们可以取出所有值为奇数的节点作为关键节点。
此时如果要插入一个值是4的新节点，不再需要和原节点8，7，6，5，3逐一比较，只需要比较关键节点7，5，3.
确定了新节点在关键节点中的位置（3和5之间），就可以回到原链表，迅速定位到对应的位置插入（同样是3和5之间）。
现在节点数目少，优化效果还不明显，如果链表中有1W甚至10W个节点，比较次数就整整减少了一半！
这样做法虽然增加了50%的额外的空间，但是性能提高了一倍。
不过我们可以进一步思考。既然已经提取出了一层关键节点作为索引，那我们为何不能从索引中进一步提取，提出一层索引的索引？
有了2级索引之后，新的节点可以先和2级索引比较，确定大体范围；然后再和1级索引比较；最后再回到原链表，找到并插入对应的位置。
当节点很多的时候，比较次数会减少到原来的四分之一。
当节点足够多的时候，不止能提出两层索引，还可以向更高层次提取，保证每一层是上一层节点数的一半。
至于提取的极限，则是同一层只有两个节点的时候，因为一个节点没有比较的意义。这样的多层链表结构，就是所谓的跳跃表。
跳跃表的插入
当大量的新节点通过逐层比较，最终插入到原链表之后，上层的索引节点会渐渐变得不够用。这时候需要从新节点当中选取一部分提到上一层。跳跃表设计者采用了一种有趣的办法：抛硬币。也就是随机决定新节点是否提拔，每向上提拔一层的几率是50%。
我们仍然借用刚才的例子，假如值为9新节点插入原链表。
因为跳跃表删除和添加的节点是不可预测的，所有很难用一种有效的算法来保证跳表的索引分部始终均匀。
随机抛硬币的方法虽然不能保证索引绝对均匀分布，却可以让大体趋于均匀。
总结一下，跳跃表插入节点的流程有以下几步：
新节点和各层索引节点逐一比较，确定原链表的插入位置。O（logN）
把索引插入到原链表。O（1）
利用抛硬币的随机方式，决定新节点是否提升为上一级索引。结果为“正”则提升并继续抛硬币，结果为“负”则停止。O（logN）
总体上，跳跃表插入操作的时间复杂度是O（logN），而这种数据结构所占空间是2N，既空间复杂度是 O（N）。
跳跃表的删除
删除操作比较简单，只要在索引层找到要删除的节点，然后顺藤摸瓜，删除每一层的相同节点即可。
如果某一层索引在删除后只剩下一个节点，那么整个一层就可以干掉了。还用原来的例子，如果要删除的节点值是5：
总结一下，跳跃表删除节点的步骤：
自上而下，查找第一次出现节点的索引，并逐层找到每一层对应的节点。O（logN）
删除每一层查找到的节点，如果该层只剩下1个节点，删除整个一层（原链表除外）。O（logN）
总体上，跳跃表删除操作的时间复杂度是O（logN）。
跳跃表与二叉查找树的区别
跳跃表的优点是维持结构平衡的成本比较低，完全依靠随机。而二叉查找树在多次插入删除后，需要rebalance来重新调整结构平衡。