Les fichiers de stockage de données InnoDB sont différents de MyISAM

Tutoriel MySQL Pourquoi l'index introduit dans la colonne utilise-t-il B+Tree

Avant-propos

Le titre de cet article est un réel problème que j'ai rencontré lors du processus d'entretien. Une société de financement participatif sur Internet a été la première à tester les connaissances liées à MySQL de l'intervieweur. Question, j'étais assez confus à l'époque. Je ne m'attendais pas à ce que ce jeune homme ne pratique pas les arts martiaux et ne joue pas ses cartes selon des routines. Lorsqu'il lui posait des questions sur ses connaissances liées à MySQL, il ne le faisait pas toujours. poser des questions sur l'optimisation de l'index, l'échec de l'index et d'autres problèmes connexes ? Pourquoi est-il sorti ? Les fichiers de stockage sont différents ? Même l'examen d'un mécanisme MVCC fera l'affaire. Cette fois, je vais donc résumer cette partie des points de connaissance.

Pourquoi avez-vous besoin de créer un index

Tout d'abord, nous savons tous que le but de la création d'un index est d'augmenter la vitesse des requêtes, alors pourquoi un index peut-il augmenter la vitesse des requêtes ?
Jetons un coup d’œil à un diagramme schématique d’un index.

Si j'ai une instruction SQL : select * from Table where id = 15 Puis en l'absence d'index, un parcours complet de la table sera effectué je rechercherai un par un jusqu'à trouver l'enregistrement avec l'id=15. . , la complexité temporelle est O(n);

Et si la requête est effectuée avec un index ? Tout d'abord, une recherche binaire sera effectuée dans la valeur d'index basée sur id=15. L'efficacité de la recherche binaire est très élevée et sa complexité temporelle est O(logn) ; efficacité, mais la quantité de données d'index est également relativement importante, elles ne sont donc généralement pas stockées en mémoire, mais sont stockées directement sur le disque. Par conséquent, les E/S du disque sont inévitables lors de la lecture du contenu du fichier sur le disque.

Pourquoi MySQL utilise-t-il B+Tree pour l'indexation ? Si le fichier d'index est très volumineux, il ne peut pas être chargé dans la mémoire en même temps, donc lorsque vous utilisez l'index pour rechercher des données, plusieurs E/S sur disque sont nécessaires. sera effectué pour charger les données d'index dans la mémoire par lots, <p> Par conséquent, une bonne structure de données indexées doit avoir le moins de fois d'E/S disque dans le but d'obtenir des résultats corrects. <strong></strong></p>

Type de hachage<strong>因此一个好的索引的数据结构，在得到正确的结果前提下，一定是磁盘IO次数最少的。</strong>

Actuellement, MySQL propose en fait deux types de données d'index, l'un est BTree (en fait B+Tree ), un hachage. Mais pourquoi la plupart des gens choisissent BTree dans l'utilisation réelle ?

Parce que si vous utilisez un index de type Hash, MySQL effectuera une opération de hachage sur les données de l'index lors de la création de l'index, afin que le pointeur du disque puisse être rapidement localisé en fonction de la valeur de hachage, même si la quantité de les données sont volumineuses. Les données peuvent également être localisées rapidement et avec précision.

Mais pour les requêtes par plage comme

, les index de type Hash ne peuvent pas gérer les requêtes par plage, la table entière sera analysée directement. De plus, les index de type Hash ne peuvent pas gérer le tri.

De plus, bien que la couche inférieure de MySQL ait effectué une série de traitements, il n'est toujours pas complètement garanti qu'aucune collision de hachage ne se produira.
• select * from Table where id > 15
• Arbre binaire

Alors pourquoi MySQL n'a-t-il pas d'arbre binaire comme structure de données d'index ? Nous savons tous que les arbres binaires localisent les données via la recherche binaire, donc l'effet est toujours bon et la complexité temporelle est O(logn);

Mais il y a un problème avec les arbres binaires, c'est-à-dire dans des cas particuliers, elle dégénérera en un bâton, c'est-à-dire une liste chaînée à sens unique. À ce stade, sa complexité temporelle dégénérera en O(n);

Ainsi, lorsque nous voulons interroger l'enregistrement avec id=50, c'est en fait la même chose qu'une analyse de table complète. Ainsi, à cause de cette situation, l’arbre binaire ne convient pas comme structure de données d’index.

Arbre binaire équilibré

Donc, puisqu'un arbre binaire dégénérera en une liste chaînée dans des circonstances particulières, pourquoi pas un arbre binaire équilibré ?

