Quelle est la raison pour laquelle l'index MySQL est rapide ?

En pré-triant, l'index peut être recherché à l'aide d'algorithmes à haute efficacité tels que la recherche binaire. La complexité de la recherche séquentielle générale est O(n), tandis que la complexité de la recherche binaire est O(log2n) ; lorsque n est très grand, la différence d'efficacité entre les deux est énorme.

Mysql est une base de données très populaire sur Internet. La conception de son moteur de stockage sous-jacent et de son moteur de récupération de données est très importante, en particulier la forme de stockage des données Mysql et la conception de l'index. , qui détermine les performances globales de récupération des données de Mysql.

Nous savons que la fonction d'un index est de récupérer rapidement des données, et l'essence d'une récupération rapide est la structure des données. Grâce à la sélection de différentes structures de données, diverses données peuvent être rapidement récupérées. Dans une base de données, des algorithmes de recherche efficaces sont très importants, car une grande quantité de données est stockée dans la base de données et un index efficace peut faire gagner énormément de temps. Par exemple, dans le tableau de données suivant, si Mysql n'implémente pas l'algorithme d'indexation, alors pour trouver les données avec id=7, vous ne pouvez utiliser qu'un parcours séquentiel violent pour trouver les données. Pour trouver les données avec id=7, vous pouvez uniquement utiliser un parcours séquentiel violent pour trouver les données. Il faut le comparer 7 fois. Si ce tableau stocke 10 millions de données. Pour rechercher les données avec id=1000W, elles seront comparées 1000W fois. Cette vitesse est inacceptable.

1. 🎜#

Hash table (Hash)

Hash table est un outil efficace pour une récupération rapide des données.

Algorithme de hachage : également appelé algorithme de hachage, il convertit n'importe quelle valeur (clé) en une adresse de clé de longueur fixe via une fonction de hachage et utilise cette adresse pour créer une structure de données pour des données spécifiques.

Considérez cet utilisateur de table de base de données Il y a un total de 7 données dans. la table. Nous devons récupérer les données avec id=7. La syntaxe SQL est :

select * from user where id=7;

L'algorithme de hachage calcule d'abord l'adresse physique des données qui stockent id=7 addr=hash(7) =4231, et l'adresse physique du mappage 4231 L'adresse est 0x77, 0x77 est l'adresse physique des données stockées par id=7. Les données correspondant à user_name='g' peuvent être trouvées via cette adresse indépendante. Il s'agit du processus de calcul utilisé par l'algorithme de hachage pour récupérer rapidement les données.

Cependant, l'algorithme de hachage a un problème de collision de données, c'est-à-dire que la fonction de hachage peut calculer le même résultat pour différentes clés, comme hash(7) peut calculer le résultat avec hash(199) Le pareil, c'est-à-dire que différentes clés sont mappées au même résultat. Il s'agit d'un problème de collision. Un moyen courant de résoudre le problème de collision est la méthode d'adresse en chaîne, qui utilise une liste chaînée pour connecter les données en collision. Après avoir calculé la valeur de hachage, vous devez également vérifier si la valeur de hachage a une collision dans la liste chaînée des données. Si tel est le cas, elle sera parcourue jusqu'à la fin de la liste chaînée jusqu'à ce que les données correspondant à la vraie clé soient trouvées.

D'après l'analyse de la complexité temporelle de l'algorithme, la complexité temporelle de l'algorithme de hachage est O(1) et la vitesse de récupération est très rapide. Par exemple, lors de la recherche de données avec id=7, l'index de hachage ne doit être calculé qu'une seule fois pour obtenir les données correspondantes, et la vitesse de récupération est très rapide. Mais Mysql n'utilise pas le hachage comme algorithme sous-jacent. Pourquoi ?

Considérant qu'une méthode courante de récupération de données est la recherche par plage, comme l'instruction SQL suivante :

select * from user where id \>3;

Pour l'instruction ci-dessus, ce que nous espérons faire est de découvrir id> 3 données, il s'agit d'une recherche de plage très typique. Si vous utilisez un index implémenté par un algorithme de hachage, comment effectuer une recherche par plage ? Une idée simple consiste à rechercher toutes les données en même temps et à les charger dans la mémoire, puis à filtrer les données dans la plage cible de la mémoire. Mais cette méthode de recherche de plage est trop lourde et pas du tout efficace.

