Top-K 排序算法在 MongoDB 中是如何工作的

Question

根据答案和 MongoDB 文档，我了解到 MongoDB 能够对大型数据集进行排序并在使用 limit() 时提供排序结果。但是，当使用 sort() 查询相同的数据集时会导致内存异常。

从上面帖子的第二个答案中，海报提到整个集合被扫描、排序并返回前 N 个结果。我想知道当我使用 limit() 时集合是如何排序的。从文档中我发现当使用 limit() 时它会进行 Top-K 排序，但是在任何地方都没有太多关于它的解释。我想查看有关 Top-K 排序算法的任何参考资料。

Answer 1

一般来说，您可以使用大小为 K 的最小堆进行有效的 top-K 排序。最小堆表示迄今为止在数据集中看到的最大 K 个元素。它还使您能够恒定时间访问前 K 个元素中的最小元素。

\n\n

当您扫描数据集时，如果给定元素大于最小堆中的最小元素（即迄今为止最大的顶部 K 中的最小元素），则用该元素替换最小堆中的最小元素并重新-堆化（O(lg K)）。

\n\n

最后，您将得到整个数据集的前 K 个元素，而不必对它们全部进行排序（最坏情况的运行时间是O(N lg K)），仅使用\xce\x98(K)。

\n\n

我实际上是在学校学到这个来改变的:-)

\n