Comprendre les index dans MySQL en un seul article

Qu'est-ce qu'un index

Un index est une structure de données dont la fonction est d'améliorer l'efficacité des données ? requête. Une métaphore courante consiste à le comparer au catalogue d’un livre. Grâce à la table des matières, vous pouvez trouver avec précision la page où se trouve le contenu d'un certain chapitre.

En fait, cela ne sert à rien d'utiliser un index lorsque la quantité de données est faible. Même s'il n'y a pas d'index, il ne faut pas beaucoup de temps à l'ordinateur pour parcourir les données une par une. Une fois que la quantité de données est importante, l'indexation est nécessaire pour garantir que nous pouvons fournir des services externes normaux et garantir l'expérience utilisateur.

Type d'index

L'index est une structure de données et il existe plusieurs implémentations pour traiter différents scénarios. Dans MySQL, il s'agit principalement de Hash index et de B+Tree.

Hash Index

Hash Je pense que tout le monde devrait le connaître. Le hachage est une structure de données sous forme de clé-valeur. L'implémentation est généralement une structure tableau + liste chaînée. La fonction de hachage est utilisée pour calculer la position de la clé dans le tableau, puis si un conflit de hachage se produit, il est résolu via la liste chaînée (méthode zipper). Bien entendu, il existe d’autres moyens de résoudre les conflits de hachage. La structure de données du hachage est très couramment utilisée. Par exemple, notre système utilise HashMap pour créer un cache de données de hotspot, et l'efficacité d'accès est très bonne.

La structure de hachage stocke les données. Tout d'abord, la valeur de hachage de la clé est calculée pour déterminer sa position dans le tableau. En cas de conflit, une liste chaînée est construite à la position du tableau. Cela pose évidemment plusieurs problèmes :

Même les positions calculées de touches ayant les mêmes caractéristiques peuvent être très éloignées, rendant les requêtes continues inefficaces. Autrement dit, les requêtes par plage ne sont pas prises en charge.

L'index de hachage stocke la valeur de hachage calculée et le pointeur de ligne, mais ne stocke pas la valeur de ligne spécifique, donc l'interrogation des données via l'index de hachage nécessite deux requêtes (interroger d'abord l'emplacement de la ligne, puis trouver le données spécifiques)

Le principe des données de requête d'index de hachage est de calculer la valeur de hachage, ce qui signifie que la clé doit être une clé qui peut pointer avec précision vers un élément de données, donc faire correspondre des requêtes telles que ne sont pas pris en charge.

Donc, ce que nous pouvons savoir, c'est que l'index de hachage est adapté pour sélectionner rapidement une certaine ligne de données.

B+Structure arborescente

À en juger par le nom, il s'agit évidemment d'une structure arborescente. La structure arborescente est un incontournable dans les manuels de structure de données au collège. La structure arborescente est une structure de données particulièrement importante qui est utilisée à de nombreux endroits.

Nous avons mentionné ci-dessus que les index de hachage ne peuvent pas effectuer de requêtes par plage. Il existe également une structure dans la structure arborescente qui est pratique pour les requêtes ordonnées - un arbre de recherche binaire. La structure de l'arbre de recherche binaire nécessite que la valeur du nœud parent soit supérieure à celle du nœud enfant gauche et inférieure à celle du nœud enfant droit, comme indiqué ci-dessous :

Temps complexité de l'interrogation de l'arbre binaire dans la figure ci-dessus C'est O(log(n)). Bien sûr, pour garantir la complexité temporelle de O(log(n)), nous devons nous assurer que l'arbre binaire reste équilibré à tout moment. .

Bien que la structure arborescente soit également utilisée dans l'index MySQL, ce n'est pas un arbre binaire. Parce que les données de la base de données sont finalement stockées sur le disque, et si l'arborescence comporte trop de nœuds, le transfert entre les nœuds prendra beaucoup de temps. Dans l'implémentation de MySQL, nous choisissons de mettre plus de contenu sur le même nœud et de transférer les opérations sur le même nœud vers la mémoire afin de réduire le nombre de transferts entre les nœuds dans la mémoire externe afin d'atteindre l'objectif d'amélioration de l'efficacité. Il s'agit de B+Tree. Dans la mise en œuvre de B+Tree, une structure arborescente à trois niveaux peut essentiellement répondre à presque tous nos besoins.

Recommandations associées : "Apprentissage des connaissances sur la base de données MySQL"

B-Tree

Pour comprendre B+Tree Tout d'abord, vous devez comprendre que B-Tree est un arbre équilibré. Le B fait ici référence à Balance plutôt qu'à Binaire. Pour être plus précis, B-Tree est un arbre de recherche équilibré à plusieurs voies.

