search - lucene 怎么这么快计算文档的交集？

Question

允许这样做的存储和搜索的内部结构是什么？就像在细节中一样？

例如，我有一百万个文档与一个词匹配，还有一百万个文档与 AND 查询的第二个词匹配。 lucene 怎么这么快就给我top k了？

它是否按照每个学期增加文档 ID 的顺序存储文档？然后，当两个术语的文档必须相交时，它会在这两个集合中查找第一个公共(public)的 k 个文档，方法是在一次遍历中增量地迭代它们。

或者，它是否使用较大文档数组中的简单无序散列集来查找公共(public)文档？

或者是否根据用户询问的文档数量、与单个术语匹配的文档数量等因素，同时使用这种(或可能更多)类型的交叉策略？

任何可以指出文档数组合并细节的文章都将不胜感激。

编辑:
感谢您的信息。现在说得通了。跳过列表很神奇。我将更深入地研究它以获得清晰的理解。

Answer 1

索引包含已排序的文档。当您使用 and operator(term1 AND term2) 查询时，它使用两个迭代器，因此当您知道第一个 term1 以 docN 开头时，您可以跳过 term2 的所有文档直到 docN。因此不仅有带有 next 方法的迭代器，而且还有非常高效的 skipTo 方法。它是通过跳过列表索引(http://en.wikipedia.org/wiki/Skip_list)实现的。
因此，通过使用 next 和 skipTo 方法，我们对大块进行非常快速的迭代，并且由于数据稀疏(例如，这些数据不适用于通常的数据库)它非常有效。

lucene 仅保存 N 最好的另一点，因此它比对所有分数文档进行排序要快得多。如果您请求 10 个最佳文档，它比您请求 20 个最佳文档要快两倍