这是发生在很多年以前的故事......
image
image
image
image
几天以前......
image
image
image
image
image
几天之后......
image
拍卖行的商品总数量有几十万件，对应数据库商品表的几十万条记录。
如果是按照商品名称精确查询还好办，可以直接从数据库查出来，最多也就上百条记录。
如果是没有商品名称的全量查询怎么办？总不可能把数据库里的所有记录全查出来吧，而且还要支持不同字段的排序。
所以，只能提前在内存中存储有序的全量商品集合，每一种排序方式都保存成独立的集合，每次请求的时候按照请求的排序种类，返回对应的集合。
比如按价格字段排序的集合：
image
比如按等级字段排序的集合：
image
需要注意的是，当时还没有Redis这样的内存数据库，所以小灰只能自己实现一套合适的数据结构来存储。
image
拍卖行商品列表是线性的，最容易表达线性结构的自然是数组和链表。可是，无论是数组还是链表，在插入新商品的时候，都会存在性能问题。
按照商品等级排序的集合为例，如果使用数组，插入新商品的方式如下：
image
如果要插入一个等级是3的商品，首先要知道这个商品应该插入的位置。使用二分查找可以最快定位，这一步时间复杂度是O（logN）。
插入过程中，原数组中所有大于3的商品都要右移，这一步时间复杂度是O（N）。所以总体时间复杂度是O（N）。
如果使用链表，插入新商品的方式如下：
image
如果要插入一个等级是3的商品，首先要知道这个商品应该插入的位置。链表无法使用二分查找，只能和原链表中的节点逐一比较大小来确定位置。这一步的时间复杂度是O（N）。
插入的过程倒是很容易，直接改变节点指针的目标，时间复杂度O（1）。因此总体的时间复杂度也是O（N）。
这对于拥有几十万商品的集合来说，这两种方法显然都太慢了。
image
——————————————
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
-
新节点和各层索引节点逐一比较，确定原链表的插入位置。O（logN）
-
把索引插入到原链表。O（1）
-
利用抛硬币的随机方式，决定新节点是否提升为上一级索引。结果为“正”则提升并继续抛硬币，结果为“负”则停止。O（logN）
总体上，跳跃表插入操作的时间复杂度是O（logN），而这种数据结构所占空间是2N，既空间复杂度是 O（N）。
image
image
image
image
image
image
-
自上而下，查找第一次出现节点的索引，并逐层找到每一层对应的节点。O（logN）
-
删除每一层查找到的节点，如果该层只剩下1个节点，删除整个一层（原链表除外）。O（logN）
总体上，跳跃表删除操作的时间复杂度是O（logN）。
image
image
image
小灰和大黄并不知道，他们的这一解决方案和若干年后Redis当中的Sorted-set不谋而合。而Sorted-set这种有序集合，正是对于跳跃表的改进和应用。
From: http://posts.careerengine.us/p/596625702f6a800cc5830235
网友评论