Comment fonctionnent les index MySQL?

Je suis vraiment intéressé par le fonctionnement des index MySQL, plus précisément, comment peuvent-ils renvoyer les données demandées sans scanner toute la table?

C'est hors sujet, je sais, mais s'il y a quelqu'un qui pourrait m'expliquer cela en détail, je serais très, très reconnaissant.

Fondamentalement, un index sur une table fonctionne comme un index dans un livre (c'est de là que vient le nom):

Disons que vous avez un livre sur les bases de données et que vous souhaitez trouver des informations sur, disons, le stockage. Sans index (en supposant qu'aucune autre aide, telle qu'une table des matières), vous devriez parcourir les pages une par une, jusqu'à ce que vous trouviez le sujet (c'est un full table scan). D'un autre côté, un index a une liste de mots-clés, vous devriez donc consulter l'index et voir ce qui storageest mentionné aux pages 113-120,231 et 354. Ensuite, vous pouvez retourner directement à ces pages, sans rechercher (c'est une recherche avec un index, un peu plus rapide).

Bien sûr, l'utilité de l'index dépend de beaucoup de choses - quelques exemples, en utilisant la comparaison ci-dessus:

• si vous aviez un livre sur les bases de données et indexiez le mot "base de données", vous verriez qu'il est mentionné aux pages 1-59,61-290 et 292 à 400. Dans ce cas, l'index n'est pas d'une grande aide et il pourrait être plus rapide pour parcourir les pages une par une (dans une base de données, c'est une "mauvaise sélectivité").
• Pour un livre de 10 pages, cela n'a aucun sens de faire un index, car vous pouvez vous retrouver avec un livre de 10 pages préfixé par un index de 5 pages, ce qui est tout simplement stupide - il suffit de numériser les 10 pages et d'en finir avec .
• L'index doit également être utile - il est généralement inutile d'indexer par exemple la fréquence de la lettre "L" par page.

La première chose que vous devez savoir est que les index sont un moyen d'éviter d'analyser la table complète pour obtenir le résultat que vous recherchez.

Il existe différents types d'index et ils sont implémentés dans la couche de stockage, il n'y a donc pas de norme entre eux et ils dépendent également du moteur de stockage que vous utilisez.

InnoDB et l'indice B + Tree

Pour InnoDB, le type d'index le plus courant est l'index B + Tree, qui stocke les éléments dans un ordre trié. De plus, vous n'avez pas besoin d'accéder à la vraie table pour obtenir les valeurs indexées, ce qui accélère considérablement le retour de votre requête.

Le "problème" de ce type d'index est que vous devez rechercher la valeur la plus à gauche pour utiliser l'index. Par conséquent, si votre index comporte deux colonnes, par exemple nom_prénom et prénom, l'ordre dans lequel vous interrogez ces champs est très important .

Donc, étant donné le tableau suivant:

CREATE TABLE person (
    last_name VARCHAR(50) NOT NULL,
    first_name VARCHAR(50) NOT NULL,
    INDEX (last_name, first_name)
);

Cette requête profiterait de l'index:

SELECT last_name, first_name FROM person
WHERE last_name = "John" AND first_name LIKE "J%"

Mais le suivant ne serait pas

SELECT last_name, first_name FROM person WHERE first_name = "Constantine"

Parce que vous interrogez la first_namecolonne en premier et que ce n'est pas la colonne la plus à gauche de l'index.

Ce dernier exemple est encore pire:

SELECT last_name, first_name FROM person WHERE first_name LIKE "%Constantine"

Parce que maintenant, vous comparez la partie la plus à droite du champ le plus à droite dans l'index.

L'index de hachage

Il s'agit d'un type d'index différent que, malheureusement, seul le backend mémoire prend en charge. Il est rapide comme l'éclair mais utile uniquement pour les recherches complètes, ce qui signifie que vous ne pouvez pas l'utiliser pour des opérations telles que >, <ou LIKE.

Comme il ne fonctionne que pour le backend mémoire, vous ne l'utiliserez probablement pas très souvent. Le cas principal auquel je peux penser en ce moment est celui où vous créez une table temporaire dans la mémoire avec un ensemble de résultats d'une autre sélection et effectuez beaucoup d'autres sélections dans cette table temporaire en utilisant des index de hachage.

Si vous avez un grand VARCHARchamp, vous pouvez "émuler" l'utilisation d'un index de hachage lorsque vous utilisez un arbre B, en créant une autre colonne et en y enregistrant un hachage de grande valeur. Disons que vous stockez une URL dans un champ et que les valeurs sont assez grandes. Vous pouvez également créer un champ entier appelé url_hashet utiliser une fonction de hachage comme CRC32ou toute autre fonction de hachage pour hacher l'URL lors de son insertion. Et puis, lorsque vous devez rechercher cette valeur, vous pouvez faire quelque chose comme ceci:

SELECT url FROM url_table WHERE url_hash=CRC32("http://gnu.org");

Le problème avec l'exemple ci-dessus est que, puisque la CRC32fonction génère un hachage assez petit, vous vous retrouverez avec beaucoup de collisions dans les valeurs hachées. Si vous avez besoin de valeurs exactes, vous pouvez résoudre ce problème en procédant comme suit:

SELECT url FROM url_table 
WHERE url_hash=CRC32("http://gnu.org") AND url="http://gnu.org";

Il vaut toujours la peine de hacher les choses même si le nombre de collisions est élevé, car vous n'effectuerez que la deuxième comparaison (la chaîne) avec les hachages répétés.

Malheureusement, en utilisant cette technique, vous devez toujours frapper la table pour comparer le urlchamp.

Emballer

Quelques faits que vous pouvez considérer chaque fois que vous souhaitez parler d'optimisation:

1. La comparaison d'entiers est bien plus rapide que la comparaison de chaînes. Il peut être illustré par l'exemple de l'émulation de l'indice de hachage dans InnoDB.

2. Peut-être que l'ajout d'étapes supplémentaires dans un processus le rend plus rapide et non plus lent. Cela peut être illustré par le fait que vous pouvez optimiser un SELECTen le divisant en deux étapes, en faisant que la première stocke des valeurs dans une table en mémoire nouvellement créée, puis en exécutant les requêtes plus lourdes sur cette deuxième table.

MySQL a aussi d'autres index, mais je pense que l'arbre B + est le plus utilisé de tous les temps et celui de hachage est une bonne chose à savoir, mais vous pouvez trouver les autres dans la documentation MySQL .

Je vous recommande fortement de lire le livre "High Performance MySQL", la réponse ci-dessus était définitivement basée sur son chapitre sur les index.

Fondamentalement, un index est une carte de toutes vos clés qui est triée dans l'ordre. Avec une liste dans l'ordre, puis au lieu de vérifier chaque clé, il peut faire quelque chose comme ceci:

1: Aller au milieu de la liste - est-il supérieur ou inférieur à ce que je recherche?

2: Si plus haut, allez à mi-chemin entre le milieu et le bas, si bas, moyen et haut

3: Est-il supérieur ou inférieur? Aller à nouveau au milieu, etc.

En utilisant cette logique, vous pouvez trouver un élément dans une liste triée en environ 7 étapes, au lieu de vérifier chaque élément.

Évidemment, il y a des complexités, mais cela vous donne l'idée de base.

Jetez un œil à ce lien: http://dev.mysql.com/doc/refman/5.0/en/mysql-indexes.html

La façon dont ils fonctionnent est trop vaste pour être abordée dans un seul message SO.

Voici l' une des meilleures explications des index que j'ai vues. Malheureusement, c'est pour SQL Server et non MySQL. Je ne sais pas à quel point les deux sont similaires ...

Regardez ces vidéos pour plus de détails sur l'indexation

Indexation simple Vous pouvez créer un index unique sur une table. Un index unique signifie que deux lignes ne peuvent pas avoir la même valeur d'index. Voici la syntaxe pour créer un index sur une table

CREATE UNIQUE INDEX index_name
ON table_name ( column1, column2,...);

Vous pouvez utiliser une ou plusieurs colonnes pour créer un index. Par exemple, nous pouvons créer un index sur l' tutorials_tblutilisation de tutorial_author.

CREATE UNIQUE INDEX AUTHOR_INDEX
ON tutorials_tbl (tutorial_author)

Vous pouvez créer un index simple sur une table. Omettez simplement le mot-clé UNIQUE de la requête pour créer un index simple. Un index simple permet de dupliquer des valeurs dans une table.

Si vous souhaitez indexer les valeurs d'une colonne dans l'ordre décroissant, vous pouvez ajouter le mot réservé DESC après le nom de la colonne.

mysql> CREATE UNIQUE INDEX AUTHOR_INDEX
ON tutorials_tbl (tutorial_author DESC)

Je veux ajouter mes 2 cents. Je suis loin d'être un expert en bases de données, mais j'ai récemment lu un peu sur ce sujet; assez pour moi d'essayer de donner un ELI5. Alors, voici l'explication du profane.

Je le comprends comme tel qu'un index est comme un mini-miroir de votre table, un peu comme un tableau associatif. Si vous l'alimentez avec une clé correspondante, vous pouvez simplement passer à cette ligne dans une "commande".

Mais si vous n'aviez pas cet index / tableau, l'interpréteur de requêtes doit utiliser une boucle for pour parcourir toutes les lignes et rechercher une correspondance (l'analyse complète de la table).

Avoir un index a «l'inconvénient» du stockage supplémentaire (pour ce mini-miroir), en échange de «l'avantage» de rechercher du contenu plus rapidement.

Notez que (en fonction de votre moteur de base de données) la création de clés primaires, étrangères ou uniques configure également automatiquement un index respectif. Ce même principe est essentiellement pourquoi et comment ces clés fonctionnent.

Ajout d'une représentation visuelle à la liste des réponses.

MySQL utilise une couche supplémentaire d'indirection: les enregistrements d'index secondaire pointent vers les enregistrements d'index principal et l'index principal lui-même contient les emplacements de ligne sur le disque. Si un décalage de ligne change, seul l'index principal doit être mis à jour.

Mise en garde: la structure des données du disque semble plate dans le diagramme mais est en réalité une arborescence B +.

Source: lien

Dans MySQL InnoDB, il existe deux types d'index.

1. Clé primaire appelée index clusterisé. Les mots-clés d'index sont stockés avec des données d'enregistrement réelles dans le nœud feuille B + Tree.

2. Clé secondaire qui est un index non clusterisé. Ces index stockent uniquement les mots clés de la clé primaire avec leurs propres mots clés d'index dans le nœud feuille B + Tree. Ainsi, lors de la recherche à partir d'un index secondaire, il trouvera d'abord ses mots clés d'index de clé primaire et analysera l'arborescence B + de la clé primaire pour trouver les enregistrements de données réels. Cela rendra l'index secondaire plus lent que la recherche d'index primaire. Cependant, si les selectcolonnes sont toutes dans l'index secondaire, il n'est pas nécessaire de rechercher à nouveau l'index principal B + Tree. C'est ce qu'on appelle l'indice de couverture.