Comment comprendre le problème de l'utilisation de l'arbre B+ dans la structure d'index MySQL

1. B-tree et B+-tree

De manière générale, le moteur de stockage de la base de données utilise B-tree ou B+-tree pour stocker l'index. Regardez d’abord l’arbre B, comme indiqué sur la figure.

L'arbre B est un arbre équilibré à plusieurs voies. Cette structure de stockage est utilisée pour stocker une grande quantité de données. Sa hauteur totale sera plus élevée. celui d'un arbre binaire, sera beaucoup plus court.

Pour la base de données, toutes les données seront enregistrées sur le disque et l'efficacité des E/S disque est relativement faible, en particulier dans le cas d'E/S disque aléatoires.

Ainsi, la hauteur détermine le nombre d'E/S disque. Moins le nombre d'E/S disque est important, plus l'amélioration des performances est importante. C'est pourquoi B-tree est utilisé comme structure de stockage d'index. comme le montre la figure présentée.

Le moteur de stockage InnoDB de MySQL utilise une structure B-tree améliorée, à savoir l'arbre B+, comme structure d'index et de stockage de données.

Par rapport à la structure B-tree, l'arbre B+ a été optimisé sous deux aspects, comme le montre la figure.

1. Toutes les données de l'arborescence B+ sont stockées dans des nœuds feuilles, et les nœuds non-feuilles ne stockent que des index.

2. Les données dans les nœuds feuilles sont liées à l'aide d'une liste doublement chaînée.

2. Analyse des raisons

Je pense que la structure d'index MySQL utilise l'arbre B+ pour les 4 raisons suivantes :

#🎜 🎜#

1. Du point de vue de l'efficacité des E/S disque : les nœuds non-feuilles de l'arborescence B+ ne stockent pas de données, donc chaque couche de l'arborescence peut stocker plus d'index. Lorsque la hauteur de la couche est la même, il peut stocker plus de données qu'un B-tree, ce qui réduira indirectement le nombre d'E/S disque.

2. Du point de vue de l'efficacité des requêtes par plage : dans MySQL, la requête par plage est une opération relativement courante, et toutes les données stockées dans les nœuds feuilles de l'arborescence B+ sont liées à l'aide de listes doublement chaînées, donc lors de l'interrogation , l'arbre B+ n'a besoin de vérifier que deux nœuds pour le parcours, tandis que l'arbre B+ doit obtenir tous les nœuds. Par conséquent, l'arbre B+ est plus efficace dans les requêtes de plage.

3. Du point de vue de l'analyse complète de la table : étant donné que les nœuds feuilles de l'arborescence B+ stockent toutes les données, la capacité d'analyse globale de l'arborescence B+ est plus forte car elle n'a besoin d'analyser que les nœuds feuilles. Le B-tree doit parcourir l’ensemble de l’arbre.

4. Du point de vue de l'ID auto-croissant : une structure de données basée sur un arbre B+, si des données entières auto-croissantes sont utilisées comme clé primaire, cela peut mieux éviter d'ajouter des données. le problème d'un grand nombre d'opérations causées par la division des nœuds feuilles.

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!