Le principe sous-jacent de mise en œuvre de l'index mysql

La structure des données et les principes de l'algorithme derrière les index MySQL

1 Définition

Définition de l'index : l'index (index) doit aider MySQL. Être efficace Obtenez la structure des données.
Essence : L'index est une structure de données.

2. B-Tree

B-Tree d'ordre m satisfait aux conditions suivantes :
1. Chaque nœud peut avoir au plus m sous-arbres.
2. Le nœud racine n'a qu'au moins 2 nœuds (ou dans les cas extrêmes, un arbre n'a qu'un seul nœud racine, un organisme unicellulaire est une racine, une feuille et un arbre).
3. Les nœuds non racines et non feuilles ont au moins des sous-arbres Ceil (m/2) (Ceil signifie arrondir, comme un arbre B d'ordre 5, chaque nœud a au moins 3 sous-arbres, c'est-à-dire il y a au moins 3 fourchettes).
4. Les informations dans les nœuds non-feuilles incluent [n,A0,K1,A1,K2,A2,…,Kn,An], où n représente le nombre de mots-clés enregistrés dans le nœud et K est le mot-clé. Et Ki5. Chaque chemin de la racine aux feuilles a la même longueur (les nœuds des feuilles sont dans la même couche)

Caractéristiques du B-Tree :

1. L'ensemble de mots-clés est distribué dans l'arborescence ;
2. Tout mot-clé apparaît et n'apparaît que dans un seul nœud
3. un nœud non-feuille ;
5. Les clés d'un nœud sont disposées de manière non décroissante de gauche à droite
6. Tous les nœuds feuilles ont la même profondeur, qui est égale à la hauteur de l'arbre h.

Le pseudo code de l'algorithme de recherche sur B-Tree est le suivant :

3.

La différence entre B+Tree et B-Tree est :

1. Les nœuds non-feuilles B+Tree ne stockent pas de données, seules les clés 2. sur les nœuds feuilles

3. Chaque nœud feuille contient un pointeur vers le nœud feuille adjacent. L'arbre B+ avec des pointeurs d'accès séquentiels améliore la capacité de recherche d'intervalles

4. et contient uniquement le mot-clé le plus grand (ou le plus petit) dans son sous-arbre (nœud racine



4. Analyse des performances de l'index de l'arborescence B/B+

Base ; : Utilisez le nombre d'E/S de disque pour évaluer la qualité de la structure d'index Données d'échange de mémoire principale et de disque en unités de page Définissez la taille d'un nœud sur une page, de sorte que chaque nœud n'ait besoin que d'une seule E/S. . Entièrement chargé. Selon la définition du B-tree, on peut voir qu'il faut accéder à un maximum de h nœuds pour une récupération

Complexité asymptotique : O(h)=O(logdN)

dmax=floor (pagesize/(keysize+datasize+pointsize) )
Dans les applications pratiques générales, le degré extérieur d est un très grand nombre, généralement supérieur à 100, donc h est très petit (généralement pas plus de 3, et la couche 3 peut stocker environ un million de données)
Une fois dans B-Tree, la récupération nécessite au plus h-1 E/S (mémoire résidente du nœud racine)
Les nœuds de B+Tree ne contiennent pas de champs de données, donc le degré sortant d est plus grand, h est plus petit, le nombre d'E/S est inférieur et l'efficacité est plus élevée, donc B+Tree est plus adapté aux index de stockage externes.


5. Implémentation de l'index MySQL

1. Le moteur MyISAM utilise B+Tree comme structure d'index Le champ de données du nœud feuille stocke l'adresse de l'enregistrement de données ; > MyISAM main Il n'y a pas de différence structurelle entre l'index et l'index auxiliaire, sauf que l'index primaire nécessite que la clé soit unique, tandis que la clé de l'index auxiliaire peut être répétée

2. d'InnoDB lui-même est le fichier d'index et le nœud feuille contient les enregistrements de données complets, cet index est appelé index clusterisé. Étant donné que les fichiers de données d'InnoDB eux-mêmes sont agrégés par clé primaire, InnoDB exige que la table ait une clé primaire (MyISAM peut ne pas en avoir une). Si cela n'est pas explicitement spécifié, le système MySQL sélectionnera automatiquement une colonne qui peut identifier de manière unique la table. enregistrement de données comme clé primaire. Si une telle colonne n'existe pas, MySQL génère automatiquement un champ implicite comme clé primaire pour la table InnoDB.
Le champ de données d'index auxiliaire d'InnoDB stocke la valeur de la clé primaire de l'enregistrement correspondant au lieu de l'adresse
La recherche d'index auxiliaire doit récupérer l'index deux fois : récupérez d'abord l'index auxiliaire pour obtenir la clé primaire, et puis utilisez la clé primaire pour récupérer l'enregistrement dans l'index primaire ;

3. Problème de fractionnement de page

Si la clé primaire augmente de manière monotone, chaque nouvelle. l'enregistrement sera inséré dans la page de manière séquentielle. Lorsque la page est pleine, continuez Insérer dans une nouvelle page

Si les écritures sont dans le désordre, InnoDB doit effectuer des fractionnements de page fréquemment pour allouer de l'espace pour de nouvelles lignes. Le fractionnement des pages entraîne le déplacement de grandes quantités de données ; une insertion nécessite la modification d'au moins trois pages au lieu d'une.

Si les pages sont fréquemment divisées, les pages deviendront clairsemées et remplies de manière irrégulière, de sorte que les données finiront par être fragmentées.

6. Résumé

Comprendre les méthodes de mise en œuvre des index des différents moteurs de stockage est très utile pour une utilisation correcte et l'optimisation des index

1. ce n'est pas recommandé ? Utiliser un champ trop long comme clé primaire ?

2. Pourquoi choisir un champ à incrémentation automatique comme clé primaire ?

3. Pourquoi n'est-il pas recommandé de créer un index pour les champs fréquemment mis à jour ?

4. Pourquoi choisir une colonne hautement différenciée comme index ? La formule de distinction est count(distinct col)/count(*)

5. Utilisez l'index de couverture autant que possible

Optimisez la requête de pagination LIMIT

SELECT * FROM table  where condition LIMIT offset , rows ;

Le mécanisme d'implémentation de l'instruction SQL ci-dessus est :

1. Lisez les enregistrements de ligne offset+rows de la table "table".
2. Abandonnez l'enregistrement de ligne décalé précédent et renvoyez l'enregistrement de ligne des lignes suivantes comme résultat final.
Index couvert :

select  a.id, sid, parent_s_id from cashpool_account_relationship a join (select id from cashpool_account_relationship LIMIT 1000000,10)b on a.id = b.id;
select  id, sid, parent_s_id from cashpool_account_relationship where id >=(select id from cashpool_account_relationship LIMIT 1000000,1) LIMIT 10;

8 Questions et réponses

1. --Ma Xin

InnoDB prend en charge l'index de hachage, mais l'index de hachage qu'il prend en charge est adaptatif. Le moteur de stockage InnoDB générera automatiquement un index de hachage pour la table en fonction de l'utilisation de la table. dans un index.
2. Les nœuds feuilles de l'index de clé primaire InnoDB contiennent des enregistrements de données complets. Le fichier d'index de clé primaire est-il plus grand que le fichier de données ? --Xu Caihou
1). Dans le moteur Innodb, les nœuds feuilles de l'index de clé primaire contiennent des données d'enregistrement et le fichier d'index de clé primaire est le fichier de données.
2). Les données data_length comptées dans la table tables sont la taille de l'index de clé primaire, et index_length est la taille comptée de tous les index auxiliaires (index secondaires) dans cette table.

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!