我很好奇Lucene中搜索和排序的时间复杂度

Question

我很好奇Lucene中搜索和排名的时间复杂度。

我了解到Lucene支持使用IndexSearcher进行搜索。 IndexWriter 在倒排索引数据结构中构建和存储文档。多亏了倒排索引，我知道搜索单词“apple”可以在 O(1) 时间复杂度内完成，以检索所有相关文档（n 个文档）。

TopDocs topDocs = shardSearcher.search(query, 10);

使用上面的代码，我们只能对 n 个文档中的 10 个进行排序和检索。据我所知，排名是使用 TF-IDF 等算法完成的。我假设这些算法所需的数据结构是在搜索之前预先构建的。在这种情况下，我很好奇排名的时间复杂度。

•   We need to calculate the TF-IDF score for n documents: O(N)
•   We need to sort the scores: Using a priority queue (Min-Heap of size 10), this would be NlogK.

如果文档数量（n）非常大，比如说超过十亿，那么每次搜索的 NlogK 时间复杂度难道不会成为性能负担吗？

根据我的发现，我明白在最坏的情况下，可能仍然需要检查所有文件。然而，Lucene 使用了各种优化技术，例如跳过列表、块跳过、提前终止和优先级队列，这使得它能够在大多数情况下高效地找到前 10 个结果，而无需扫描所有文档。

这是正确的吗？

Answer 1

你是对的，基本上是正确的。 如果文档数量 (n) 非常大，比如超过十亿，那么每次搜索都会非常慢。

但是现在，我们使用分布式组件来提高速度。你应该将你的数据（非常大，比如TB）分散到许多节点，并在每个节点中搜索，然后收集搜索结果以生成你想要的内容。