Par conséquent, bien que l'index implémenté à l'aide de l'algorithme de hachage puisse récupérer rapidement des données, il ne peut pas effectuer une recherche de plage efficace des données. Par conséquent, l'index de hachage ne convient pas en tant que structure de données pour l'index sous-jacent. MySQL.

Arbre de recherche binaire (BST)

L'arbre de recherche binaire est une structure de données qui prend en charge la recherche rapide de données, comme le montre la figure ci-dessous :

Complexité temporelle de l'arbre de recherche binaire C'est O (lgn). Par exemple, pour la structure arborescente binaire ci-dessus, nous devons calculer et comparer trois fois pour récupérer les données avec id=7. Par rapport à la requête de traversée directe, cela permet d'économiser la moitié du temps. il semble que cela puisse être réalisé. De plus, la structure de l'arbre binaire peut-elle résoudre la fonction de recherche de plage que l'index de hachage ne peut pas fournir ?

La réponse est oui. Observez l'image ci-dessus. Les nœuds feuilles de l'arbre binaire sont disposés dans l'ordre croissant de gauche à droite. Si nous avons besoin de trouver les données avec id>5, alors nous pouvons simplement supprimer le nœud avec le nœud 6 et son. sous-arbre droit, la recherche par plage est relativement facile à mettre en œuvre.

Mais les arbres de recherche binaires ordinaires ont un défaut fatal : dans les cas extrêmes, ils dégénéreront en listes chaînées linéaires, la recherche binaire dégénérera également en recherche traversante, la complexité temporelle dégénérera en O(N) et les performances de récupération chuteront. nettement. Par exemple, dans la situation suivante, l'arbre binaire est extrêmement déséquilibré et a dégénéré en une liste chaînée, et la vitesse de récupération est considérablement réduite. À l’heure actuelle, le nombre de calculs requis pour récupérer les données avec id=7 est passé à 7.

Dans la base de données, l'auto-incrémentation des données est une forme très courante. Par exemple, la clé primaire d'une table est id, et la clé primaire est généralement auto-incrémentée par défaut. Une structure comme un arbre binaire est utilisée comme index, alors le problème de recherche linéaire causé par l'état déséquilibré introduit ci-dessus se produira inévitablement. Par conséquent, un simple arbre de recherche binaire présente le problème de performances de récupération réduites causées par un déséquilibre et ne peut pas être directement utilisé pour implémenter l'index sous-jacent de Mysql.

Arbres AVL et arbres rouge-noir

Les arbres de recherche binaires ont des problèmes de déséquilibre. Par conséquent, les chercheurs ont proposé que grâce à la rotation et à l'ajustement automatiques des nœuds de l'arbre, l'arbre de recherche binaire puisse être maintenu dans un état fondamentalement équilibré. meilleures performances de recherche. Les arbres binaires équilibrés auto-ajustables basés sur cette idée comprennent les arbres AVL et les arbres rouge-noir.

Tout d'abord, nous présentons brièvement l'arbre rouge-noir. Il s'agit d'une structure arborescente qui ajuste automatiquement la forme de l'arbre. Par exemple, lorsque l'arbre binaire est dans un état déséquilibré, l'arbre rouge-noir pivote automatiquement vers la gauche et. Les nœuds de droite et les nœuds changeront de couleur pour ajuster la forme de l'arbre, afin de maintenir un état d'équilibre de base (la complexité temporelle est O (logn)), ce qui garantit que l'efficacité de la recherche ne sera pas réduite de manière significative. Par exemple, si les nœuds de données sont insérés dans l'ordre croissant de 1 à 7, un arbre de recherche binaire ordinaire dégénérera en une liste chaînée, mais un arbre rouge-noir ajustera continuellement la forme de l'arbre pour maintenir un équilibre de base, comme illustré. dans la figure ci-dessous. Le nombre de nœuds à comparer lors de la recherche de id=7 dans l'arbre rouge-noir ci-dessous est de 4, ce qui maintient toujours la bonne efficacité de recherche de l'arbre binaire.

L'arbre rouge-noir a une bonne efficacité de recherche moyenne, et il n'y a pas de situation O(n) extrême. Alors, l'arbre rouge-noir peut-il être utilisé comme implémentation d'index sous-jacente de Mysql ? En fait, les arbres rouge-noir ont aussi quelques problèmes. Regardez l’exemple suivant.
L'arbre rouge-noir insère 1 à 7 nœuds séquentiellement et le nombre de nœuds qui doivent être calculés lors de la recherche de id=7 est de 4.