L'arbre de recherche équilibré multi-chemins est le suivant :

Il s'agit d'un arbre 2-3, ce qui signifie que chaque nœud stocke deux valeurs. Le nombre de branches par nœud est de 3. Comme le montre la figure ci-dessus, la structure intermédiaire est très adaptée à l'interrogation de données. La valeur du sous-arbre gauche de chaque nœud est inférieure à la plus petite valeur du nœud actuel, les valeurs du sous-arbre du milieu sont toutes comprises entre les deux valeurs du nœud actuel, et les valeurs du sous-arbre droit sont tous supérieurs à la valeur maximale du nœud actuel.

Par exemple, nous voulons trouver la valeur 24 :

(1) Tout d'abord, jugez à partir du nœud racine que 24 est entre les nœuds racines (15, 25), donc la gauche et les sous-arbres de droite sont exclus et la recherche se fait à partir du milieu.

(2) Recherchez ensuite le nœud racine (18,22) du sous-arbre du milieu. La comparaison révèle que 24 est supérieur à la valeur maximale du nœud, à l'exclusion du sous-arbre de gauche et du sous-arbre du milieu.

(3) Trouvez le bon sous-arbre, jugez que la valeur maximale du nœud est exactement égale à 24, et la requête se termine.

Sur la base du processus ci-dessus, la recherche de B-tree peut être résumée :

(1) À partir du nœud racine, effectuez une recherche binaire sur la séquence de mots-clés (ordonnée) dans le nœud.

(2) Si frappé, terminez, sinon entrez le nœud enfant de la plage à laquelle appartient le mot-clé de requête

(3) Répétez le processus ci-dessus jusqu'à ce que le noeud enfant correspondant soit vide ou soit déjà un noeud feuille

On peut voir que les performances de recherche sont équivalentes à une recherche binaire dans l'ensemble de mots clés ; De là, il semble qu'il n'y ait rien de mal avec B-Tree, mais il convient de noter que chaque nœud de B-Tree stocke la clé d'index et les données de ligne spécifiques qu'il représente. Dans MySQL, les données de chargement de la base de données sont chargées en unités de page et la taille de chaque page est fixe (16 Ko par défaut). Si chaque nœud stocke toutes les valeurs, très peu de nœuds pourront être stockés sur une page et une requête peut charger des données de la mémoire plusieurs fois, ce qui entraînera une réduction des performances.

B+Tree

B+Tree est une variante de B-Tree, le rendant plus adapté à l'indexation de fichiers de stockage externes.

La plus grande différence entre les deux est que chaque nœud de B-Tree stocke toutes les données, tandis que les données qui doivent être stockées dans B+Tree se trouvent toutes sur les nœuds feuilles, et un pointeur d'accès séquentiel est ajouté. , chaque nœud feuille a une adresse pointant vers le nœud feuille adjacent suivant. Cette structure garantit que davantage de nœuds d'index peuvent être stockés dans une seule page mémoire et est plus adaptée aux requêtes de plage.

Index

Étant donné que le moteur de stockage est responsable de l'implémentation de l'index, les index discutés ensuite sont tous basés sur le moteur InnoDB de MySQL.

Index clusterisé

Le clustering signifie que les lignes de données et les clusters de valeurs clés adjacents sont stockés ensemble. Certaines bases de données vous permettent de sélectionner un index spécifique comme index clusterisé, tandis que dans l'implémentation d'InnoDB, l'index de clé primaire est directement désigné comme index clusterisé. Si aucune clé primaire n'est définie, InnoDB choisira un index unique non nul pour remplacer l'index de clé primaire. Si un tel index n'est pas défini, InnoDB définira implicitement une clé primaire comme un index clusterisé (row_id).

Un exemple d'index clusterisé est tel qu'illustré dans la figure :

Index d'index non clusterisé

À l'exclusion la clé primaire dans InnoDB À l'exception de l'index, tout le reste est un index non clusterisé, on l'appelle donc également un index de clé non primaire. Les nœuds feuilles des index de clé non primaire ne stockent pas la valeur d'une ligne, mais la valeur de clé primaire d'une ligne spécifique. La définition du clustering n’est pas remplie.

Un exemple d'index non clusterisé est présenté dans la figure :

La différence entre un index clusterisé et un index non clusterisé dans query

Comme le montrent les deux exemples d'index ci-dessus, si la requête passe par l'index de clé primaire, les lignes de données seront directement interrogées et renvoyées. Cependant, si vous effectuez une requête via un index de clé non primaire, vous devez d'abord déterminer la clé primaire via l'index, puis utiliser la clé primaire obtenue pour trouver les données d'une ligne spécifique à partir de l'index de clé primaire. l'obtention de données à partir de l'index de clé primaire via la clé primaire obtenue est appelée Retour à la table.

