漫画：什么是跳跃表？

正文

请到「今天看啥」查看全文

需要注意的是，当时还没有Redis这样的内存数据库，所以小灰只能自己实现一套合适的数据结构来存储。

拍卖行商品列表是线性的，最容易表达线性结构的自然是数组和链表。可是，无论是数组还是链表，在插入新商品的时候，都会存在性能问题。

按照商品等级排序的集合为例，如果使用数组，插入新商品的方式如下：

如果要插入一个等级是3的商品，首先要知道这个商品应该插入的位置。使用二分查找可以最快定位，这一步时间复杂度是O（logN）。

插入过程中，原数组中所有大于3的商品都要右移，这一步时间复杂度是O（N）。所以总体时间复杂度是 O（N）。

如果使用链表，插入新商品的方式如下：

如果要插入一个等级是3的商品，首先要知道这个商品应该插入的位置。链表无法使用二分查找，只能和原链表中的节点逐一比较大小来确定位置。这一步的时间复杂度是O（N）。

插入的过程倒是很容易，直接改变节点指针的目标，时间复杂度O（1）。因此总体的时间复杂度也是O（N）。

这 对于拥有几十万商品的集合来说，这两种方法显然都太慢了。

——————————————

请到「今天看啥」查看全文