倒置索引与二叉树vs ...？

Question

我一直在使用Elastic Search(由Lucene提供支持)并且非常棒.无论我扔什么,它都会快速燃烧.

我想知道为什么它现在快.我理解它使用倒排索引,我部分理解基于我发现的几篇文章以及一些很好的YouTube视频解释它的内容,但为什么这比Mysql或Mongo中的二叉树快得多？我知道它有点拿苹果和橘子比较,但我一直没能找到任何真正好的解释(如由一侧的侧)如何倒排索引的作品相比,二叉树指数将如何工作.

到目前为止,我唯一收集的是基于索引时间,反向索引总是更快,因为它不必重新平衡树的叶子(对于分形索引也是如此).

Answer 1

这完全取决于权衡.

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

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

这种设计允许Lucene有效地运行许多查询,但另一方面,Lucene仍然不擅长原子单文档更新(因为每次提交都需要刷新一个新段,因为你需要重新索引整个文档,没有无论你修改多大).目前正在进行与个别领域更新相关的工作,但这仍然是实验性的.