LevelDB源码分析之五：skiplist（1）

LevelDB源码分析之五：skiplist（1）

一.skiplist简介跳表是由William Pugh发明。他在 Communications of the ACM June 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees，在该论文中详细解释了跳表的数据结构和插入删除操作。跳跃表使用概率均衡技术而不是使用强制性均衡，因此，对于插入和删除结点比传统上的平衡树算法更为简洁高效。参考算法导论，跳表插入、删除、查找的复杂度均为O(logN)。LevelDB的核心数据结构是用跳表实现的，redis的sorted set数据结构也是用跳表实现的。 下面来研究一下跳表的核心思想：

先从链表开始，如果是一个单链表，那么我们知道在链表中查找一个元素I的话，需要将整个链表遍历一次，时间复杂度为O(n)。

如果是说链表是排序的，并且结点中还存储了指向后面第二个结点的指针的话，那么在查找一个结点时，仅仅需要遍历N/2个结点即可。因为我们可以先通过每个结点最上面的指针先进行查找，这样子就能跳过一半的节点。比如我们想查找19，首先和6比较，大于6之后，在和9进行比较，然后在和12进行比较......最后比较到21的时候，发现21大于19，说明查找的点在17和21之间，从这个过程中，我们可以看出，查找的时候跳过了3、7、12等点，因此查找的时间复杂度为O(n/2)（只是下图的情况）。

其实，上面基本上就是跳跃表的思想，每一个结点不单单只包含指向下一个结点的指针，可能包含很多个指向后续结点的指针，这样就可以跳过一些不必要的结点，从而加快查找、删除等操作。对于一个链表内每一个结点包含多少个指向后续元素的指针，这个过程是通过一个随机函数生成器得到，这样子就构成了一个跳跃表。这就是为什么论文“Skip Lists : A Probabilistic Alternative to Balanced Trees ”中有“概率”的原因了，就是通过随机生成一个结点中指向后续结点的指针数目。随机生成的跳跃表可能如下图所示。

如果一个结点存在k个指向后续元素指针的话，那么称该结点是一个k层结点。一个跳表的层MaxLevel义为跳表中所有结点中最大的层数。跳表的所有操作均从上向下逐层进行，越上层一次next操作的跨度越大。

二.skiplist原理

为了描述方便，将跳表结构绘画成如下形式。

跳表结构：

(1) 由多层结构组成 (2) 每一层都是一个有序的链表 (3) 最底层(Level 1)的链表包含所有元素 (4) 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。 (5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

1.跳表的查找

例子：查找元素 117 (1) 比较 21， 比 21 大，往后面找 (2) 比较 37,   比 37大，比链表最大值小，从 37 的下面一层开始找 (3) 比较 71,  比 71 大，比链表最大值小，从 71 的下面一层开始找 (4) 比较 85， 比 85 大，从后面找 (5) 比较 117， 等于 117， 找到了节点。

2.跳表的插入

1）K小于链表的层数

先确定该元素要占据的层数 K（采用丢硬币的方式，这完全是随机的），然后在 Level 1 ... Level K 各个层的链表都插入元素。 例子：插入 119， K = 2

2）K大于链表的层数

如果 K 大于链表的层数，则要添加新的层。 例子：插入 119， K = 4

插入元素的时候，元素所占有的层数完全是随机的，通过某种随机算法产生。

3.跳表的删除

在各个层中找到包含 x 的节点，使用标准的 delete from list 方法删除该节点。

例子：删除 71

三.简单的skiplist实现

运行结果如下，由于K值得随机性，并不是每次的运行结果都是这样。

参考链接：​​http://kenby.iteye.com/blog/1187303​​

参考链接：​​http://dsqiu.iteye.com/blog/1705530​​

​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。