L'arbre rouge-noir insère séquentiellement 1 à 16 nœuds, et le nombre de nœuds qui doivent être comparés pour trouver l'identifiant = 16 est 6 fois. Observez la forme de cet arbre. Est-il vrai que lorsque les données sont insérées de manière séquentielle, la forme de l'arbre a toujours été dans une tendance « à droite » ? Fondamentalement, l'arbre rouge-noir ne résout pas complètement l'arbre de recherche binaire. Bien que cette tendance « à droite » soit beaucoup moins exagérée que l'arbre de recherche binaire dégénérant en une liste chaînée linéaire, l'opération de base d'auto-incrémentation de clé primaire dans le base de données, la clé primaire est généralement des millions et des dizaines de millions. Si l'arbre rouge-noir a ce genre de problème, cela consommera également énormément de performances de recherche. Notre base de données ne peut pas tolérer cette attente inutile.

Considérons maintenant un autre arbre binaire à auto-équilibrage plus strict, l'arbre AVL. Étant donné que l'arbre AVL est un arbre binaire absolument équilibré, il consomme plus de performances pour ajuster la forme de l'arbre binaire.

L'arbre AVL insère 1 à 7 nœuds séquentiellement, et le nombre de fois où comparer les nœuds pour trouver l'identifiant = 7 est de 3.

L'arborescence AVL insère séquentiellement 1 à 16 nœuds, et le nombre de nœuds qui doivent être comparés pour trouver l'identifiant = 16 est de 4. En termes d'efficacité de recherche, la vitesse de recherche de l'arbre AVL est supérieure à celle de l'arbre rouge-noir (l'arbre AVL est de 4 comparaisons, l'arbre rouge-noir est de 6 comparaisons). À en juger par la forme de l'arbre, les arbres AVL n'ont pas le problème de « bonne inclinaison » des arbres rouge-noir. En d'autres termes, un grand nombre d'insertions séquentielles n'entraînera pas de diminution des performances des requêtes, ce qui résout fondamentalement le problème des arbres rouge-noir.

Pour résumer les avantages de l'arbre AVL :

1. Bonnes performances de recherche (O(logn)), il n'y a pas de situation de recherche extrêmement inefficace.
   

2. Peut réaliser une recherche par plage et un tri de données.
   

Il semble que l'arborescence AVL soit vraiment bonne comme structure de données pour la recherche de données, mais l'arborescence AVL ne convient pas à la structure de données d'index de la base de données Mysql, car considérez ce problème :

Le goulot d'étranglement de la base de données Les données de requête sont des E/S de disque. Si nous utilisons une arborescence AVL, chacun de nos nœuds d'arborescence ne stocke qu'une seule donnée. Nous ne pouvons extraire les données que sur un seul nœud et les charger en mémoire avec une E/S de disque. interrogez les données avec id=7, nous devons effectuer trois fois les E/S sur le disque, ce qui prend beaucoup de temps. Par conséquent, lors de la conception d’index de base de données, nous devons d’abord réfléchir à la manière de réduire autant que possible le nombre d’E/S disque.

Une caractéristique des E/S du disque est que le temps nécessaire pour lire 1 Mo de données et 1 Ko de données à partir du disque est fondamentalement le même. Sur la base de cette idée, nous pouvons stocker autant de données que possible sur un nœud d'arborescence. Un disque IO se charge. plus de données dans la mémoire. C'est le principe de conception du B-tree et du B+-tree.

Arbre B

L'arbre B suivant est limité au stockage de jusqu'à deux clés par nœud. Si un nœud a plus de deux clés, il sera automatiquement divisé. Par exemple, le B-tree suivant stocke 7 données. Il vous suffit d'interroger deux nœuds pour connaître l'emplacement spécifique des données avec id=7. Autrement dit, vous pouvez interroger les données spécifiées avec deux E/S de disque, ce qui est mieux que. l'arborescence AVL.

Ce qui suit est un arbre B qui stocke 16 éléments de données. De même, chaque nœud stocke jusqu'à 2 clés. L'interrogation des données avec id=16 nécessite d'interroger et de comparer 4 nœuds, ce qui signifie 4. le disque passe. On dirait que les performances des requêtes sont les mêmes que celles de l'arborescence AVL.

