Structure de données d'index MySQL

1. Avant-propos :

Dans nos vies, nous exportons des applications qui peuvent voir l'effet d'index, comme les horaires de train consultés dans les gares, les annuaires de dictionnaires, etc. Leur fonction est celle des index. Ils filtrent les résultats finaux souhaités en réduisant continuellement la portée des données à obtenir, et en même temps transforment les événements aléatoires en événements séquentiels, c'est-à-dire que nous utilisons toujours la même méthode de recherche pour verrouiller. Données (recherche A-Z du dictionnaire).

Exemple de vie - prendre un train : je vais prendre un train pour rentrer dans ma ville natale S'il n'y a pas d'horaire de train quand je veux prendre le train, le pire résultat est que je dois me rendre à tous les trains. m'arrêter pour trouver le train que je veux prendre ; mais il y en a. Avec les horaires, je peux savoir rapidement où s'arrête le train que je veux prendre, et je peux m'y rendre directement au lieu d'y aller un par un pour voir si le train que je veux prendre est aller, accélérant ainsi ma visite. Cet horaire de train est l'index de la base de données.

2. Principe du disque :

Cette partie contient beaucoup de texte et de théorie, et c'est un casse-tête à lire. Vous pouvez la lire si vous l'avez. êtes intéressé. Peu importe si vous n'êtes pas intéressé. Lorsque vous lisez les chapitres suivants, rappelez-vous simplement une conclusion de cette partie :

