如何在MongoDB中使用索引進行排序？

Question

我想知道如何使用索引進行排序實際上在MongoDB中有效。 MongoDB文檔中有一個couplearticles，但它們實際上沒有描述排序過程或時間複雜度。一般來說，搜索SO和互聯網並沒有涉及任何相關內容。

假設有集合中的一個文件，查找（）子句b文件相匹配，還有的Ç文件限制返回，一個 >>b >>Ç ，並且c是一些適當的大數字，例如返回的集合不能適應內存 - 比方說1M文檔。

在操作的開始，存在b文件需要進行排序和大小一個爲特徵的文件將被排序的排序樹索引。

我可以想像：

A），以便遍歷索引，並且對於每個遍歷的ObjectID的b文檔列表。返回匹配，直到達到c。這將是O（ab）。 B）作爲A），但首先在文檔中建立對象ID的哈希集合。這是O（a），但需要O（b）內存。

我試着考慮基於遍歷集合b文件排序，但似乎無法拿出任何東西爲O快（b日誌b），這是不優於無索引排序。

我認爲（但也許我錯了），每種不需要索引掃描，那麼排序如何實際工作？

更新：

凱文的答案，並提供鏈接縮小的問題很多，但我想確認/澄清幾點：

1. 據我所知，你不能如果您想避免內存排序，請爲查詢和排序使用不同的索引。當我讀this page它看起來好像你可以（或者至少，它沒有指定一種方式或另一種方式），但這似乎是不正確的。從本質上講，文檔是按照索引順序查找索引的順序進行排序的，因此按索引順序返回。對？
2. 在查詢複合索引時，排序索引必須是複合索引中的第一個索引，但查詢是相等的索引除外。如果不是，則在存儲器中執行排序。對？

3. 如何使用$in或$or查詢進行排序？例如，假設查詢是

   {a: {$in: [4, 6, 2, 1, 3, 10]}, b: {$gt: 1, $lt: 6}}

...並有上依次a和b一個複合索引。排序在a或b的情況下如何處理？ $or更加複雜，因爲據我所知，$or查詢基本上分成多個單獨的查詢。是否$or查詢始終是內存中的排序，至少用於合併單獨查詢的結果？

Answer 1

MongoDB中的索引存儲在B樹結構中，其中每個索引條目指向磁盤上的特定位置。使用B樹結構還意味着MongoDB索引以排序順序存儲，總是按順序遍歷，並且MongoDB通過索引以排序順序獲取一系列文檔很便宜。

A SORT查詢中的階段（即，內存中的排序）限於32MB的內存使用。如果SORT階段超過此限制，則查詢將失敗。這個限制可以通過利用索引的排序性質來回避，這樣MongoDB可以返回一個帶有sort()參數的查詢，而不需要執行內存中的排序。

讓我們假設查詢是形狀的：

db.a.find({b:{$gt:100}, c:{$gt:200}}).sort(...) 

與收集a具有指數：

db.a.createIndex({b:1,c:1}) 

當指定了sort()階段有兩種可能的情況查詢：

1. MongoDB不能使用索引的排序性質，必須執行內存中的SORT階段。

這是如果查詢不能使用「索引前綴」的結果。例如：

db.a.find({b:{$gt:100}, c:{$gt:200}}).sort({c:1}) 

在上面的查詢，索引{b:1,c:1}可用於：具有b大於100用於查詢的{b:{$gt:100}}部

• 匹配的文檔。
• 但是，不能保證返回的文檔按照c排序。

因此，MongoDB別無選擇，只能執行內存中的排序。該查詢的explain()輸出將具有SORT階段。這個SORT階段將被限制到32MB的內存使用。

2. MongoDB可以使用索引的排序性質。

這是結果，如果查詢使用：匹配索引的順序

• 排序鍵和
• 指定相同的順序與索引（即{b:1,c:1}可用於sort({b:1,c:1})指數或sort({b:-1,c:-1})但不sort({b:1,c:-1})）

例如：

db.a.find({b:{$gt:100}, c:{$gt:200}}).sort({b:1}) 

在上面的查詢，索引{b:1,c:1}可用於：具有b大於100用於查詢的{b:{$gt:100}}部

• 匹配的文檔。
• 在這種情況下，MongoDB可以保證返回的文檔按照b排序。

查詢的explain()輸出將不具有SORT階段。另外，explain()輸出的查詢有和沒有sort()是相同的。實質上，我們免費獲得sort()。

瞭解這個問題的有價值的資源是Optimizing MongoDB Compound Indexes。請注意，這篇博文是在2012年寫的。雖然有些術語可能已經過時，但這篇文章的技術性仍然相關。

更新的後續問題

1. MongoDB使用only one index for most queries。因此，例如，爲了避免在內存SORT階段在查詢

   db.a.find({a:1}).sort({b:1}) 
   

   索引必須覆蓋在同一時間都a和b字段;例如需要使用{a:1,b:1}等複合索引。您不能有兩個單獨的索引{a:1}和{b:1}，並且期望將{a:1}索引用於相等部分，並將{b:1}索引用於排序部分。在這種情況下，MongoDB將選擇兩個索引中的一個。

   因此，結果排序是正確的，因爲它們是按照索引的順序查找和返回的。

2. 爲了避免排序使用化合物索引的存儲器內，索引的第一部分必須迎合查詢的平等部分，並且秒部分必須迎合的排序部查詢（如上面（1）的解釋所示）。

   如果你有這樣的查詢：

   db.a.find({}).sort({a:1}) 
   

   指數{a:1,b:1}可用於分類部分（因爲你基本上全部退回集合）。如果您的查詢是這樣的：

   db.a.find({a:1}).sort({b:1}) 
   

   相同指數{a:1,b:1}也可用於查詢的兩個部分。另外：

   db.a.find({a:1,b:1}) 
   

   還可以在這裏的模式使用相同的索引{a:1,b:1}

   注意：find()其次sort()參數按照索引順序{a:1,b:1}。因此，複合指數必須按排序 - >排序。