Le processus de renvoi de la table rend l'interrogation via un index ordinaire une étape de plus que l'interrogation via un index de clé primaire, et dans de nombreux cas, l'efficacité est relativement faible. Par conséquent, dans notre processus de requête, si les données peuvent être déterminées uniquement par la clé primaire, il est préférable d'effectuer une requête directement à l'aide de la clé primaire.

Index de couverture

Ce qui précède décrit le processus de renvoi de la table via des requêtes à clé non primaire, mais il convient de noter que toutes les requêtes n'ont pas le processus de retour la table. Premièrement, pour un index ordinaire, ses nœuds feuilles stockent la valeur de la clé primaire. Et si les données dont j'ai besoin maintenant sont uniquement la valeur de la clé primaire ? Après avoir obtenu la valeur de la clé primaire via l'index ordinaire, il n'est pas nécessaire de la rechercher dans l'index de la clé primaire, il n'y a donc pas de processus de retour à la table.

Dans l'exemple ci-dessus, l'index de clé non primaire contient déjà la valeur dont nous avons besoin, cet index est donc également appelé index de couverture. L'index de couverture n'est pas une structure fixe. Il peut s'agir d'un index unique (un index sur un champ) ou d'un index composé. Tout ce qui peut fournir directement des résultats de requête sans qu'il soit nécessaire d'effectuer un processus de retour de table peut être appelé un index de couverture.

Souvent, il nous est impossible de déterminer les données uniquement via la clé primaire. L'utilisation d'index ordinaires peut conduire à une inefficacité, c'est pourquoi la couverture des index est également une méthode d'optimisation des performances très courante dans le processus de développement quotidien.

Bien sûr, il n'est pas toujours bon de couvrir les pages d'index. Par exemple, j'ai maintenant créé un index index(a,b). L'avantage d'établir un index à l'aide de deux champs, a et b, est que la table ne sera pas renvoyée lors de l'interrogation du champ ab. Cependant, si vous interrogez uniquement via le champ b, vous ne pouvez pas utiliser cet index. Les éléments d'index de l'index créé sont triés selon l'ordre des champs apparaissant dans la définition de l'index.

Principe du préfixe le plus à gauche

Supposons qu'il existe un index d'index (a, b), alors si vous interrogez via a et b, l'index peut être appliqué, utilisez a seul à La requête peut également être appliquée à l'index, mais si vous utilisez b seul pour interroger, elle ne peut pas être appliquée à l'index. C'est le principe du préfixe le plus à gauche. Lors de la correspondance de l'index, les n champs les plus à gauche de l'index seront mis en correspondance. S'ils peuvent correspondre, l'index peut être appliqué.

En raison de l'existence du principe du préfixe le plus à gauche, nous devrons peut-être prendre en compte davantage de choses lors de la création d'un index.

Tout d'abord, vous devez être clair sur le fait qu'un index est une structure de données. Lors de l'établissement d'un index, l'espace de stockage est consommé. Par conséquent, plus il y a d'index, mieux c'est. les indices doivent être réduits autant que possible en fonction des besoins.

L'existence du principe du préfixe le plus à gauche permet d'utiliser un index conjoint comme plusieurs index. Bien entendu, le principe est que l'ordre des champs dans l'index est conçu (en fait, le principe du préfixe le plus à gauche est. non seulement applicable à l'index Union, également utilisé pour l'index de chaîne, les n caractères les plus à gauche de l'index de chaîne sont équivalents aux n champs les plus à gauche de l'index union).

Par exemple, index(a,b), avec cet index, nous n'avons pas besoin de créer un index séparé pour a, donc lors de la conception d'un index conjoint, nous mettons généralement en premier les champs avec une fréquence d'utilisation plus élevée. .

Déplacez ensuite les champs avec une discrimination plus élevée vers l'avant. La discrimination est le taux de répétition des valeurs dans le champ. Plus le taux de répétition est faible, plus la discrimination est élevée. Par exemple, le sexe ne convient pas comme index. Les champs avec une distinction plus élevée peuvent filtrer davantage de lignes après un seul filtre.

Ensuite, ce qu'il faut considérer, c'est la taille du champ. Puisque l'index doit également occuper de l'espace, des champs plus petits sont généralement sélectionnés.

Documents de référence

Référence interne sur l'exploitation et la maintenance de MySQL : MySQL, Galera, principes fondamentaux et bonnes pratiques d'Inception

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!