Comment fonctionne le tri avec un index dans MongoDB ?

Les index dans MongoDB sont stockés dans une structure arborescente B, où chaque entrée d'index pointe vers un emplacement spécifique sur le disque. L'utilisation d'une structure arborescente signifie également qu'un index MongoDB est stocké dans un ordre trié, toujours parcouru dans l'ordre, et qu'il est peu coûteux pour MongoDB de récupérer une série de documents dans un ordre trié via des index.

Mettre à jour :La structure B-tree est vraie pour le moteur de stockage MMAPv1, mais est implémentée légèrement différemment par le moteur de stockage WiredTiger (par défaut depuis MongoDB 3.2). L'idée de base reste la même, où il est bon marché de parcourir l'index dans un ordre trié.

Un SORT l'étape (c'est-à-dire le tri en mémoire) dans une requête est limitée à 32 Mo d'utilisation de la mémoire. Une requête échouera si le SORT dépasse cette limite. Cette limite peut être contournée en utilisant la nature triée des index, afin que MongoDB puisse renvoyer une requête avec un sort() paramètre sans effectuer de tri en mémoire.

Supposons que la requête est de la forme :

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

avec la collection a ayant un index de :

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

Il existe deux scénarios possibles lorsqu'un sort() l'étape est spécifiée dans la requête :

1. MongoDB ne peut pas utiliser la nature triée de l'index et doit effectuer un SORT en mémoire scène .

C'est le résultat si la requête ne peut pas utiliser le "préfixe d'index". Par exemple :

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

Dans la requête ci-dessus, l'index {b:1,c:1} peut être utilisé pour :

Reconnaître les documents ayant b supérieur à 100 pour le {b:{$gt:100}} partie de la requête.
Cependant, il n'y a aucune garantie que les documents renvoyés soient triés en termes de c .

Par conséquent, MongoDB n'a d'autre choix que d'effectuer un tri en mémoire. Le explain() la sortie de cette requête aura un SORT organiser. Ce SORT l'étape serait limitée à 32 Mo d'utilisation de la mémoire.

2. MongoDB peut utiliser la nature triée de l'index .

Voici le résultat si la requête utilise :

Trier les clés qui correspondent à l'ordre de l'index, et
Spécifie le même ordre que l'index (c'est-à-dire l'index {b:1,c:1} peut être utilisé pour sort({b:1,c:1}) ou sort({b:-1,c:-1}) mais pas sort({b:1,c:-1}) )

Par exemple :

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

Dans la requête ci-dessus, l'index {b:1,c:1} peut être utilisé pour :

Reconnaître les documents ayant b supérieur à 100 pour le {b:{$gt:100}} partie de la requête.
Dans ce cas, MongoDB peut garantir que les documents renvoyés sont triés en termes de b .

Le explain() la sortie de la requête ci-dessus ne sera pas avoir un SORT organiser. Aussi, le explain() sortie de la requête avec et sans sort() sont identiques . Essentiellement, nous obtenons le sort() gratuitement.

Une ressource intéressante pour comprendre ce sujet est Optimisation des index composés MongoDB. Veuillez noter que cet article de blog a été rédigé en 2012. Bien qu'une partie de la terminologie puisse être obsolète, la technicité de l'article est toujours pertinente.

Mise à jour sur les questions de suivi

MongoDB utilise un seul index pour la plupart des requêtes. Ainsi, par exemple, pour éviter un SORT en mémoire étape dans la requête
```
db.a.find({a:1}).sort({b:1})
```
l'index doit couvrir à la fois a et b champs en même temps; par exemple. un index composé tel que {a:1,b:1} est requis. Vous ne pouvez pas avoir deux index distincts {a:1} et {b:1} , et attendez le {a:1} index à utiliser pour la partie égalité, et le {b:1} index à utiliser pour la partie tri. Dans ce cas, MongoDB choisira l'un des deux index.

Par conséquent, il est correct que les résultats soient triés car ils sont recherchés et renvoyés dans l'ordre de l'index.
Pour éviter d'avoir un tri en mémoire utilisant un index composé, la première partie de l'index doit répondre à la partie égalité de la requête, et la seconde partie doit répondre à la partie tri de la requête (comme indiqué dans l'explication de (1) ci-dessus).

Si vous avez une requête comme celle-ci :
```
db.a.find({}).sort({a:1})
```
l'indice {a:1,b:1} peut être utilisé pour la partie tri (puisque vous renvoyez essentiellement toute la collection). Et si votre requête ressemble à ceci :
```
db.a.find({a:1}).sort({b:1})
```
le même index {a:1,b:1} peut également être utilisé pour les deux parties de la requête. Aussi :
```
db.a.find({a:1,b:1})
```
peut également utiliser le même index {a:1,b:1}

Remarquez le modèle ici :le find() suivi de sort() les paramètres suivent l'ordre d'indexation {a:1,b:1} . Par conséquent, un index composé doit être ordonné par égalité -> tri .

Mise à jour concernant le tri des différents types

Si un champ a des types différents entre les documents (par exemple, si a est une chaîne dans un document, un nombre dans d'autres, un booléen dans un autre), comment se déroule le tri ?

La réponse est l'ordre de comparaison de type MongoDB BSON. Pour paraphraser la page de manuel, l'ordre est :

MinKey (type interne)
Nul
Nombres (entiers, longs, doubles, décimaux)
Symbole, Chaîne
Objet
Tableau
BinData
ObjectId
Booléen
Date
Horodatage
Expression régulière
MaxKey (type interne)

Ainsi, à partir de l'exemple ci-dessus utilisant l'ordre croissant, les documents contenant des nombres apparaîtront en premier, puis des chaînes, puis des booléens.