Lucene 索引建模 - 为什么使用跳表而不是 btree？

Question

最近开始学习lucene，了解了lucene是如何存储和查询索引的。 Lucene 似乎使用跳跃列表作为底层数据结构。但是，我没有找到任何理由在二叉树上使用跳过列表。

跳跃列表的优点是它在并发使用时提供良好的性能。而且 lucene 允许每个索引使用单个写入器线程，并且读取器从不可变段中读取，因此跳过列表在这里也没有帮助。除此之外，二叉树（自平衡）胜过跳跃列表 - 因为它为读写提供了 O(logn) 的“最坏”情况复杂度，而跳跃列表在“平均”情况下提供了相同的时间复杂度。此外，与跳跃列表相比，二叉树可以更快地提供范围查询。为了提供合取查询，lucene 使用多个倒排列表的跳过列表来查找它们的交集 - 对于这种情况，二叉树就足够了。 是否有任何我错过的在 lucene 中使用跳跃列表用于索引目的的具体原因？

Lucene 使用磁盘上的 Skip-List 构建倒排索引，然后使用有限状态转换器 (FST) 将索引项的映射加载到内存中。请参阅此答案

Lucene 如何索引文档？

Answer 1

在该答案中，它还表明使用 Skip-Lists 的主要好处是它避免了ever必须重新平衡 B 树。 如果您想更深入地挖掘该答案，请引用另一个提供更多详细信息的答案：

跳过列表与二叉搜索树

哪个实习生引用了其他白皮书。 进一步研究一下，使用 Skip-Lists 而不是 BTree 还有另一个优点。 不仅避免了重新平衡，而且还避免了在重新平衡发生时锁定树的一部分。 这方面将在here进一步讨论。 后一个优点提高了并发性。