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

Question

根據answer和MongoDB文檔，我瞭解到，當使用limit（）時，MongoDB能夠排序大型數據集並提供排序結果。 但是，如果使用sort（）查詢相同的數據集，則會導致內存異常。

從上面的帖子中的第二個答案，海報提到整個集合被掃描，排序並返回前N個結果。我想知道當我使用limit（）時集合是如何排序的。 從文檔中我發現，當使用limit（）時，它會進行Top-K排序，但是對於它的任何地方都沒有太多解釋。我希望看到有關Top-K排序算法的任何參考。

Answer 1

一般來說，你可以做一個有效的top-K排序，大小爲K的最小堆。最小堆表示迄今爲止在數據集中看到的最大K個元素。它還使您可以隨時訪問這些頂級K元素中的最小元素。

在掃描數據集時，如果給定的元素大於最小堆中的最小元素（即迄今爲止最大的最小K值最小的元素），則用最小堆代替最小堆中的最小值該元素和重新heapify（O(lg K)）。

最後，您只剩下整個數據集的前K個元素，而不必將它們全部排序（最差情況下的運行時間爲O(N lg K)），僅使用Θ(K)內存。

我實際上在學校學到了這個變化:-)