我最近开始学习lucene，并开始了解lucene是如何存储和查询索引的。Lucene似乎是使用跳表作为底层数据结构。但是，我没有发现任何理由使用跳表而不是二叉树。
跳转列表的优点是在并发使用时提供了很好的性能，Lucene允许每个索引使用一个写线程，所以跳过列表在这里也没有帮助。除了那个二叉树（自平衡）胜过跳表-因为它提供了O最坏情况复杂度（logn）来进行阅读，而跳表在平均情况下提供了相同的时间复杂度。而且，与跳表相比，二叉树将以更好的时间来服务范围查询。为了也服务合取查询，lucene使用多个发布列表的跳过列表来找到它们的交集-对于这种情况，二叉树已经足够了。
有没有什么我没有注意到的特定原因，在lucene中使用跳表来建立索引？
1条答案
按热度按时间gajydyqb1#
Lucene使用磁盘上的Skip-Lists建立一个倒排索引，然后使用一个有限状态转换器（FST）将索引项的Map加载到内存中。
在这个答案中，它还指出了使用跳过列表的主要好处是它 * 永远 * 不必重新平衡B树。如果你想更深入地挖掘这个答案，请引用另一个提供了更多细节的答案：跳过列表与二叉搜索树哪个实习生参考其他白皮书。
再研究一下这个问题，使用Skip-Lists而不是BTree还有一个好处。它不仅避免了重新平衡，而且还避免了在重新平衡时锁定树的一部分。这方面将在这里进一步讨论。后一个好处提高了并发性。