Top-K排序算法在MongoDB中的工作原理

Question

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

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

Answer 1

通常，您可以使用大小为K的最小堆进行有效的top-K排序。最小堆表示到目前为止在数据集中看到的最大K个元素。它还为您提供了对前K个元素中最小元素的恒定时间访问。

在扫描数据集时，如果给定的元素大于最小堆中的最小元素(即，到目前为止最大的前K个元素中的最小元素)，则将最小堆中的最小元素替换为该元素并重新堆(O(lg K))。

最后，您只需要使用Θ(K)内存，就可以得到整个数据集的前K个元素，而不必对所有元素进行排序(最坏的情况下运行时间是O(N lg K))。

实际上，我是在学校里学到的:-)