一、业务场景
某游戏开发公司，boss交代程序员开发一套拍卖行系统，用来查阅和出售游戏中的道具。拍卖行商品可以按照等级、价格等排序并展示给玩家，支持全名称的精确搜索和不输入名称的全量查询。
拍卖行系统
游戏中的商品动辄几十万的数量，如果是精确搜索还好办，可以直接查询数据库，但是如果是全量搜索的话，不仅要将数据库中所有的记录查询出来，还要支持排序。因此我们可以提前在内存中存储有序的全量商品集合，每一种排序方式都保存成独立的集合，根据不同请求的排序种类，返回不同的集合结果。
假设在当时的环境下并没有redis这样的内存数据库，你会选择什么样的数据存储结构呢？
二、分析
拍卖行商品列表是线性的，因此我们首先考虑到的是数组和链表，可是仔细考虑，无论是数组还是链表，在插入新商品的时候，都会存在性能问题。
以按照商品等级排序为例，假如我们使用数组结构，那么我们在插入新商品的时候，首先我们需要知道插入商品的位置。这里我们可以使用二分查找法，时间复杂度为O（logN）。在插入的过程中，我们需要将插入位置之后的数据全部后移一位，这一步时间复杂度为O（N），所以总体的时间复杂度为O（N）。
假如我们使用链表结构，我们同样的首先需要知道插入商品的位置，这里我们无法使用二分查找法，只能逐节点比较，时间复杂度为O（N）。插入的过程倒是容易，我们只需要改变节点指向的目标位置，这一步的时间复杂度为O（1），因此总体时间复杂度为O（N）。
相对于几十万的商品集合来说，这两种方法显然都太慢了。那么有没有一种数据结构能够提高性能呢？
三、跳跃列表
跳跃列表（skipList）是一种基于有序列表的扩展，简称跳表。
在详细解释跳跃列表之前，我们不妨思考这样一个问题：怎样才能跟更快的查找到一个有序列表的某一个节点呢？
我们可以利用类似索引的思想，提取中链表中的部分关键节点。比如给定一个1>2>3>5>6>7的有序链表，我们可以提取中中间的奇数作为关键节点。假如我们此时需要插入元素4，我们无需逐一比较，只需要比较关键节点3、5、7。在确定新节点在关键节点中的位置，我们就可以在原链表中，迅速定位到节点并且插入。数据量小的情况下，优化效果不是十分明显，如果链表中有1w甚至10w个节点，比较次数就整整减少了一半！这样的做法虽然增加了50％的空间，但是性能提高了一倍。
现在我们可以进一步思考，我们能否再已经提取的索引基础上，进一步提取出一层索引的索引？事实上这是可以的，当有了二级索引后，新节点可以先和二级索引比较，确定大体范围，然后再跟一级索引比较，最后回到原链表，插入节点。当节点很多的时候，比较次数就能减少到原来的四分之一。我们可以利用这样的思想，不断向上抽取，保证每一层是上层节点的一半，至于提取的极限，是当同一层只有两个节点的时候，因为一个节点没有比较的意义。这样的多层链表结构，就是所谓的【跳跃表】。
跳跃列表的"提拔"机制
这时候出现了一个问题，当大量的数据节点被插入到原链表中，上层的节点会逐渐变得不够用。这时候需要从新节点中选取一部分提到上一层，可是究竟应该"提拔"谁，忽略谁呢？
跳跃列表的设计者采取了一种有趣的方案：【抛硬币】。也就是随机决定新节点是否提拔，每向上提拔一层的概率是50％。
至于为什么要采取这么奇怪的方法，这是因为跳跃列表的添加和删除节点是不可预测的，我们很难使用一种有效的算法来保证所索引始终均匀。随机抛硬币的方法虽然不能保证索引绝对均匀分布，却可以让索引大体趋于均匀。
插入
跳跃列表插入节点的流程大致可以分为以下几步：
- 新节点和各层索引节点逐层比较，确定原链表的插入位置，时间复杂度为O（logN）
- 将元素插入到原链表，时间复杂度为O（1）
- 利用抛硬币的方式提拔节点为上一层索引，时间复杂度为O（logN）
综上所述，跳跃列表插入的操作的时间复杂度为O（logN），而这种数据结构所占空间是2N，即空间复杂度为O（N）。
删除
跳跃列表删除节点大致可以分为以下几步：
-
自上而下，查找第一次出现节点的索引，并逐层找到每一层对应的节点。O（logN）
-
删除每一层查找到的节点，如果该层只剩下1个节点，删除整个一层（原链表除外）。O（logN）
总体上，跳跃表删除操作的时间复杂度是O（logN）
四、跳跃列表VS二叉查找树
跳跃列表的优点是维持结构平衡的成本比较低，完全依靠随机。而二叉查找树在多次插入删除后，需要rebalance来重新调整结构平衡。
没有绝对优劣的数据结构，关键还是要看应用场景。
这一解决方案和Redis当中的Sorted-set不谋而合。而Sorted-set这种有序集合，正是对于跳跃表的改进和应用。而对于关系型数据库如何维护有序的记录集合呢？他们使用的是B+树。有关B+树的知识，将在以后的章节中提到。
网友评论