Come funziona l'ordinamento con un indice in MongoDB?

Gli indici in MongoDB sono archiviati in una struttura ad albero B, in cui ogni voce di indice punta a una posizione specifica sul disco. L'uso di una struttura ad albero B significa anche che un indice MongoDB è archiviato in un ordine ordinato, sempre attraversato in ordine, ed è economico per MongoDB recuperare una serie di documenti in un ordine ordinato tramite indici.

Aggiorna :La struttura B-tree è vera per il motore di archiviazione MMAPv1, ma è implementata in modo leggermente diverso dal motore di archiviazione WiredTiger (impostazione predefinita da MongoDB 3.2). L'idea di base rimane la stessa, dove è economico attraversare l'indice in ordine.

Un SORT fase (cioè l'ordinamento in memoria) in una query è limitato a 32 MB di memoria utilizzata. Una query avrà esito negativo se SORT stadio supera questo limite. Questo limite può essere aggirato utilizzando la natura ordinata degli indici, in modo che MongoDB possa restituire una query con un sort() parametro senza eseguire un ordinamento in memoria.

Assumiamo che la query abbia la forma:

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

con collezione a avente un indice di:

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

Ci sono due possibili scenari quando un sort() stage è specificato nella query:

1. MongoDB non può utilizzare la natura ordinata dell'indice e deve eseguire un SORT in memoria fase .

Questo è il risultato se la query non può utilizzare il "prefisso indice". Ad esempio:

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

Nella query precedente, l'indice {b:1,c:1} può essere utilizzato per:

Abbina documenti con b maggiore di 100 per {b:{$gt:100}} parte della query.
Tuttavia, non vi è alcuna garanzia che i documenti restituiti siano ordinati in termini di c .

Pertanto, MongoDB non ha altra scelta che eseguire un ordinamento in memoria. Il explain() l'output di questa query avrà un SORT fase. Questo SORT fase sarebbe limitato a 32 MB di memoria utilizzata.

2. MongoDB può utilizzare la natura ordinata dell'indice .

Questo è il risultato se la query utilizza:

Chiavi di ordinamento che corrispondono all'ordine dell'indice e
Specifica lo stesso ordinamento dell'indice (ovvero l'indice {b:1,c:1} può essere utilizzato per sort({b:1,c:1}) o sort({b:-1,c:-1}) ma non sort({b:1,c:-1}) )

Ad esempio:

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

Nella query precedente, l'indice {b:1,c:1} può essere utilizzato per:

Abbina documenti con b maggiore di 100 per {b:{$gt:100}} parte della query.
In questo caso, MongoDB può garantire che i documenti restituiti siano ordinati in termini di b .

Il explain() l'output della query precedente non avere un SORT fase. Inoltre, il explain() output della query con e senza sort() sono identici . In sostanza, stiamo ottenendo il sort() gratis.

Una risorsa utile per comprendere questo argomento è l'ottimizzazione degli indici composti MongoDB. Tieni presente che questo post del blog è stato scritto nel lontano 2012. Sebbene parte della terminologia possa essere obsoleta, la tecnicità del post è ancora rilevante.

Aggiornamento sulle domande di follow-up

MongoDB utilizza un solo indice per la maggior parte delle query. Ad esempio, per evitare un SORT in memoria fase della query
```
db.a.find({a:1}).sort({b:1})
```
l'indice deve coprire entrambi a e b campi contemporaneamente; per esempio. un indice composto come {a:1,b:1} è obbligatorio. Non puoi avere due indici separati {a:1} e {b:1} e aspettati il {a:1} index da utilizzare per la parte di uguaglianza e il {b:1} indice da utilizzare per la parte di ordinamento. In questo caso, MongoDB sceglierà uno dei due indici.

Pertanto, è corretto che i risultati vengano ordinati perché vengono cercati e restituiti nell'ordine dell'indice.
Per evitare di avere un ordinamento in memoria utilizzando un indice composto, la prima parte dell'indice deve soddisfare la parte di uguaglianza della query e la seconda parte deve soddisfare la parte di ordinamento della query (come mostrato nella spiegazione di (1) sopra).

Se hai una domanda come questa:
```
db.a.find({}).sort({a:1})
```
l'indice {a:1,b:1} può essere utilizzato per la parte di ordinamento (dal momento che stai praticamente restituendo l'intera raccolta). E se la tua richiesta è simile a questa:
```
db.a.find({a:1}).sort({b:1})
```
lo stesso indice {a:1,b:1} può essere utilizzato anche per entrambe le parti della query. Inoltre:
```
db.a.find({a:1,b:1})
```
può anche utilizzare lo stesso indice {a:1,b:1}

Nota lo schema qui:find() seguito da sort() i parametri seguono l'ordine dell'indice {a:1,b:1} . Pertanto un indice composto deve essere ordinato per uguaglianza -> ordinamento .

Aggiornamento relativo all'ordinamento di diversi tipi

Se un campo ha tipi diversi tra i documenti (ad es. se a è stringa in un documento, numero in altri, booleano in un altro), come procede l'ordinamento?

La risposta è l'ordine di confronto del tipo MongoDB BSON. Per parafrasare la pagina di manuale, l'ordine è:

MinKey (tipo interno)
Nulla
Numeri (int, long, double, decimali)
Simbolo, Stringa
Oggetto
Matrice
BinData
ID oggetto
Booleano
Data
Data e ora
Espressione regolare
MaxKey (tipo interno)

Quindi dall'esempio sopra usando l'ordine crescente, appariranno prima i documenti contenenti numeri, poi le stringhe, quindi il booleano.