Compréhension approfondie de la structure de l'index MySQL

Cet article vous apporte des connaissances pertinentes sur mysql, qui introduit principalement des questions liées à la structure de l'index. Alors, quelle est la structure de l'index ? Pourquoi l’indexation peut-elle être si rapide ? Jetons un coup d'œil ci-dessous, j'espère que cela sera utile à tout le monde.

Apprentissage recommandé : Tutoriel mysql

Unité de stockage de base de données

Tout d'abord, nous devons savoir que pour obtenir la persistance, l'index ne peut être stocké que sur le disque dur lors d'une interrogation via l'index. , un disque dur sera généré des opérations d'E/S, par conséquent, lors de la conception de l'index, il est nécessaire de réduire autant que possible le nombre de recherches pour réduire le temps d'E/S.

De plus, vous devez connaître un principe très important : l'unité de base de l'espace de stockage de gestion de base de données est la page (Page), et plusieurs enregistrements de ligne (Row) sont stockés sur une seule page. 页(Page)，一个页中存储多条行记录(Row)。

计算机系统对磁盘 I/O 会做预读优化，当一次I/O时，除了当前磁盘地址的数据以外，还会把相邻的数据也读取到内存缓冲池中，每一次 I/O 读取的数据成为一页，InnoDB 默认的页大小是 16KB。
连续的 64 个页组成一个区(Extent)，一个或多个区组成一个段(Segment)，一个或多个段组成表空间(Tablespace)。InnoDB 有两种表空间类型，共享表空间表示多张表共享一个表空间，独立表空间表示每张表的数据和索引全部存在独立的表空间中。

数据页结构如下（图源：极客时间《MySQL 必知必会》）：

数据页的 7 个结构内容可以大致分为以下三类：

• 文件通用部分，用于校验页传输完整
  • 文件头（File Header）: 表述页信息，文件头中使用 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 构成一个双向链表，分别指向前后的数据页。
  • 页头（File Header）：记录页的状态信息
  • 文件尾（File Trailer）: 校验页是否完整
• 记录部分，用于存储数据记录
  • 最大最小记录（Infimum/Supremum）：虚拟的行记录，表示数据页的最大记录和最小记录。
  • 用户记录（User Record）和空闲空间（Free Space）: 用于存储数据行记录内容
• 索引部分，用于提高记录的检索效率
  • 页目录（Page Directory）：存储用户记录的相对位置

详情可参考淘宝的数据库内核月报

索引数据结构

很自然的，我们会想到查找算法中涉及到的一些常用数据结构，比如二叉查找树，二叉平衡树等等，实际上，Innodb 的索引是用 B+ 树

Le système informatique effectuera une optimisation de lecture anticipée pour les E/S du disque Lorsqu'une E/S est effectuée, en plus des données à l'adresse actuelle du disque, les données adjacentes seront également lues dans le disque. mémoire tampon. Dans le pool, les données lues par chaque E/S deviennent une page et la taille de page par défaut d'InnoDB est de 16 Ko.

64 pages consécutives forment un seul Étendue, une ou plusieurs étendues forment un Segment et un ou plusieurs segments forment un Tablespace. InnoDB a deux types d'espace table partagé, ce qui signifie que plusieurs tables partagent un espace table indépendant, ce qui signifie que les données et les index de chaque table sont tous stockés dans des espaces table indépendants.

La structure de la page de données est la suivante (Source : Geek Time "Must Know MySQL") :
Les 7 contenus structurels de la page de données peuvent être grossièrement divisés en trois catégories suivantes :

• Partie générale du fichier, utilisée pour vérifier que la transmission de la page est terminée
• En-tête de fichier : exprime les informations de page FIL_PAGE_PREV et FIL_PAGE_NEXT sont utilisées dans l'en-tête du fichier pour former une liste doublement chaînée, pointant respectivement vers les pages de données précédentes et suivantes.
• En-tête de fichier : enregistrez les informations d'état de la page
• Remorque de fichier : vérifiez si la page est complète

L'enregistrement la partie est utilisée pour stocker les enregistrements de données

• Enregistrements maximum et minimum (Infimum/Supremum) : enregistrements de lignes virtuelles, représentant l'enregistrement maximum et l'enregistrement minimum de la page de données.
• Enregistrement utilisateur et espace libre : utilisé pour stocker le contenu des enregistrements de lignes de données

Partie index, utilisée pour améliorer l'efficacité de la récupération des enregistrements

• Répertoire de pages : stocke l'emplacement relatif des enregistrements des utilisateurs

Pour plus de détails, veuillez vous référer au rapport mensuel du noyau de base de données de Taobao
Structure des données d'indexation

