Qu’est-ce qu’un index dans MySQL ? Brève analyse du modèle de stockage d'index

La colonne tutoriel mysql suivante vous donnera une analyse approfondie des index dans MySQL et vous présentera quelques connaissances sur les index MySQL. J'espère qu'elle vous sera utile !

La base de données MySQL devrait être l'une des bases de données les plus couramment utilisées. Elle peut être vue dans diverses grandes et petites entreprises. Dans quelle mesure maîtrisez-vous la base de données MySQL ? Si l'on veut mieux l'utiliser, il faut d'abord le comprendre. Comme le dit le proverbe, si un travailleur veut bien faire son travail, il doit d'abord affûter ses outils. Cet article vous mènera à une analyse approfondie de certaines connaissances sur les index MySQL. Tout d'abord, comprenons ce qu'est un index et la déduction du modèle de stockage d'index Pourquoi la structure de données sous-jacente est-elle choisie

B+ tree

La raison. ? Qu'est-ce que l'index ?

Une table contient 5 millions de données. Exécutez une requête Where sur le champ de nom sans index :

select * from user_innodb where name ='小马';

Et s'il y a un index sur le champ de nom ? Créez un index sur le champ de nom et exécutez à nouveau la même requête.

ALTER TABLE user_innodb DROP INDEX idx_name; 
ALTER TABLE user_innodb ADD INDEX idx_name (name);

Par rapport aux requêtes sans index, l'efficacité des requêtes avec index est des dizaines de fois différente.

Grâce à ce cas, vous devriez pouvoir sentir intuitivement que l'indexation peut grandement améliorer les performances de récupération des données.

Alors, qu’est-ce qu’un indice exactement ? Pourquoi cela peut-il avoir un si grand impact sur nos requêtes ? Que se passe-t-il lorsque l'index est créé ?

Définition de l'index

Un index de base de données est une structure de données triée dans un système de gestion de base de données (SGBD) pour aider à interroger et mettre à jour rapidement les données dans les tables de base de données.

Les données sont stockées sur le disque sous forme de fichiers, et chaque ligne de données a son adresse de disque. S'il n'y a pas d'index, nous devons récupérer une donnée à partir de 5 millions de lignes de données, et nous ne pouvons parcourir toutes les données de cette table que jusqu'à ce que nous trouvions cette donnée.

Mais une fois que nous avons l'index, il nous suffit de récupérer ces données dans l'index, car il s'agit d'une structure de données spéciale conçue pour une récupération rapide. Après avoir trouvé l'adresse du disque où les données sont stockées, nous pouvons l'obtenir. les données.

Types d'index

Dans InnoDB, il existe trois types d'index : l'index ordinaire, l'index unique (l'index de clé primaire est un index unique spécial) et l'index de texte intégral.

Normal

 : Également appelé index non unique, c'est l'index le plus courant sans aucune restriction.

Unique

 : Un index unique nécessite que les valeurs clés ne puissent pas être répétées. De plus, il convient de noter que l'index de clé primaire est un index unique spécial. Il comporte également une restriction supplémentaire, qui exige que la valeur de la clé ne puisse pas être vide. Les index de clé primaire sont créés à l'aide de la clé primaire. Fulltext : Pour des données relativement volumineuses, par exemple, si nous stockons le contenu du message et plusieurs Ko de données, si vous souhaitez résoudre le problème de la faible efficacité des requêtes, vous pouvez créer un index de texte intégral. Les index de texte intégral ne peuvent être créés que pour les champs de type texte, tels que char, varchar et text.

Un index est une structure de données, alors quel type de structure de données doit-il choisir pour obtenir une récupération efficace des données ?

Déduction du modèle de stockage d'index

Recherche binaire

Après Double Eleven, votre petite amie a joué à un jeu de devinettes avec vous. Devinez combien j’ai acheté hier et donnez-vous cinq chances.

10000 ? Faible. 30 000 ? Haut. Que devinerez-vous ensuite ? 20000. Pourquoi n’avez-vous pas deviné 11 000 ou 29 000 ?

C'est une idée de recherche binaire, également appelée demi-recherche. À chaque fois, nous réduisons les données des candidats de moitié. Cette méthode est plus efficace si les données ont été triées.

