Le principe de l'index MySQL

La base de données MySQL prend en charge une variété d'index, tels que les index B-tree, les index de hachage, les index de texte intégral, etc. Cet article se concentre sur les index B-tree. (Recommandé : "Tutoriel MySQL")

Principe et essence de l'index

Explication officielle MySQL : L'index est une donnée qui améliore l'efficacité de l'acquisition de données pour la structure MySQL pour une interrogation rapide des données. Les index sont des structures de données qui satisfont un algorithme de recherche spécifique, et ces structures de données pointent vers les données d'une certaine manière pour réaliser une recherche de données efficace.

Arbre B+

MySQL utilise généralement l'arbre B+ comme structure d'index, alors quelles sont les caractéristiques de l'arbre B+ ?

Si le degré de l'arbre est n, la limite supérieure de chaque pointeur de nœud est 2n+1

Les nœuds non-feuilles ne stockent pas de données, seuls les index de pointeur stockent toutes les données, pas ; pointeurs

Un pointeur d'accès séquentiel est ajouté sur la base de l'arborescence B+ classique. Chaque nœud feuille a un pointeur vers le nœud feuille adjacent suivant, comme le montre la figure. Principalement pour améliorer les performances de l'accès par intervalles. Par exemple, si vous souhaitez trouver toutes les données avec les clés 20 à 50, il vous suffit d'accéder à tous les nœuds de données en même temps selon la route d'accès séquentielle.

Arborescence B+ à accès séquentiel

Principe de localité et lecture anticipée du disque

Alors pourquoi Base de données ? les systèmes utilisent généralement des arbres B+ comme structures d'index, au lieu d'autres structures telles que des arbres rouge-noir ?

Tout d’abord, introduisons le principe de localité et la notion de lecture anticipée du disque.

D'une manière générale, l'index lui-même est volumineux et ne sera pas entièrement stocké en mémoire, mais sera stocké sur disque sous la forme d'un fichier d'index. Par conséquent, les opérations d'E/S disque se produiront pendant le processus de recherche d'index, et les E/S disque sont très lentes par rapport à l'accès à la mémoire, la structure de l'index doit donc minimiser le nombre d'accès aux E/S disque.

Afin de réduire les E/S du disque, le disque effectue souvent une pré-lecture des données, en commençant à partir d'une certaine position et en pré-levant une certaine longueur de données vers l'arrière dans la mémoire, ce qui est le principe de localité. Étant donné que la lecture séquentielle du disque est plus efficace et ne nécessite pas de temps de recherche, elle peut améliorer l'efficacité des E/S.

La longueur de lecture anticipée est généralement un multiple entier de la page, et la mémoire principale et le disque échangent des données en unités de pages. Lorsque les données à lire ne sont pas dans la mémoire, une interruption de défaut de page est déclenchée. Le système envoie une demande au disque pour lire les données du disque. Le disque trouve la position de départ des données et en lit en continu une ou. plusieurs pages de données en arrière et les charge dans la mémoire. Ensuite, l'interruption revient et le système continue de fonctionner. Lors de la conception d'un système de base de données général, la taille du nœud de l'arborescence B+ est définie sur une page, de sorte que le chargement de chaque nœud ne nécessite qu'une seule E/S.

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!