Naturellement, nous réfléchirons de certaines structures de données courantes impliquées dans les algorithmes de recherche, telles que les arbres de recherche binaires, les arbres binaires équilibrés, etc. En fait, l'index d'Innodb utilise B+ tree pour y parvenir, voyons pourquoi cette structure d'index a été choisi.

Limitations de l'arbre binaire

Tout d'abord, passons brièvement en revue la définition de l'arbre de recherche binaire. Dans un arbre de recherche binaire, si la clé à trouver est supérieure au nœud racine, recherchez dans le sous-arbre de droite si la clé est la suivante. est inférieur au nœud racine, recherchez dans le sous-arbre de gauche jusqu'à ce que la clé soit trouvée. La complexité temporelle est O(logn). Par exemple, la séquence [4,2,6,1,3,5,7] générera l'arbre de recherche binaire suivant :

Cependant, dans certains cas particuliers, la profondeur de l'arbre binaire sera très grande, comme comme [1,2, 3,4,5,6,7], l'arbre suivant sera généré :

🎜🎜 Dans la situation suivante, dans le pire des cas, il faut 7 fois pour trouver le résultat souhaité, et la requête le temps devient C'est O(n). 🎜🎜Afin d'optimiser cette situation, il existe un arbre de recherche binaire équilibré (arbre AVL). Un arbre AVL fait référence à un arbre dans lequel la différence de hauteur entre les sous-arbres gauche et droit ne dépasse pas 1. La complexité du temps de recherche est O. (logn), qui est déjà C'est un arbre de recherche relativement idéal, mais dans une base de données avec des dizaines de millions de lignes d'enregistrements, la profondeur de l'arbre sera toujours très élevée, et ce n'est toujours pas la structure la plus idéale. 🎜🎜Arbre B🎜🎜Donc, si vous passez d'un arbre binaire à un arbre N-aire, il est facile d'imaginer que l'arbre N-aire peut réduire considérablement la profondeur de l'arbre. La structure peut déjà prendre en charge des dizaines de téraoctets de données. 🎜🎜B-tree (Balance Tree) est un tel arbre N-aire, également appelé B-tree, qui satisfait à la définition suivante : 🎜 Soit k le degré de B-tree, indiquant le nombre d'enfants de chaque nœud. peut avoir au maximum un nœud), 🎜

1. Chaque bloc de disque contient au plus k - 1 个关键字 和 kdes pointeurs vers des nœuds enfants
2. Dans les nœuds feuilles, il n'y a que des mots-clés et aucun pointeur de nœud enfant
3. Les mots-clés de chaque nœud sont classés du plus petit au plus grand, et chaque clé Toutes les clés dans le sous-arbre gauche d'un mot est inférieur à lui et toutes les clés du sous-arbre droit sont supérieures à lui.
4. Tous les nœuds feuilles sont sur le même calque.

Comme mentionné ci-dessus, chaque E/S pré-lisera les données d'un bloc de disque, qui fait une page. Le contenu d'un bloc de disque est utilisé pour représenter une E/S. La structure du B-. L'arbre est le suivant (Source : Ji Vous devez connaître SQL en temps invité) :

Le B-tree est également ordonné Puisque le pointeur du nœud enfant doit être 1 de plus que le mot-clé, le mot-clé peut être utilisé pour diviser les segments. du nœud enfant. Comme dans l'exemple de la figure, chaque nœud A a 2 mots-clés et 3 nœuds enfants, tels que le bloc de disque 2. Le mot-clé 3, 5 du premier point d'octet est plus petit que son propre premier nœud enfant 8, et le 9, 10 du deuxième nœud enfant est compris entre 8 et 10. Entre 12 et 12, la valeur du troisième nœud enfant est 13 et 15, ce qui est supérieur à son deuxième nœud enfant 12.

Supposons que nous voulions trouver 9 maintenant, les étapes sont les suivantes :

1. Comparez avec le bloc de disque du nœud racine 1 (17,35), il est inférieur à 17, continuez à chercher dans le pointeur P1, correspondant au disque bloc 2
2. et bloc disque 2 (8, 12) Comparez, situé entre les deux, continuez à chercher au pointeur P2, correspondant au bloc disque 6
3. et comparez avec le bloc disque 6 (9, 10), vous pouvez voir que 9

est trouvé, bien que de nombreuses comparaisons aient été effectuées, mais en raison de la pré-lecture, la comparaison au sein du bloc disque est effectuée en mémoire, ce qui ne consomme pas d'E/S disque. L'opération ci-dessus ne nécessite que 3 E/S. Os à compléter, ce qui est une structure idéale.

