MongoDB concatène la clé composée d'une manière ou d'une autre et l'utilise comme clé dans un BTree.
Lors de la recherche d'éléments uniques - L'ordre des nœuds dans l'arbre n'a pas d'importance.
Si vous renvoyez une plage de nœuds - Les éléments proches les uns des autres seront en bas des mêmes branches de l'arbre. Plus les nœuds sont proches dans la plage, plus ils peuvent être récupérés rapidement.
Avec un index de champ unique - L'ordre n'aura pas d'importance. S'ils sont proches les uns des autres dans l'ordre croissant, ils le seront également dans l'ordre décroissant.
Lorsque vous avez une clé composée - L'ordre commence à compter.
Par exemple, si la clé est A croissant B croissant, l'index pourrait ressembler à ceci :
Row A B 1 1 1 2 2 6 3 2 7 4 3 4 5 3 5 6 3 6 7 5 1
Une requête pour A croissant B décroissant devra parcourir l'index dans le désordre pour renvoyer les lignes et sera plus lente. Par exemple, il renverra Row 1, 3, 2, 6, 5, 4, 7
Une requête étendue dans le même ordre que l'index renverra simplement les lignes séquentiellement dans le bon ordre.
Trouver un enregistrement dans un BTree prend un temps O(Log(n)). Trouver une plage d'enregistrements dans l'ordre est uniquement OLog(n) + k où k est le nombre d'enregistrements à renvoyer.
Si les enregistrements sont en panne, le coût peut atteindre OLog(n) * k