La différence de hauteur entre les nœuds enfants d'un arbre binaire équilibré ne peut pas dépasser 1

Comme l'arbre binaire de la figure ci-dessous, le nœud avec la clé 15 a une hauteur de 0 sur son. le nœud enfant gauche et une hauteur de 0 sur son nœud enfant droit est 1, et la différence de hauteur ne dépasse pas 1, donc l'arbre ci-dessous est un arbre binaire équilibré.

Parce qu'il peut maintenir l'équilibre, sa complexité temporelle de requête est O(logN). Quant à la façon de maintenir l'équilibre, cela implique principalement d'effectuer une rotation à gauche, une rotation à droite, etc. Les détails spécifiques sur le maintien de l'équilibre ne figurent pas dans cet article. Si vous souhaitez connaître le contenu principal, vous pouvez le rechercher vous-même.
Quels sont les problèmes liés à l'utilisation de cette structure de données pour indexer MySQL ?

• Trop d'IO de disque : Dans MySQL, une opération d'IO ne lit qu'un seul nœud. Si un nœud a au plus deux nœuds enfants, alors il n'y a que des requêtes pour ces deux nœuds enfants. , donc pour être précis sur des données spécifiques, plusieurs lectures sont nécessaires. Si l'arborescence est très profonde, une grande quantité d'E/S disque sera effectuée. Les performances se dégradent naturellement.
• Faible utilisation de l'espace : Pour un arbre binaire équilibré, chaque valeur de nœud stocke un mot-clé, une zone de données et des pointeurs vers deux nœuds enfants. Par conséquent, charger seulement une si petite quantité de données en une seule opération d’E/S laborieuse est vraiment exagéré.
• L'effet de requête est instable : Si dans un arbre binaire équilibré avec une hauteur très profonde, si les données interrogées se trouvent être le nœud racine, elles seront trouvées rapidement. Les données sont S'il s'agit d'un nœud feuille, il devra effectuer plusieurs E/S sur disque avant de pouvoir être renvoyé. Le temps de réponse peut ne pas être du même ordre de grandeur que celui du nœud racine.

Bien que l'arbre binaire résolve le problème de l'équilibre, il apporte également de nouveaux problèmes, c'est-à-dire qu'en raison de la profondeur de son propre arbre, il provoquera une série de problèmes d'efficacité.

Ainsi, afin de résoudre le problème de l'équilibrage des arbres binaires, le multi-arbre équilibré (Balance Tree) est devenu un meilleur choix.

Balance Tree – B-Tree

B-Tree signifie multi-arbre équilibré. Généralement, un nœud dans B-Tree a le nombre de nœuds enfants que nous avons. appelez un B-Tree de cet ordre. Habituellement, m est utilisé pour représenter l'ordre. Lorsque m vaut 2, il s'agit d'un arbre binaire équilibré.

Chaque nœud d'un B-Tree peut avoir au plus m-1 mots-clés, et au moins Math.ceil(m/2)-1 mots-clés doivent être stockés. Tous les nœuds feuilles sont au même niveau. L'image ci-dessous est un B-Tree du 4ème ordre.

Ensuite, regardons comment B-Tree recherche les données  :

• Si vous interrogez les données avec id=7, ajoutez d'abord le mot-clé Le nœud 20 est chargé dans la mémoire, et il est jugé que 7 est inférieur à 20
• Chargez ensuite le premier nœud enfant Si la donnée interrogée est égale à 12 ou 17, elle sera renvoyée. directement S'il n'est pas égal, continuez à chercher vers le bas et trouvez 7 Moins de 12
• Continuez ensuite à charger le premier nœud enfant. Après avoir trouvé 7, renvoyez directement les données en dessous de 7.

De cette façon, l'ensemble de l'opération effectue en fait 3 opérations d'E/S, mais en fait, le B-Tree général a de nombreuses branches (généralement supérieures à 100) dans chaque couche.

Afin de mieux utiliser la capacité IO du disque, MySQL définit la taille de la page d'opération à 16 Ko, c'est-à-dire que la taille de chaque nœud est de 16 Ko. Si les mots-clés de chaque nœud sont de type int, alors ils font 4 octets. Si la taille de la zone de données est de 8 octets et que le pointeur de nœud occupe 4 octets supplémentaires, alors chaque nœud du B-Tree est le nombre de mots-clés. peut être enregistré est : (16*1000) / (4+8+4)=1000, chaque nœud peut stocker jusqu'à 1000 mots-clés et chaque nœud peut avoir jusqu'à 1001 nœuds de branche.

