这实际上是我正在研究的一个真实问题，但为了简单起见，让我们假设我是 Google。
假设用户搜索“纳米级特百惠”。这两个词的页面并不多……只有大约 3k。但是大约有 200 万页带有“纳米级”，大约有 400 万页带有“特百惠”。不过，Google 在 0.3 秒内为我找到了 3k。
它是如何做到的？
我所知道的唯一算法是获取“nanoscale”的文档，获取“tupperware”的文档，然后进行列表合并。但这是 O(N + M) 或 O(5,000,000)，这似乎有点慢。特别是如果我在桌面上运行它而不是超快集群。
那么这实际上是 Google 正在做的事情吗？他们的速度主要是因为他们在其庞大的分布式集群上运行这种昂贵的计算？
或者是否有我不知道的更好的算法？维基百科和谷歌没有为我找到任何东西。
编辑:
由于人们似乎关注我的问题的 Google 方面，我想我会用实际的术语重申一下。
我有几个非常大的(数百万项)索引作为键/值对实现。键是简单的单词，值是文档集。一个常见的用例是在不同索引上的多个搜索中获得结果的交集:痛点是获得文档集的交集。
我可以根据需要重新实现我的索引 - 目前这主要是一个学术项目。
最佳答案
按照您描述的方式，您已经有一个 inverted index ，每个学期都有一个发布列表(文档列表)。我不知道有什么比合并加入每个术语的发布列表更好的解决方案，据我所知，这就是像 Lucene 这样的全文索引解决方案所做的。不过，您可以在此处进行一些明显的优化:
- 如果您可以将数据集存储在内存中，甚至分布在多台机器上，您就可以 merge join与磁盘搜索所需的相比，结果集确实非常快。
- “朴素”的合并联接算法在每个不匹配项上将一个指针前进一个位置，但是如果您的发布列表本身已编入索引，您可以做得更好，方法是取各个当前值的最大值，然后求在所有其他发布列表中，第一个值大于或等于该键 - 可能会在此过程中跳过数百万个不相关的结果。这被称为 zig-zag merge join .
关于algorithm - 搜索多个值的索引的算法是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2313363/