Mais étant donné que le temps consommé par les E/S du disque pour lire une donnée est fondamentalement le même que pour lire 100 données, alors notre idée d'optimisation peut être modifiée comme suit : lire autant de données que possible dans un disque IO mémoire. Cela se reflète directement dans la structure de l'arborescence, c'est-à-dire que la clé que chaque nœud peut stocker peut être augmentée de manière appropriée.

Lorsque nous fixons à 6 le nombre de clés limitées à un seul nœud, pour un B-tree qui stocke 7 éléments de données, l'E/S disque requise pour interroger les données avec id=7 est de 2 fois.

Un B-tree qui stocke 16 éléments de données L'E/S disque requise pour interroger les données avec id=. 7 est 2 fois. Par rapport à l’arborescence AVL, le nombre d’E/S disque est réduit de moitié.

Donc, en termes de sélection des données d'index de base de données structure, B-tree est un très bon choix. En résumé, B-tree présente les avantages suivants lorsqu'il est utilisé comme index de base de données :

1. Excellente vitesse de récupération, complexité temporelle : B- recherche dans l'arbre La performance est égale à O(h*logn), où h est la hauteur de l'arbre et n est le nombre de mots-clés dans chaque nœud
   

2. #🎜🎜 ;

   
   

3. peut prendre en charge les recherches par plage.

   
   

4. B+tree

   
   

B arbre et B+ En quoi les arbres sont-ils différents ?

Premièrement, Un nœud dans l'arbre B stocke des données, tandis que l'arbre B+ stocke un index (adresse), donc un nœud dans l'arbre B Il ne peut pas stocker beaucoup de données, mais un nœud de l'arborescence B+ peut stocker de nombreux index, et les nœuds feuilles de l'arborescence B+ stockent toutes les données.

Deuxièmement, les nœuds feuilles de l'arbre B+ sont connectés en série avec une liste chaînée au stade des données pour faciliter la recherche de plage.

En comparant B-tree et B+ tree, on peut voir que B+ tree Les nœuds stockent des index. Lorsque la capacité de stockage d'un seul nœud est limitée, un seul nœud peut également stocker un grand nombre d'index, ce qui réduit la hauteur de l'ensemble de l'arborescence B+ et réduit les E/S du disque. Deuxièmement, les nœuds feuilles de l'arborescence B+ sont l'endroit où les données réelles sont stockées. Les nœuds feuilles sont connectés à l'aide d'une liste chaînée. La liste chaînée elle-même est ordonnée et est plus efficace lors de la recherche dans la plage de données. Par conséquent, l'index de MySQL utilise l'arbre B+ et offre de très bonnes performances en termes d'efficacité de recherche et de recherche par plage.

2. Implémentation du moteur Innodb et du moteur Myisam

Le moteur de données sous-jacent Mysql est conçu sous forme de plug-ins, les plus courants Il s'agit du moteur Innodb et du moteur Myisam, les utilisateurs peuvent choisir différents moteurs en fonction de leurs besoins personnels comme moteur sous-jacent de la table de données Mysql. Nous venons d'analyser que l'arbre B+ est très approprié comme structure de données de l'index Mysql, mais la façon d'organiser les données et l'index nécessite également une certaine conception. La différence dans les concepts de conception a également conduit à l'émergence d'Innodb et de Myisam, chacun présentant des performances uniques. .

MyISAM Bien que les performances de recherche de données soient excellentes, elles ne prennent pas en charge le traitement des transactions. La plus grande caractéristique d'Innodb est qu'il prend en charge les fonctions de transaction compatibles ACID et qu'il prend en charge les verrous au niveau des lignes. Vous pouvez spécifier le moteur lorsque Mysql crée une table. Par exemple, dans l'exemple suivant, Myisam et Innodb sont spécifiés respectivement comme moteurs de données pour la table user et la table user2.

Après avoir exécuté ces deux instructions, les fichiers suivants apparaissent dans le système, indiquant que les données et index des deux moteurs sont organisés différemment.

Innodb Les fichiers générés après la création de la table sont :

# 🎜🎜#

frm : Instruction pour créer la table

• 
  

  idb : Données + fichier d'index dans le tableau

• 
  

  Myisam Les fichiers générés après la création du tableau sont

#🎜🎜 #frm : Instruction pour créer une table

• 
  MYD : Fichier de données dans la table (données myisam)

• MYI : Fichier d'index (index myisam) dans le tableau
  