De cette façon, lors de l'interrogation des données d'index, une opération d'E/S sur disque peut lire 1 000 mots-clés dans la mémoire pour le calcul. Une opération d'E/S sur disque de B-Tree équilibre les données binaires sur N opérations d'E/S sur disque. effectué.

要注意的是 : B-Tree effectuera une série d'opérations afin d'assurer l'équilibre des données. Ce processus de maintien de l'équilibre prend du temps, alors quand. lors de la création de l'index, choisissez les champs appropriés et ne créez pas trop d'index. Si vous créez trop d'index, le processus de mise à jour de l'index prendra plus de temps lors de la mise à jour des données.

De plus, Ne choisissez pas des valeurs de champ à faible discrimination comme index, comme les champs de genre, qui n'ont que deux valeurs au total, ce qui peut entraîner la profondeur du B -L'arbre est trop grand et l'indice d'efficacité est réduit.

B+Tree

B-Tree a très bien résolu le problème des arbres binaires équilibrés et peut également garantir l'efficacité des requêtes, alors pourquoi y a-t-il quoi à propos de B+Tree ?

Regardons d’abord à quoi ressemble B+Tree.

B+Tree est une variante de B-Tree. La relation de formule entre chaque mot-clé de nœud et l'ordre m de B+Tree est différente de celle de B-Tree.

Tout d'abord, le nombre de nœuds enfants de chaque nœud et le ratio de mots-clés pouvant être stockés dans chaque nœud sont 1:1. Deuxièmement, lors de l'interrogation de données, l'intervalle fermé de gauche est utilisé pour l'interrogation, et il y a des nœuds de branche Lorsqu'il n'y a pas de données, seuls les mots-clés et les points de nœuds enfants sont enregistrés et les données sont stockées dans les nœuds feuilles.

Voyons ensuite comment effectuer une requête de données dans B+Tree.

Par exemple :

• Maintenant, pour interroger les données avec id=2, le nœud racine sera d'abord extrait et chargé dans la mémoire. On constate que id=2 existe dans le nœud racine car les données sont stockées dans le. intervalle fermé à gauche, les id sont tous sur le premier nœud enfant du nœud racine
• puis retirez le premier nœud enfant, chargez-le dans la mémoire et constatez que le nœud actuel a le mot-clé et a atteint le nœud feuille, puis récupérez directement les données des nœuds feuilles et renvoyez-les. id=2

Regardons maintenant la différence entre B-Tree et B+Tree

• L'intervalle fermé gauche utilisé dans B+Tree query , qui peut mieux prendre en charge l'effet de requête des index à incrémentation automatique, donc généralement lors de la création de clés primaires, elles s'auto-incrémentent généralement. Ceci est différent de B-Tree.
• Aucune donnée n'est enregistrée sur le nœud racine et les nœuds de branche dans B+Tree. Les données liées aux mots-clés ne sont enregistrées que sur les nœuds feuilles. Cela garantit la stabilité de l'effet de requête. La requête doit aller au nœud feuille pour obtenir des données. B-Tree enregistre les données dans les nœuds de branche, et si le mot-clé est atteint, les données sont renvoyées directement.
• Les nœuds feuilles de B+Tree sont disposés séquentiellement et les deux nœuds feuilles adjacents ont une relation de référence séquentielle, ce qui peut mieux prendre en charge les requêtes de plage. B-Tree n'a pas cette relation d'ordre.

Pourquoi MySQL a choisi B+Tree pour son index

Après l'analyse couche par couche ci-dessus, nous pouvons maintenant résumer pourquoi MySQL a choisi B+Tree comme index . Qu'en est-il des structures de données.

1. Tout d'abord, par rapport à l'arbre binaire équilibré, B+Tree a une profondeur inférieure, plus de nœuds enregistrent des mots-clés, moins de temps d'E/S disque et une meilleure efficacité de calcul des requêtes.

2. B+Tree a des capacités d'analyse globale plus puissantes. Si vous souhaitez analyser globalement la table de données en fonction des données d'index, B-Tree analysera l'intégralité de l'arborescence. , puis parcourez couche par couche. Quant à B+Tree, il vous suffit de parcourir les nœuds feuilles, car il existe une relation de référence séquentielle entre les nœuds feuilles.

3. B+Tree a des capacités de lecture et d'écriture d'E/S disque plus fortes, car seuls les mots-clés sont enregistrés sur chaque nœud de branche de B+Tree, de sorte qu'à chaque fois que le disque Lorsque IO lit et écrit, une page de 16 Ko de données peut stocker plus de mots-clés, et chaque nœud peut stocker plus de mots-clés que B-Tree. De cette façon, B+Tree charge beaucoup plus de données dans une seule E/S disque que B-Tree.

