Quelle structure de données l'index MySQL utilise-t-il généralement ?

MyISAM est le moteur de stockage par défaut pour les versions MySQL antérieures à 5.5. À partir de la version 5.5, InnoDB devient le moteur de stockage par défaut pour MySQL.

MyISAM utilise B-Tree pour implémenter l'index de clé primaire, l'index unique et l'index de clé non primaire.

InnoDB utilise la structure de données B-Tree pour les index de clé non primaire, tandis que B+Tree est utilisé pour les index de clé primaire.

B-Tree

B-tree (arbre de recherche multidirectionnel, non binaire) est une structure de données courante. L'utilisation de la structure B-tree peut réduire considérablement le processus intermédiaire rencontré lors de la localisation des enregistrements, accélérant ainsi l'accès. Selon la traduction, B est généralement considéré comme l'abréviation de Balance. Cette structure de données est généralement utilisée pour l'indexation de bases de données et présente une efficacité globale élevée.

Performances(Apprentissage recommandé : Tutoriel vidéo MySQL)

B-tree a les fonctionnalités suivantes :

1. La collection est répartie dans tout l'arborescence ;

2. Tout mot-clé apparaît et n'apparaît que dans un seul nœud

3. La recherche peut se terminer à un nœud non-feuille ; >4. Ses performances de recherche sont équivalentes à une recherche binaire dans l'ensemble complet de mots-clés

5. Contrôle hiérarchique automatique

B+Tree

Différents moteurs de stockage peuvent utiliser différentes structures de données pour le stockage. InnoDB utilise B+Tree

Alors, qu'est-ce que B+Tree ?

B+Tree est une variante de B-Tree requise par le système de fichiers. La différence entre un arbre B+ d'ordre m et un arbre B d'ordre m est :

B+. et B- (c'est-à-dire B) sont dus au fait que les mots-clés sur chaque nœud sont différents. Un de plus, un de moins.

Pour l'arbre B+, sa structure de nœuds est la même que pour l'arbre B. La différence réside dans le mot-clé de chaque nœud et le nombre de nœuds enfants qu'il peut avoir. Par exemple, dans un arbre B+ d’ordre m, chaque nœud peut avoir au plus m nœuds enfants. Les nœuds non racines ont au moins [m/2] nœuds enfants et le nombre de mots-clés est supérieur d'un à celui de B-tree, qui est de [m/2]~m.

Les différences entre ces deux structures de données pour la gestion des index :

1. La même valeur de clé n'apparaîtra pas plusieurs fois dans le B-tree et peut apparaître dans des nœuds feuilles ou des nœuds non feuilles. Les clés de l'arbre B+ apparaîtront certainement dans les nœuds feuilles, et peuvent également apparaître de manière répétée dans les nœuds non-feuilles pour maintenir l'équilibre de l'arbre B+.

2. Étant donné que la position de la clé du B-tree est incertaine et n'apparaît qu'une seule fois dans toute la structure arborescente, bien qu'elle puisse économiser de l'espace de stockage, elle augmente considérablement la complexité des opérations d'insertion et de suppression. Les arbres B+ sont un meilleur compromis en comparaison.

3. L'efficacité des requêtes de l'arbre B est liée à la position de la clé dans l'arbre. La complexité temporelle maximale est la même que celle de l'arbre B+ (lorsqu'il se trouve au nœud feuille) et la complexité temporelle minimale est de 1 (lorsque c'est au nœud racine). La complexité temporelle de l’arbre B+ est fixée pour un certain arbre construit.

Pour plus d'articles techniques liés à MySQL, veuillez visiter la colonne

Tutoriel graphique de base de données MySQL

pour apprendre !

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!