D'après les fichiers générés, il semble que les données et l'index sous-jacents des deux moteurs soient organisés différemment. La personne possède un fichier, appelé méthode d'index non clusterisé ; le moteur Innodb place les données et l'index dans le même fichier, appelé méthode d'index clusterisé. Ce qui suit analysera comment ces deux moteurs s'appuient sur la structure de données arborescente B+ pour organiser la mise en œuvre du moteur du point de vue de la mise en œuvre sous-jacente.

L'implémentation sous-jacente du moteur MyISAM (méthode d'index non clusterisée)

MyISAM utilise une méthode d'index non clusterisée, c'est-à-dire que les données et l'index tombent sur deux fichiers différents. Lorsque MyISAM crée une table, il utilise la clé primaire comme KEY pour créer une arborescence d'index primaire B+. Les nœuds feuilles de l'arborescence stockent l'adresse physique des données correspondantes. Après avoir obtenu cette adresse physique, nous pouvons localiser directement l'enregistrement de données spécifique dans le fichier de données MyISAM.

Lorsque nous ajoutons un index à un champ, nous générerons également un arbre d'index pour le champ correspondant. Les nœuds feuilles de l'arbre d'index pour le champ enregistrent également l'adresse physique des données correspondantes, puis prenez Utiliser cette adresse physique pour localiser l'enregistrement de données spécifique dans le fichier de données.

L'implémentation sous-jacente du moteur Innodb (méthode d'index clusterisé)

InnoDB est une méthode d'index clusterisé, donc les données et l'index sont stockés dans le même fichier. Tout d'abord, InnoDB construira un arbre d'index B+ basé sur l'ID de clé primaire comme KEY, comme le montre la figure en bas à gauche. Les nœuds feuilles de l'arborescence B+ stockent les données correspondant à l'ID de clé primaire, par exemple, lors de l'exécution de l'instruction. select * from user_info which id=15, InnoDB Il interrogera l'arborescence B+ de l'index d'ID de clé primaire et trouvera le user_name='Bob' correspondant.

C'est à ce moment-là qu'InnoDB construira automatiquement l'arborescence d'index d'ID de clé primaire lors de la création d'une table. C'est pourquoi Mysql nécessite que la clé primaire soit spécifiée lors de la création d'une table. Comment InnoDB construit-il un arbre d'index lorsque nous ajoutons un index à un champ de la table ? Par exemple, si nous voulons ajouter un index au champ user_name, alors InnoDB créera un arbre B+ d'index de nom d'utilisateur. La KEY de user_name est stockée dans le nœud et les données stockées dans les nœuds feuilles sont la clé primaire KEY. Notez que les feuilles stockent la clé primaire KEY ! Après avoir obtenu la clé primaire KEY, InnoDB ira à l'arborescence d'index de clé primaire pour trouver les données correspondantes en fonction de la clé primaire KEY qui vient d'être trouvée dans l'arborescence d'index de nom_utilisateur.

La question est de savoir pourquoi InnoDB stocke uniquement des données spécifiques dans les nœuds feuilles de l'arborescence d'index de clé primaire, alors que les autres arbres d'index ne stockent pas de données spécifiques et qu'il n'est pas nécessaire de trouver d'abord la clé primaire. , puis dans l'arborescence d'index de clé primaire. Que diriez-vous de trouver les données correspondantes ?

C'est en fait très simple, car InnoDB a besoin d'économiser de l'espace de stockage. Il peut y avoir plusieurs index dans une table. InnoDB générera un arbre d'index pour chaque champ indexé. Si l'arbre d'index de chaque champ stocke des données spécifiques, alors le fichier de données d'index de cette table deviendra très volumineux (données extrêmement redondantes). Du point de vue de l'économie d'espace disque, il n'est vraiment pas nécessaire de stocker des données spécifiques dans chaque arborescence d'index de champ. Grâce à cette étape apparemment « inutile », un espace disque énorme est économisé au détriment des performances des requêtes.

Lors de la comparaison des fonctionnalités d'InnoDB et de MyISAM, il a été mentionné que MyISAM a de meilleures performances de requête. La raison peut également être vue dans la conception du fichier de données du fichier d'index ci-dessus : MyISAM peut localiser directement l'enregistrement de données après avoir directement trouvé le physique. adresse, mais après qu'InnoDB ait interrogé les nœuds feuilles, il doit à nouveau interroger l'arborescence d'index de clé primaire pour localiser les données spécifiques. Cela signifie que MyISAM peut trouver les données en une seule étape, mais InnoDB nécessite deux étapes. Bien entendu, les performances des requêtes de MyISAM sont plus élevées.

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!