4. La structure de données B+Tree a une capacité de tri naturelle, qui est plus forte que les autres structures de données et le tri est effectué via des nœuds de branche si vous en avez besoin. chargez les nœuds de branche en mémoire pour le tri, plus de données peuvent être chargées en même temps.

5. L'effet de requête de B+Tree est plus stable, car toutes les requêtes doivent analyser les nœuds feuilles avant de renvoyer les données. L'effet est seulement stable mais pas nécessairement optimal. Si les données du nœud racine de B-Tree sont directement interrogées, B-Tree peut renvoyer directement les données avec une seule E/S disque, mais l'effet est optimal.

Après avoir analysé les points ci-dessus, MySQL a finalement choisi B+Tree comme structure de données de son index.

Quelles sont les différences entre les fichiers de stockage de données d'InnDB et ceux de MyISAM ?

Ce qui précède résume la structure des données de l'index MySQL. Cette fois, nous pouvons parler de la deuxième question, car ce problème a en fait une certaine relation avec l'index MySQL.

Jetons un coup d'œil. Trouvez d'abord le répertoire dans lequel le serveur MySQL stocke les données :
Connectez-vous à MySQL et ouvrez l'interface de ligne de commande MySQL : entrez
et vous verrez le répertoire dans lequel les données sont stockées. show variables like '%datadir%'; Le répertoire dans lequel MySQL stocke les données sur mon serveur est :

/var/lib/mysql/

Après avoir entré ce répertoire, vous pouvez voir les répertoires de toutes les bases de données et créer une nouvelle base de données

. study_test Entrez ensuite dans le répertoire

/var/lib/mysql/study_test

Actuellement, il n'existe qu'un seul fichier. Ce fichier permet d'enregistrer le contenu du jeu de caractères configuré lors de la création de la base de données.

-rw-r----- 1 mysql mysql     60 1月  31 10:28 db.opt

Créez maintenant deux nouvelles tables, sélectionnez InnoDB comme type de moteur de la première table et sélectionnez MyISAM comme type de moteur de la deuxième table.

student_innodb：

CREATE TABLE `student_innodb` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `name` varchar(50) COLLATE utf8mb4_bin DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `address` varchar(100) COLLATE utf8mb4_bin DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_name` (`name`) USING BTREE COMMENT 'name索引') ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_bin COMMENT='innodb引擎表';

student_myisam：

CREATE TABLE `student_myisam` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `name` varchar(50) COLLATE utf8mb4_bin DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `address` varchar(100) COLLATE utf8mb4_bin DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_name` (`name`) USING BTREE COMMENT 'name索引') ENGINE=MyISAM DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_bin COMMENT='myISAM引擎类型表';

Après la création des deux tables, on entre

Prendre un regardez : /var/lib/mysql/study_test

-rw-r----- 1 mysql mysql     60 1月  31 10:28 db.opt-rw-r----- 1 mysql mysql   8650 1月  31 10:41 student_innodb.frm-rw-r----- 1 mysql mysql 114688 1月  31 10:41 student_innodb.ibd-rw-r----- 1 mysql mysql   8650 1月  31 10:58 student_myisam.frm-rw-r----- 1 mysql mysql      0 1月  31 10:58 student_myisam.MYD-rw-r----- 1 mysql mysql   1024 1月  31 10:58 student_myisam.MYI

À travers les fichiers du répertoire, vous pouvez voir qu'il y a plusieurs autres fichiers après la création de la table. Cela montre également les différences de fichiers entre la table des types de moteur InnoDB et la table des types de moteur MyISAM.

Chacun de ces fichiers a son propre rôle :

• Il existe deux fichiers de table dans le moteur InnoDB :
  • *.frm Ce type de fichier est le fichier de définition de la table.
  • *.ibd Ces fichiers sont des fichiers de stockage de données et d'index. Les données des tables et les index sont agrégées et stockées, et les données peuvent être directement interrogées via l'index.
• Il existe trois fichiers de table dans le moteur MyIASM :
  • *.frm Ce type de fichier est le fichier de définition de la table.
  • *.MYD Ce type de fichier est un fichier de données de table, et toutes les données du tableau sont enregistrées dans ce fichier.
  • *.MYI Ce type de fichier est le fichier d'index de la table, et les données d'index du moteur de stockage MyISAM sont stockées séparément.

Moteur de stockage de données MyISAM, index et structure de stockage de données

