MongoDBでTop-Kソートアルゴリズムがどのように機能するのですか

Question

answerとMongoDBドキュメントに基づいて、MongoDBは大きなデータセットをソートし、limit（）を使用するとソート結果を提供できることを理解しました。 しかし、sort（）を使用して同じデータセットを照会すると、メモリ例外が発生します。

上記の2番目の回答から、全体のコレクションがスキャンされ、ソートされ、上位Nの結果が返されることがポスターに記載されています。私は、limit（）を使うとコレクションがどのようにソートされるのか知りたいです。 私は、limit（）が使用されているときにTop-Kソートを行っていることがわかりましたが、どこでもそれについての説明はあまりありません。 Top-K Sortアルゴリズムに関する参考文献をご覧になりたい。

Answer 1

一般に、サイズKの最小ヒープを使用して効率的なトップKソートを実行できます。最小ヒープは、データセットでこれまでに見られた最大のK要素を表します。また、これらの上位K要素の最小要素に一定時間アクセスできます。

データセットをスキャンするとき、特定の要素がmin-heapの最小要素（これまでの最大の上位Kの最小の要素）より大きい場合、min-heapから最小のものをその要素と再heapify（O(lg K)）。

最後に、メモリのみを使用して、すべてのデータをソートしなくても（最悪の場合の実行時間はO(N lg K)）、データセット全体の上位K個の要素が残っています。

私は実際に私はMongoDBのがトップ-Kのソートを行い、具体的方法を知らないことを