Lucene SkipList 深入分析(1)

引言

了解事物如何运行最好的方法是自己尝试来设计它。本文尝试使用跳表SkipList进行分析，为进一步深入理解Lucene搜索引擎的SkipList打下坚实的基础。
相比Red-Black Tree数据结构，SkipList是一种相对简单的数据结构，但是它具有与复杂的红黑树相同的效率。
SkipList的基本操作的时间复杂度如下：

操作	时间复杂度
插入	O(log N)
删除	O(log N)
查找	O(log N)
枚举	O(N)

这使得SkipList成为一种非常有效率的数据结构，可以作为排序的数据集的底层存储。强调一点：SkipList处理的是有序的数据集。
从单链表到跳表

首先，考虑一个普通的有序单链表。单链表基本操作的时间复杂度如下：

操作	时间复杂度
插入	O(N)
删除	O(N)
查找	O(N)
枚举	O(N)

有序单链表的插入，删除和搜索操作都是O(N)。对于链表结构，我们只能线性遍历，搜索时不能跳过节点。有序单链表完全退化成无序的单链表，并没有充分利用”有序“这一特征。
那么，我们怎样才能使有序单链表上的操作更加高效呢？
有一个想法是：引入一个排序的多层链表。SkipList与Link链表结构相似，它只是引入了“分层”的思想，从上到下的每一层都是一个有序链表。
搜索

引入多层链表的设计是为了提高查找效率，现在我们查找一个特定的元素是否在集合中只需要O(log N)。此时的查找算法是从最高层向下查找过程，很接近二分搜索算法。比如，当搜索一个特定元素时，首先从最高层链表开始遍历，一层一层遍历最后下沉到原始链表。

插入与删除

O(log N)是一个不错的搜索时间复杂度。它付出的代价是：在对元素进行插入与删除的时候需要维护这个多层的链表结构。具体来说是：

删除元素节点时，通过高层链表索引向低层链表索引逐层递进，进行查找，并在这个查找过程中对节点进行删除。
添加新元素节点时，对多层的链表进行更新。它的逻辑相对要复杂一些，当每次有新的元素节点插入时，需要通过概率算法告诉当前插入元素节点需要插入到第几层链表索引节点中。

简言之，SkipList跳表采用空间换时间的基本设计思路。
为什么Lucene提供SkipList的索引而不是BTree?

众所周知的是，在关系数据库中进行索引最流行的数据结构是BTree或者一些变体。相比其它数据结构，BTree树执行磁盘IO操作来运行查找的次数更少。
数据大部分时间都存储在磁盘上，只有在运行查询才被加载到内存缓存中，BTree本身特征可以减少磁盘IO的操作。但随着内存大小的增加，越来越多的数据直接加载进内存，SkipList数据结构适合同时在内存和磁盘上的数据进行索引。
SkipList的优点

内存优化

Lucene的存储模型即支持行存储又支持列存储模式。其中对Fields正向索引信息的存储（e.g. fdt/fdx文件）体现为行存储模式，对倒排索引信息的存储（e.g. tis/frq/pros文件）体现为列存储模式。
Lucene中行存储是为了快速，高吞吐量地访问内存中的数据而设计。Lucene中列存储是为了集中管理term的倒排索引数据而设计，以便通过查询接口快速方便取出用户搜索的关键字对应的文档列表。
简单

相比BTree结构，SkipList的实现更加简单。例如，BTree需要处理页面合并与分裂，而SkipList并没有相应的操作。
无锁与并发

Skiplist Indexes VS. B+ Tree Indexes

Skiplist跳表用于存储已排序的列表，非常类似Binary Search Tree。对比B+ Tree最主要的优点是它最适合并发访问。
一方面，当我们研究B+ Tree的时候，会简化成2-3-4树来理解与分析。而Red Black Tree本质上可以看成是2-3-4树。当一个数据元素被修改或者删除时，无论是2-3-4树，B+树还是红黑树都要涉及到页分裂与页合并操作。这个过程中也伴随着递归对树节点进行旋转操作，以达成树的平衡。而并发访问（修改或者删除节点）树的问题就是互斥锁定。
考虑下图，插入一个红色节点，挂在4-节点下（将框中“上黑下二红节点”理解成2-3-4树中的&#34;4-节点&#34;），在一棵红黑树中，是不允许有两个相邻的红色结点的(stage1)，所以需要对4-节点加锁并更换颜色(stage2)。更换后颜色的Red Black Tree仍然违反“不允许两个相邻的红色结点”的原则，需要自底向上进行递归调整，整个过程可能会一直持续到根节点，加锁会损失对树操作的并发性。

另一方面，对Skiplist跳表进行插入，更新和删除节点时，只有直接连接到受影响的节点才需要锁定。
需要指出的是，Skiplist跳表对缓存并不存好，因为它们不会优化访问局部性，也就是说，链表连接的元素通常相隔很远，并不在相邻的页面上。
补充一句：如果你看到介绍与讲解Red Black Tree的资料，没有从2-3-4树角度进行关联解读，就是耍流氓。
SkipList的缺点？

CPU 缓存效率

SkipList不能充分利用内存的局部性原理。在搜索结果中遍历时，会在内存中基于分层的链表进行随机跳转。
反向迭代

大多SkipList通过增加previous指针来支持在列表中反向迭代。无锁的双向链表比较难于实现。
小结

Lucene中SkipList索引结构是空间换时间的基本设计思路。
于上，SkipList成为Lucene首选索引数据结构。