lucene - 倒排索引 vs 二叉树 vs ...？

Question

我一直在使用 Elastic Search(由底层的 Lucene 提供支持)并且它非常棒。无论我向它扔什么，它都快如闪电。

我想知道为什么它现在变快了。我理解它使用倒排索引，并且我部分理解基于我发现的几篇文章和一些很好的 youtube 视频解释它的内容，但是为什么这比 Mysql 或 Mongo 中的二叉树快得多？我知道这有点像苹果和橘子的比较，但我一直没能找到任何关于倒排索引如何与二叉树索引相比如何工作的真正好的解释(比如并排)会工作。

到目前为止我收集到的唯一一件事是，基于索引时间，倒排索引总是更快，因为它不必重新平衡树的叶子(分形索引也是如此)。

Answer 1

这都是关于权衡的。

Lucene 的索引与 B 树非常不同，它基于一次写入的段。对于每个段，都有一个 terms dictionary和 postings lists .查找一个术语需要在术语词典中阅读有关该术语的一些信息，然后它们会跳转到其发布列表的开头，您将能够在其中按顺序阅读与该术语匹配的文档列表。术语词典中的查找基于二进制搜索的变体，以便能够有效地运行范围查询。

每次添加文档时，都会创建一个新段(这就是 Lucene 在批量更新方面做得更好的原因)，当段数达到可配置的阈值(称为合并因子)时，一些段会合并在一起(基于 MergePolicy )。

这种设计让 Lucene 可以高效地运行许多查询，但另一方面，Lucene 在单文档原子更新方面仍然不是很好(因为每次提交都需要刷新一个新的段，并且因为你需要重新索引整个文件，无论你修改多大)。正在进行与 individual field updates 相关的工作但这仍然是实验性的。