图解Skip List——本质是空间换时间的数据结构，在lucene的倒排列表，bigtable，hbase，cassandra的memtable，redis中sorted set中均用到

Skip List的提出已有二十多年[Pugh, W. (1990)]，却依旧应用广泛（Redis、LevelDB等）。作为平衡树(AVL、红黑树、伸展树、树堆)的替代方案，虽然它性能不如平衡树稳定，但是在实现难度上却很有优势。它的查询、插入、删除等主要操作时间复杂度也都是Θ(lgn)，空间复杂度是Θ(n)。

一个Skip List的结构如下图，除了数据域，每个节点还包括1个或多个域用来保存后续节点的位置。

从结构上看，Skip List通过增加层数，节点上可以带有更多的信息，通过这些信息可以直接访问更远的节点（这 也是Skip List精髓所在），就像跳过去一样，所以取名叫Skip List（跳表）。

Skip List查询

查询操作很简单，比如我们要找图中节点key为 20 的节点。

• 我们首先获取到头节点，从头检点的最高层开始（节点中的点表示指向节点的指针），下一个节点是 17 , 很明显 20>17 所以应该在后面。继续往后结果是 NULL 那说明后面没有要找的节点了。
• 跳到下一层继续往后是 25 且 20<25 说明后面也没有我们要找的节点了。
• 再跳到下一层，往后就找到我们要的节点了。如果到最下面一层还找不到，那这个节点就肯定不在表中了（因为最低层包含所有节点）。

Skip List插入

插入操作稍微复杂， 首先我们要找到插入位置，怎么找我们刚才已经描述过了。如下图所示，插入key为 10 的节点，插入点应该是节点 9 和节点 12 之间（紫色的线表示要更新的指向）。然后是插入节点 10 ，其实就是链表的逐层插入。

这里的需要注意是，逐层插入需要知道节点在每一层的位置，如在level-2中，节点 10 前面应该是头结点，而后面应该是节点 17 。 因为查询操作得到的只是最后位置，所以通常需要一个临时的空间来记录这些信息。如果节点的高度超过超过了Skip List的最大层数，那么Skip List的层数相应的需要升高。如节点 10 的高度是 4 的话，根据Skip List的结构特点，那么层数需要提高到level-3。

节点高度与Skip List的最大层数

理想的SkipList结构（如图一）是第一层有所有的节点，第二层只有1/2的节点，且是均匀间隔的，第三 层是1/4的节点，且是均匀间隔的...，那么理想的层数是lgnlgn。

每一次插入一个新节点时，最好的做法就是根据当前表的结构得到一个合适的高度，插入后可以让Skip List的尽量的接近理想的结构，但是实现上这会非常的复杂。

Pugh论文中提出的方法是根据概率随机为新节点生成一个高度，具体的算法如下：

• 给定一个概率pp, 产生一个[0,1)[0,1) 之间的随机数
• 如果这个随机数小于pp,则高度加11
• 重复以上动作，直到随机数大于概率pp

虽然随机生成的高度会打破理想的结构，Pugh在论文中证明，这种结构依然有非常 高概率 可以使得时间复杂度为Θ(lgn)Θ(lgn)。

通常我们还会约束Skip List的最大层数，公式：maxLevel=log1/pnmaxLevel=log1/pn,其中n表示节点总数。 根据Pugh论文中的结论，p为1/2或者1/4时，整体性能会比较好。(当p=1/2时，确定节点高度有的地方称为抛硬币的方法)。

Skip List删除

删除操作跟插入操作类似。

有兴趣可以看看Pugh论文！

转自：http://www.zkt.name/skip-list/