Indice d'arbre B+

L'arbre B+ est encore amélioré sur la base de l'arbre B. La différence entre l'arbre B+ et l'arbre B est la suivante :

1. La façon dont l'arbre B+ est construit est celle des mots-clés dans le nœud parent, tous les mots-clés du sous-arbre de gauche sont inférieurs à celui-ci, et tous les mots-clés du sous-arbre de droite lui sont supérieurs ou égaux
2. Les nœuds non-feuilles ne sont utilisés que pour l'indexation et ne stockeront pas d'enregistrements de données
3. Mots-clés du parent Le nœud apparaîtra également dans les nœuds enfants et constitue la valeur maximale (ou la valeur minimale) dans les nœuds enfants
4. Tous les mots-clés apparaîtront dans les nœuds feuilles, et les nœuds feuilles forment une liste chaînée ordonnée, triée du plus petit au plus grand.

L'exemple est le suivant. Dans cet exemple, les mots-clés du nœud parent sont tous les valeurs minimales parmi les nœuds enfants (Source : Geek Time SQL doit savoir) :
Supposons que vous souhaitiez trouver le mot-clé 16, les étapes de recherche sont les suivantes :

1. Comparez avec le disque du nœud racine 1 (1,18,35), 16 est compris entre 1 et 18, obtenez le pointeur P1, pointant vers le disque 2
2. Trouver le disque 2 (1,8 ,14), 16 est supérieur à 14, obtenez le pointeur P3, pointant vers le disque 7
3. Trouver le disque 7 (14,16,17), trouver 16

B+ avantages de l'arbre :

1. Les nœuds internes ne stockent pas de données, Ainsi, le nombre d'enregistrements que chaque nœud interne peut stocker est beaucoup plus grand que B Tree, la hauteur de l'arbre est inférieure, les E/S sont moindres et la page de données lue par chaque E/S contient plus de contenu
2. Peut prendre en charge les requêtes de plage, parcourez simplement la liste chaînée ordonnée composée de nœuds feuilles directement
3. Toutes les données sont stockées dans des nœuds feuilles, de sorte que l'efficacité de la requête est plus stable

Indice HASH

La structure d'index par défaut du moteur de stockage de mémoire de MySQL est l'index de hachage. une fonction, appelée fonction de hachage, qui utilise un algorithme spécifique (tel que MD5 , SHA1, SHA2, etc.) pour convertir une entrée de n'importe quelle longueur en sortie de longueur fixe. L'entrée et la sortie correspondent une à une. une introduction approfondie à la fonction de hachage. Pour plus de détails, veuillez vous référer à l'Encyclopédie Baidu.

L'efficacité de la recherche de hachage est O(1), ce qui est très efficace. Le dict de Python, la carte de Golang et la carte de hachage de Java sont tous implémentés sur la base de bases de données de valeurs clés telles que Redis sont également implémentées par Hash.

Pour une recherche précise, l'index Hash est plus efficace que l'index arborescent B+, mais l'index Hash a certaines limites, ce n'est donc pas la structure d'index la plus courante.

1. Étant donné que les données pointées par l'index Hash ne sont pas ordonnées, l'index Hash ne peut pas être interrogé par plage et ne prend pas non plus en charge le tri ORDER BY.
2. Étant donné que Hash est une correspondance exacte, les requêtes floues ne peuvent pas être effectuées.
3. L'index de hachage ne prend pas en charge le principe de correspondance le plus à gauche de l'index conjoint, et l'index conjoint ne prend effet que lorsqu'il existe une correspondance complète. Parce que l'index de hachage calcule la valeur de hachage en fusionnant les index, puis en calculant la valeur de hachage ensemble, au lieu de calculer la valeur de hachage distincte de chaque index.
4. Si le champ indexé comporte de nombreuses valeurs en double, cela entraînera un grand nombre de conflits de hachage et la requête deviendra très longue.

Pour les raisons ci-dessus, le moteur Mysql InnoDB ne prend pas en charge l'index de hachage, mais il existe une fonction d'index de hachage adaptative dans la structure de la mémoire. Lorsqu'une certaine valeur d'index est utilisée très fréquemment, elle sera basée sur l'arborescence B+. index Créez automatiquement un index de hachage pour améliorer les performances des requêtes.

L'index Hash adaptatif peut être compris comme un "index d'index". L'index Hash est utilisé pour stocker l'adresse de la page dans l'index de l'arborescence B+ et localiser rapidement le nœud feuille correspondant. Il peut être consulté via la variable innodb_adaptive_hash_index.

Apprentissage recommandé : Tutoriel 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!