Lorsque le moteur de stockage MyISAM stocke l'index, les données sont stocké séparément, et le B+Tree indexé pointe finalement vers l'adresse physique où les données existent, et non vers les données spécifiques. Recherchez ensuite les données spécifiques dans le fichier de données (*.MYD) en fonction de l'adresse physique.

Comme le montre la figure ci-dessous :

Ensuite, lorsqu'il y a plusieurs index, plusieurs index pointent vers la même adresse physique.
Comme le montre la figure ci-dessous :

Grâce à cette structure, nous pouvons voir que les index du moteur de stockage MyISAM sont tous au même niveau, et l'index de clé primaire et celui de clé non primaire les structures et les méthodes de requête sont exactement les mêmes.

Moteur de stockage de données InnoDB, index et structure de stockage de données

Tout d'abord, les index InnoDB sont divisés en index clusterisés et les index non clusterisés stockent des mots clés. enregistrez les données, les mots-clés sont enregistrés sur chaque nœud de branche de B+Tree et les données sont enregistrées sur les nœuds feuilles.
"Clustering" signifie que les lignes de données sont stockées étroitement ensemble une par une dans un certain ordre. Une table ne peut avoir qu'un seul index clusterisé, car il n'y a qu'une seule façon de stocker des données dans une table. Généralement, la clé primaire est utilisée comme index clusterisé. S'il n'y a pas de clé primaire, InnoDB générera une colonne cachée comme primaire. clé par défaut.

Comme le montre la figure ci-dessous :

Index non clusterisé, également appelé index secondaire, bien qu'il enregistre également des mots-clés sur chaque nœud de branche de B+Tree, mais les feuilles Les nœuds ne sont pas des données enregistrées, mais des valeurs de clé primaire enregistrées. L'interrogation de données via l'index secondaire interrogera d'abord la clé primaire correspondant aux données, puis interrogera la ligne de données spécifique en fonction de la clé primaire.

Comme le montre la figure ci-dessous :

En raison de la structure de conception de l'index non clusterisé, l'index non clusterisé doit effectuer deux récupérations d'index lors de l'interrogation de cette conception. L'avantage est qu'une fois la migration des données effectuée, seul l'index de clé primaire doit être mis à jour et l'index non clusterisé n'a pas besoin d'être déplacé. Cela évite également d'avoir à stocker des adresses physiques comme l'index MyISAM, qui doit être déplacé. maintenu pendant la migration des données. Tous les problèmes d'indexation.

Résumé

Cette fois, j'ai clairement résumé la structure des données de l'index MySQL et la structure de stockage des fichiers plus tard, dans le processus de travail lui-même, lors de la conception de l'index. peut penser de manière plus globale. En comprenant la structure des données de l'index, vous pouvez également déterminer, lorsque vous écrivez réellement du SQL, quelles situations sont indexées et lesquelles ne le sont pas.

• MySQL utilise B+Tree comme structure de données de l'index. Étant donné que B+Tree a une faible profondeur, les nœuds stockent plus de mots-clés et le nombre d'E/S sur disque est faible, garantissant ainsi une plus grande efficacité des requêtes.
• B+Tree peut garantir que l'effet de requête de MySQL est stable, qu'il s'agisse d'un index de clé primaire ou d'un index de clé non primaire. Chaque fois, le nœud feuille doit être interrogé pour renvoyer des données. le nœud feuille de B+Tree est le même, et afin de mieux prendre en charge les clés primaires à incrémentation automatique, la plage de nœuds de requête de B+Tree est fermée à gauche et ouverte à droite.
• Le moteur de stockage MyISAM de MySQL, les données de table et les données d'index sont stockées respectivement dans deux fichiers, en raison du B+Tree de son propre index L'adresse du disque où se trouve le les données de la table pointées par le nœud feuille sont localisées et l'index ne fait pas de distinction entre la clé primaire et la clé non primaire, donc un stockage séparé peut mieux gérer l'index de manière unifiée
• Moteur de stockage InnoDB de MySQL ; Les données de table et données d'index sont stockées dans un fichier, car les nœuds feuilles de l'index clusterisé d'InnoDB pointent vers des lignes de données spécifiques, et afin d'assurer la stabilité de l'effet de requête, le La table InnoDB doit Il existe un index clusterisé. Lorsque l'index secondaire effectue une récupération d'index, il récupère d'abord la valeur de la clé primaire des données via l'index secondaire, puis récupère les données spécifiques dans l'index cluster en fonction de la clé primaire.

Recommandations d'apprentissage gratuites associées : Tutoriel vidéo MySQL

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!