Lisez les données autant que possible [réduisez le nombre d'interactions d'E/S. avec le système d'exploitation].

D'accord, si vous n'êtes pas intéressé, vous pouvez l'ignorer et passer à la partie suivante.

La mise en œuvre de la base de données est relativement complexe. Les données sont stockées sur le disque. Afin d'améliorer les performances, une partie des données peut être lue en mémoire pour être calculée à chaque fois, car on connaît le coût d'accès. le disque est environ 100 000 fois celui de l'accès à la mémoire, donc un simple arbre de recherche est difficile à répondre à des scénarios d'application complexes. L'accès au disque a été mentionné plus tôt, voici donc une brève introduction aux E/S du disque et à la pré-lecture. La lecture des données à partir du disque repose sur un mouvement mécanique. Le temps passé à chaque lecture de données peut être divisé en trois catégories : temps de recherche et délai de rotation. , et le temps de transmission. Partie,
a)·Temps de recherche : Le temps nécessaire au bras magnétique pour se déplacer vers la piste spécifiée est généralement inférieur à 5 ms. b) Délai de rotation : C'est la vitesse du disque que nous entendons souvent. environ, comme 7 200 tr/min pour un disque. Cela signifie qu'il peut tourner 7 200 fois par minute, ce qui signifie qu'il peut tourner 120 fois par seconde, et le délai de rotation est de 1/120/2 = 4,17 ms ; fait référence à la lecture du disque ou à l'écriture de données sur le disque. Le temps est généralement de quelques dixièmes de milliseconde, ce qui est négligeable par rapport aux deux premières fois.
(J'ai lu un article très détaillé : http://wdxtub.com/2016/04/16/thin-csapp-3/)

Ensuite, le temps qu'il faut pour accéder à un disque est un disque IO Le temps est approximativement égal à 5 ​​4,17 = 9 ms, ce qui semble plutôt bien, mais il faut savoir qu'une machine à 500 MIPS (Million Instructions Per Second) peut exécuter 500 millions d'instructions par seconde, car les instructions dépendent de la nature de Autrement dit, 400 000 instructions peuvent être exécutées dans le temps nécessaire à l'exécution d'une IO. La base de données contient souvent des centaines de milliers, des millions voire des dizaines de millions de données. Chaque fois que cela prend 9 millisecondes, c'est évidemment un désastre. .

Donc, conclusion : réduisez le nombre d’interactions E/S du système d’exploitation.

(Nous appelons les données lues par IO à chaque fois une page. La taille spécifique des données sur une page dépend du système d'exploitation, généralement 4k ou 8k, c'est-à-dire que nous lisons les données dans une page. Quand les données sont générées, une seule IO se produit réellement)

3. Qu'est-ce qu'un index :

Lors de l'utilisation du système de base de données, la requête de données est l'opération de données la plus fréquemment utilisée.

L'algorithme de requête le plus basique est bien sûr la recherche linéaire. Il parcourt la table puis fait correspondre ligne par ligne si la valeur de la ligne est égale au mot-clé à trouver. Sa complexité temporelle est O(n). Cependant, les algorithmes avec une complexité temporelle de O(n) peuvent également atteindre de bonnes performances avec de petites tables et des bases de données peu chargées. Mais lorsque les données augmentent, l'algorithme avec une complexité temporelle de O(n) est évidemment mauvais et les performances chutent rapidement.

Heureusement, le développement de l'informatique a fourni de nombreux meilleurs algorithmes de recherche, tels que la recherche binaire et la recherche binaire. recherche arborescente), etc. Si vous faites une petite analyse, vous constaterez que chaque algorithme de recherche ne peut être appliqué qu'à des structures de données spécifiques. Par exemple, la recherche binaire nécessite que les données récupérées soient ordonnées, tandis que la recherche par arbre binaire ne peut être appliquée qu'aux arbres de recherche binaires, mais. les données elles-mêmes La structure organisationnelle ne peut pas satisfaire complètement diverses structures de données (par exemple, il est théoriquement impossible d'organiser les deux colonnes dans l'ordre en même temps), donc en plus des données, le système de base de données maintient également des structures de données qui satisfont une recherche spécifique Les structures font référence (pointent vers) les données d'une manière ou d'une autre, ce qui permet d'implémenter des algorithmes de recherche avancés sur ces structures de données. Cette structure de données est un index.

4. L'index B-Tree de MySQL (techniquement B Tree)

D'accord, voici le cœur de cet article !

Dans MySQL, il existe quatre principaux types d'index, à savoir : l'index B-Tree, l'index Hash, l'index Fulltext et l'index R-Tree. Nous analysons principalement les indices B-Tree. (B : équilibre signifie équilibre, pas arbre binaire)

1 Explication détaillée de la structure des données de l'arbre b

.

L'image ci-dessus est un arbre b (sous le moteur innodb, la structure de B sous le moteur myisam est différente. Pour parler franchement, c'est la différence entre un index clusterisé et un index non clusterisé. Pour plus de détails, voir :

Mysql-Clustered Index

Le bloc bleu clair est appelé un bloc de disque. Vous pouvez voir que chaque bloc de disque contient plusieurs éléments de données (affichés en bleu foncé, plage : [(M/ 2). )-1, M-1] M représente le total des données) et des pointeurs (affichés en jaune). Par exemple, le bloc de disque 1 contient les éléments de données 17 et 35, y compris les pointeurs P1, P2 et P3 qui représentent les blocs de disque inférieurs à. 17 et P2 représente les blocs de disque entre 17 et 35, P3 représente les blocs de disque supérieurs à 35. Les données réelles existent dans les nœuds feuilles, à savoir 3, 5, 9, 10, 13, 15, 28, 29, 36, 60, 75. , 79. , 90, 99. Les nœuds non-feuilles ne stockent pas de données réelles (Caractéristiques de B), seuls les éléments de données qui guident la direction de recherche, comme 17 et 35, n'existent pas vraiment dans la table de données >

.

Processus de recherche arborescente 2.B

Comme le montre la figure, si vous souhaitez trouver l'élément de données 29, le bloc de disque 1 sera d'abord chargé du disque vers la mémoire et une E/S se produira à ce moment, utilisez la recherche binaire en mémoire pour déterminer que 29 est compris entre 17 et 35, verrouillez le pointeur P2 du bloc disque 1, le temps mémoire est négligeable car très court (par rapport aux IO du disque), et passez l'adresse disque du pointeur P2 du bloc de disque 1 Chargez le bloc de disque 3 du disque vers la mémoire, la deuxième IO se produit, 29 est entre 26 et 30, verrouillez le pointeur P2 du bloc de disque 3, chargez le bloc de disque 8 dans la mémoire via le pointeur, le troisième IO se produit, et en même temps dans la mémoire Faites une recherche binaire et trouvez 29, terminez la requête, un total de trois IO

La situation réelle est qu'un b-tree à 3 couches peut représenter des millions de données. Si des millions de données sont recherchées, seulement trois IO sont nécessaires, ce qui améliorera les performances. S'il n'y a pas d'index, une IO se produira pour chaque élément de données, donc un total de. des millions d'IO seront nécessaires. Évidemment, le coût est très, très élevé

