Lucene如何组织和遍历倒排索引？

Question

3

在SQL中，索引通常是一种平衡树（有序节点，指向真实的表行以便在O(log n)时间内进行搜索）。遍历这样的树实际上就是搜索过程。

现在，Lucene使用倒排索引和词项频率：它为每个词项存储它在哪些文档中出现了多少次。这很容易理解。但这并没有解释如何实际执行对这样一个索引的搜索。

当然，搜索字符串也会被分析并分成相同的词项，然后“搜索索引”以查找包含它们的文档——但是如何呢？Lucene索引本身是否也按某种方式有序且类似于树形组织，以使O(log n)成为可能？还是说在搜索时遍历Lucene索引实际上是线性的，因此是O(n)？

- Foo Bar

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel Schneiter · Accepted Answer

这并没有简单的答案。首先，因为内部格式从版本到版本都得到了改进；其次，随着Lucene 4的出现，引入了可配置的编解码器，它们作为逻辑格式和实际物理格式之间的抽象。

索引由分片和副本组成，每个分片和副本都是一个Lucene索引本身。然后，Lucene索引又由多个段组成，而每个段又是一个Lucene索引。一个段是只读的，并由多个工件组成，可以保存在文件系统或RAM中。

Adrien Grand的“Lucene索引中有什么”是关于Lucene索引组织的一份优秀的演示文稿。Michael McCandless的博客文章和Elastic的博客文章则介绍了Lucene 4中引入的编解码器。

因此，查询Lucene索引实际上会并行查询多个段，利用特定的编解码器。编解码器可以表示文件系统或RAM中的结构，通常针对特定需求进行了优化/压缩。内部格式可以是任何东西，例如树、哈希映射、有限状态机等。只要在搜索查询中使用通配符字符（“？”或“*”），这就自动导致对索引进行更多或更少的遍历。