pourquoi l'ajout d'un index sur un élément que vous triez diminue-t-il la quantité de travail de tri ?

Question

D'ici : http://dev.mysql.com/doc/refman/5.0/en/order-by-optimization.html

In some cases, MySQL can use an index to satisfy an ORDER BY clause without doing any extra sorting.

Je pensais que les index aidaient à récupérer des éléments de données spécifiques (comme les index dans les tableaux), ce qui donne un résultat de O(1) au lieu de O(n) lorsqu'ils sont indexés. Mais lors du tri, je supposais qu'ils utilisaient un algorithme O(nlogn) ou autre basé sur la colonne de tri, mais apparemment l'indexation des colonnes par lesquelles vous triez peut diminuer la quantité de travail impliquée.

Comment cela fonctionne-t-il ? (Je ne suis pas sûr qu'il s'agisse d'un problème SQL général ou d'un problème MySQL).

Answer 1

Une réponse simple : En général, les index sont eux-mêmes stockés dans un ordre trié (sinon, l'utilisation d'un index pour trouver rapidement un enregistrement serait extrêmement difficile). Par conséquent, "dans certains cas" (lorsqu'un ORDER BY correspond à l'ordre de tri d'un index), les données peuvent être renvoyées via l'ordre de l'index, "sans effectuer de tri supplémentaire".

Plus loin : Comme me l'a rappelé la réponse de @Will A, vous pouvez vous renseigner sur indices de couverture qui étendent ce concept.

Answer 2

La consultation d'une seule ligne dans un index est probablement une opération en O(log n) ou à peu près.

Cependant, lorsque vous lisez un index dans un "ordre de tri", vous effectuez généralement une traversée d'arbre ou même de liste, et cela sera O(n). Si l'index contient toutes les informations nécessaires pour satisfaire le résultat de la requête, cela sera considérablement plus rapide que de lire et trier les données.

Il s'agit d'un problème SQL général, non spécifique à MySQL.