(Question ???, comme mentionné ci-dessus. , le B-tree d'INNOBD est un type d'index clusterisé, et les données réelles sont placées avec les nœuds feuilles d'index. La question est donc la suivante : si j'ai plusieurs index, est-il possible que les données soient stockées sous chaque index ? N'est-ce pas un gaspillage de stockage sur disque ? passé. Comment l'exprimer avec une structure de données ? )

Réponse : Chaque table ne peut avoir qu'un seul index clusterisé, et il peut y avoir plusieurs index auxiliaires. Le nœud ne stocke pas les données mais un pointeur pointant vers l'index principal où les données sont stockées

3.b Propriétés de l'arbre

Analyse, on sait que le nombre d'IO dépend du. hauteur h du nombre b. Supposons que les données dans la table de données actuelle soient N et que le nombre d'éléments de données dans chaque bloc de disque soit m, alors h=㏒(m 1)N, lorsque la quantité de données Lorsque N est bien sûr, plus m est grand, plus h et m sont petits ; = La taille du bloc disque/la taille de l'élément de données. La taille du bloc disque est la taille d'une page de données, qui est fixe. Si l'espace occupé par l'élément de données est plus petit, le nombre d'éléments de données est. plus, et la hauteur h de l'arbre est plus faible. Il y a également moins d'E/S. C'est pourquoi chaque élément de données, c'est-à-dire le champ d'index, doit être le plus petit possible.

À titre d'exemple négatif, int occupe 4 octets, soit la moitié de moins que bigint 8 octets. C'est pourquoi le b-tree nécessite que les données réelles soient placées dans des nœuds feuilles au lieu de nœuds internes. Une fois placés dans les nœuds internes, les éléments de données des blocs de disque diminueront considérablement (voir le principe dans la partie 2 ci-dessus), provoquant l'arbre. pour augmenter en hauteur. Lorsque la donnée est égale à 1, elle dégénère en un tableau linéaire. Comme suit :

Si c'est la structure de gauche, le nombre d'E/S est trois fois ; si c'est la table linéaire de droite, le nombre d'E/S ; Les E/S sont 6 fois. Il est évident que les IO changent. Il y a plus

mappage de deux conclusions :

1 Le champ len à définir. car un index doit être petit;

2. Faire une union Lors de l'indexation, le nombre de champs joints doit également être inférieur

2). Lorsque les éléments de données de l'arbre b sont des structures de données composites (index multi-colonnes), telles que (nom, âge, sexe), les nombres b sont utilisés pour construire l'arbre de recherche dans l'ordre de gauche. à droite.

Par exemple, lorsque des données telles que (Zhang San, 20 ans, F) sont récupérées, le b-tree comparera d'abord le nom pour déterminer la direction de recherche suivante. Si les noms sont identiques, l'âge et le sexe le seront. être comparé dans l'ordre, et finalement Les données récupérées sont obtenues ; mais lorsque des données sans nom comme (20,F) arrivent, le b-tree ne sait pas quel nœud vérifier ensuite, car le nom est le premier facteur de comparaison lors de la construction de la recherche. arbre, et il doit d'abord être effectué une recherche basée sur le nom pour savoir où rechercher ensuite.

Par exemple, lors de la récupération de données comme (Zhang San, F), le b-tree peut utiliser le nom pour spécifier la direction de recherche, mais l'âge du champ suivant est manquant, il ne peut donc récupérer que les données dont le nom est égal à Zhang San. Recherchez puis faites correspondre les données dont le sexe est F. Il s'agit d'une propriété très importante, c'est-à-dire la caractéristique de correspondance la plus à gauche de l'index.

cartographie deux conclusions :

1 La caractéristique de correspondance la plus à gauche, l'index conjoint est lu de gauche à droite

2. il existe un index multi-colonnes, alors l'index de gauche à droite n'a pas besoin d'être établi (a, b, c), puis (a), (a, b) n'a pas besoin d'être établi

3. Plus de conclusions : résumé de l'index MySQL http://blog.csdn.net/ty_hf/article/details/53526405

Ce qui précède est le contenu de la structure de données Mysql-index. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois (www. .php.cn) !