Alors tout d'abord, nous pouvons envisager d'utiliser un tableau ordonné comme structure de données indexées.

Les requêtes égales et les requêtes de comparaison de tableaux ordonnés sont très efficaces, mais il y aura un problème lors de la mise à jour des données. Une grande quantité de données devra peut-être être déplacée (changement d'index), elle ne convient donc qu'au stockage de données statiques.

Afin de prendre en charge des modifications fréquentes, telles que l'insertion de données, nous devons utiliser des listes chaînées. Quant aux listes chaînées, s’il s’agit d’une liste chaînée unique, son efficacité de recherche n’est toujours pas assez élevée.

Alors, existe-t-il une liste chaînée qui peut utiliser la recherche binaire ?

Afin de résoudre ce problème, le BST (Binary [ˈbaɪnəri] Search Tree), qui est ce que nous appelons un arbre de recherche binaire, est né.

Arbre de recherche binaire (arbre de recherche binaire)

Tous les nœuds du sous-arbre de gauche sont plus petits que le nœud parent et tous les nœuds du sous-arbre de droite sont plus grands que le nœud parent. Après avoir été projeté sur un plan, il devient un tableau linéaire ordonné.

二叉查找树既能够实现快速查找，又能够实现快速插入。

但是二叉查找树有一个问题：查找耗时是和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成 O(n)。

什么情况是最坏的情况呢？

还是刚才的这一批数字，如果我们插入的数据刚好是有序的，2、10、12、15、 21、28

这个时候 BST 会变成链表（ “斜树”），这种情况下不能达到加快检索速度的目的，和顺序查找效率是没有区别的。

造成它倾斜的原因是什么呢？

因为左右子树深度差太大，这棵树的左子树根本没有节点——也就是它不够平衡。

所以，我们有没有左右子树深度相差不是那么大，更加平衡的树呢？

这个就是平衡二叉树，叫做 Balanced binary search trees，或者 AVL 树。

平衡二叉树（AVL Tree）

平衡二叉树的定义：左右子树深度差绝对值不能超过 1。

是什么意思呢？比如左子树的深度是 2，右子树的深度只能是 1 或者 3。

这个时候我们再按顺序插入 1、2、3、4、5、6，一定是这样，不会变成一棵“斜树”。

那 AVL 树的平衡是怎么做到的呢？怎么保证左右子树的深度差不能超过 1 呢？ 例如：插入 1、2、3。

当我们插入了 1、2 之后，如果按照二叉查找树的定义，3 肯定是要在 2 的右边的，这个时候根节点 1 的右节点深度会变成 2，但是左节点的深度是 0，因为它没有子节点，所以就会违反平衡二叉树的定义。

那应该怎么办呢？因为它是右节点下面接一个右节点，右-右型，所以这个时候我们要把 2 提上去，这个操作叫做左旋。

同样的，如果我们插入 7、6、5，这个时候会变成左左型，就会发生右旋操作，把 6 提上去。

所以为了保持平衡，AVL 树在插入和更新数据的时候执行了一系列的计算和调整的操作。

平衡的问题我们解决了，那么平衡二叉树作为索引怎么查询数据？ 在平衡二叉树中，一个节点，它的大小是一个固定的单位，作为索引应该存储什么内容？

第一个：索引的键值。比如我们在 id 上面创建了一个索引，我在用 where id =1 的条件查询的时候就会找到索引里面的 id 的这个键值。

第二个：数据的磁盘地址，因为索引的作用就是去查找数据的存放的地址。

第三个因为是二叉树，它必须还要有左子节点和右子节点的引用，这样我们才能找到下一个节点。比如大于 26 的时候，走右边，到下一个树的节点，继续判断。

如果是这样存储数据的话，我们来看一下会有什么问题。

首先，索引的数据，是放在硬盘上的。查看数据和索引的大小：

select CONCAT(ROUND(SUM(DATA_LENGTH/1024/1024),2),'MB') AS data_len, 
CONCAT(ROUND(SUM(INDEX_LENGTH/1024/1024),2),'MB') as index_len 
from information_schema.TABLES 
where table_schema='gupao' and table_name='user_innodb';

当我们用树的结构来存储索引的时候，因为拿到一块数据就要在 Server 层比较是不是需要的数据，如果不是的话就要再读一次磁盘。访问一个节点就要跟磁盘之间发生一次 IO。InnoDB 操作磁盘的最小的单位是一页（或者叫一个磁盘块），大小是 16K(16384 字节)。

Ensuite, un nœud d’arbre a une taille de 16 Ko. Si nous ne stockons qu'une seule valeur clé + données + référence dans un nœud, comme un champ entier, il ne peut utiliser qu'une douzaine ou des dizaines d'octets, ce qui est loin de la capacité de 16 Ko, donc accéder à un nœud d'arbre, lors de l'exécution une IO, beaucoup d’espace est perdu.

Donc, si chaque nœud stocke trop peu de données, pour trouver les données dont nous avons besoin à partir de l'index, nous devons accéder à plus de nœuds, ce qui signifie qu'il y aura trop d'interactions avec le disque.

À l'ère des disques durs mécaniques, il faut environ 10 ms de temps de recherche pour lire les données du disque à chaque fois. Plus il y a d'interactions, plus cela prend de temps.

Par exemple, dans l'image ci-dessus, nous avons 6 éléments de données dans une table. Lorsque nous interrogeons id=37, pour interroger deux nœuds enfants, nous devons interagir avec le disque 3 fois. Et si nous avons des millions de données. ? Ce temps est encore plus difficile à estimer.

Alors quelle est notre solution ?

La première consiste à laisser chaque nœud stocker plus de données.

Deuxièmement, plus il y a de mots-clés sur un nœud, plus nous avons de pointeurs, ce qui signifie qu'il peut y avoir plus de forks.

Parce que plus il y a de branches, la profondeur de l'arbre diminuera (le nœud racine est 0). De cette façon, notre arbre passera-t-il de son aspect grand et mince d'origine à un aspect court et gros ?

À l'heure actuelle, notre arbre n'est plus à deux fourches, mais à plusieurs fourches, ou à plusieurs voies.

Arbre de recherche équilibré à plusieurs voies (arbre B)

Identique à l'arbre AVL, l'arbre B stocke les valeurs clés, les adresses de données et les références de nœuds dans les nœuds de branche et les nœuds feuilles.

Il a une particularité : le nombre de forks (nombre de chemins) est toujours 1 de plus que le nombre de mots-clés. Par exemple, dans l’arborescence que nous avons dessinée, chaque nœud stocke deux mots-clés, il y aura donc trois pointeurs pointant vers trois nœuds enfants.

Quelles sont les règles de recherche pour B Tree ?

Par exemple, nous voulons en trouver 15 dans ce tableau. Puisque 15 est inférieur à 17, allez à gauche. Puisque 15 est supérieur à 12, allez vers la droite. 15 ont été trouvés dans le bloc de disque 7 et seulement 3 E/S ont été utilisées.

Est-ce plus efficace que l'arbre AVL ? Alors, comment B Tree réalise-t-il qu'un nœud stocke plusieurs mots-clés tout en maintenant l'équilibre ? Quelle est la différence avec les arbres AVL ?

Par exemple, lorsque le degré maximum (nombre de façons) est de 3, nous insérons les données 1, 2 et 3. Lors de l'insertion de 3, elles doivent être dans le premier bloc de disque, mais si un nœud a trois mots-clés, ceci signifie qu'il y a 4 pointeurs et que les nœuds enfants deviendront à 4 voies, donc le fractionnement doit être effectué à ce moment (en fait B+Tree). Affichez les données du milieu 2 et transformez 1 et 3 en nœuds enfants de 2.

Si vous supprimez un nœud, il y aura une opération de fusion inversée.

Notez qu'il s'agit d'un fractionnement et d'une fusion, ce qui est différent de la rotation à gauche et à droite de l'arborescence AVL.

Nous continuons à insérer 4 et 5, et B Tree se divisera et fusionnera à nouveau.

De cela, nous pouvons également voir qu'il y aura beaucoup d'ajustements structurels à l'index lors de la mise à jour de l'index, ce qui explique pourquoi nous ne construisons pas d'index sur des colonnes fréquemment mises à jour, ou pourquoi nous ne mettons pas à jour le clé primaire.

Le fractionnement et la fusion de nœuds sont en fait le fractionnement et la fusion de pages InnoDB.

B+Tree (version améliorée de B Tree)

B Tree est déjà très efficace Pourquoi MySQL a-t-il encore besoin d'améliorer B Tree et enfin d'utiliser B+Tree ?

En général, cette version améliorée de B-Tree résout des problèmes plus complets que B-Tree.

Regardons la structure de stockage de l'arbre B+ dans InnoDB :

Le B+Tree dans MySQL a plusieurs caractéristiques :

1. Le nombre de ses mots-clés est égal au nombre de chemins

2. B+Tree ne stockera pas de données dans le nœud racine ou les nœuds de branche, seuls les nœuds feuilles stockeront les données. La recherche de mots-clés ne reviendra pas directement, mais ira aux nœuds feuilles de la dernière couche. Par exemple, si nous recherchons id=28, bien qu'il soit directement atteint sur la première couche, toutes les données se trouvent sur les nœuds feuilles, je vais donc continuer à chercher vers le bas, jusqu'aux nœuds feuilles.

3. Chaque nœud feuille de B+Tree ajoute un pointeur vers le nœud feuille adjacent, et ses dernières données pointeront vers les premières données du nœud feuille suivant, formant une structure de liste chaînée ordonnée.

4. Il récupère les données en fonction de l'intervalle gauche-fermé-droite-ouvert [ ).

Processus de recherche de données de B+Tree :

1. Par exemple, si nous voulons rechercher 28, nous avons trouvé la valeur clé au niveau du nœud racine, mais comme il ne s'agit pas d'un nœud enfant de page, nous continuerons à chercher vers le bas, 28 est la valeur critique de gauche. -intervalle fermé et ouvert à droite de [28,66), nous irons donc au nœud enfant du milieu, puis continuerons à rechercher, qui est la valeur critique de l'intervalle fermé à gauche et ouvert à droite de [28,34 ), nous allons donc aller au nœud enfant de gauche, et enfin trouver les données requises sur le nœud feuille .

2. Deuxièmement, s'il s'agit d'une requête de plage, par exemple, si vous souhaitez interroger des données de 22 à 60, après avoir trouvé 22, il vous suffit de parcourir séquentiellement le long des nœuds et des pointeurs pour accéder à tous les nœuds de données à la fois. , de sorte que Améliore considérablement l'efficacité de la requête par intervalles (pas besoin de revenir au nœud parent supérieur pour parcourir la recherche à plusieurs reprises).

Caractéristiques de B+Tree dans InnoDB :

1. C'est une variante de B Tree. Il peut résoudre tous les problèmes que B Tree peut résoudre. Quels sont les deux problèmes majeurs résolus par B Tree ? (Chaque nœud stocke plus de mots-clés ; plus de chemins) ;

2. Capacités d'analyse de base de données et de table plus puissantes (si nous voulons effectuer une analyse complète de la table, il suffit de parcourir les nœuds feuilles, pas besoin de parcourir l'intégralité du B +Tree pour obtenir toutes les données) ;

3. B+Tree a des capacités de lecture et d'écriture sur disque plus puissantes que B Tree (le nœud racine et les nœuds de branche n'enregistrent pas la zone de données, donc un nœud peut enregistrer plus de mots-clés, plus de mots-clés sont chargés sur le disque en même temps)

4. La capacité de tri est plus forte (car il y a un pointeur vers la zone de données suivante sur le nœud feuille et les données forment une liste chaînée) ; est plus stable (B + Tree obtient toujours les données des nœuds feuilles, donc le nombre d'E/S est stable).

5. Postscript

Après avoir vu cela, je pense que tout le monde devrait savoir pourquoi MySQL choisit d'utiliser l'arborescence B+ comme modèle de structure de données de l'index.

Pour plus de connaissances sur la programmation, veuillez visiter :

Introduction à la programmation

 ! !

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!