Quelle est la structure des données de l'index mysql

1. Introduction

La structure des données de l'index mysql est un arbre, et le moteur de stockage couramment utilisé innodb utilise B+Tree. Voici une brève introduction à B+Tree et à ses

arbres de recherche associés.

2. Divers arbres de recherche

1. Arbre de tri binaire (également appelé arbre de recherche binaire)

Arbre de tri binaire est l'arbre de recherche le plus simple Caractéristiques :

a) C'est un arbre binaire

b) La valeur de tous les nœuds du sous-arbre de gauche est inférieure à celle de son nœud parent Value ; la valeur de tous les nœuds du sous-arbre droit est supérieure à la valeur de son nœud parent.

2. Arbre binaire équilibré (également connu sous le nom d'arbre AVL)

L'arbre binaire équilibré est basé sur l'arbre de tri binaire et limite la profondeur de l'arbre, ainsi réduire Trouver le nombre de comparaisons,

Caractéristiques :

a) est un arbre binaire

b) la valeur de tous les nœuds du sous-arbre de gauche est inférieure à la valeur ; de son nœud parent, les valeurs de tous les nœuds du sous-arbre droit sont supérieures aux valeurs de ses nœuds parents

c) La différence de profondeur entre le sous-arbre gauche et le sous-arbre droit est comprise entre - ; 1, 0, 1, sinon le sous-arbre est Ajustement de rotation.

3. B-Tree (B-Tree)

B-tree est un arbre de recherche équilibré à plusieurs voies Comparé à l'arbre binaire équilibré, l'enfant direct. du nœud parent Le nombre de nœuds n'est plus limité à 2.

peut spécifier m (personnalisé), afin que plus de nœuds puissent être enregistrés sans augmenter considérablement la profondeur de l'arborescence.

B-tree est couramment utilisé dans les systèmes de fichiers.

Caractéristiques :

a) Chaque nœud de l'arbre a au plus m nœuds enfants (personnalisés)

b) Si le nœud racine n'est pas un nœud feuille, alors il y a au moins deux nœuds enfants ;

c) Tous les nœuds non-feuilles à l'exception du nœud racine, au moins m/2, prennent le nœud enfant entier

d) Le nœud parent Les valeurs ; ​​de tous les nœuds du sous-arbre le plus à gauche ci-dessous sont inférieures à la valeur minimale du nœud parent,

les valeurs de tous les nœuds du sous-arbre le plus à droite sont supérieures à la valeur maximale du nœud parent,

et le reste au milieu Les valeurs de tous les nœuds du sous-arbre sont entre les valeurs des deux côtés du nœud parent du pointeur

e) Tous les nœuds feuilles sont ; au même niveau ;

Remarque : Tous les nœuds ont une valeur

B+Tree (B+Tree)

L'arbre B+ est une variante. de B-tree. Par rapport à B-tree, la valeur du nœud feuille inclut Toutes les valeurs et les valeurs de tous les nœuds parents sont des valeurs répétées des nœuds feuilles

Le nœud parent joue uniquement. le rôle de recherche d'index, et tous les nœuds feuilles forment également une liste chaînée ordonnée.

Le moteur de stockage dans MySQL est l'index d'Innodb, et la structure de données utilisée est l'arborescence B+.

Caractéristiques :

a) Le nœud parent avec m nœuds enfants a m mots-clés

b) Tous les nœuds feuilles contiennent tous les mots-clés (valeur) et forment un lien ordonné ; liste de petit à grand ;

c) Tous les nœuds non-feuilles servent d'index, et les nœuds ne contiennent que la valeur maximale de tous les nœuds du sous-arbre ;

d) Tous les nœuds feuilles sont au même niveau ;

Remarque : les nœuds feuilles contiennent tous les mots-clés (valeurs).

5. B*Tree (B*Tree)

L'arbre B* est une variante de l'arbre B+. Par rapport à l'arbre B+, il ajoute la prise en charge des arbres non-feuilles. les nœuds de la même couche, les pointeurs vers des points, c'est-à-dire les nœuds non-feuilles au même niveau, forment également une liste chaînée.

3. Résumé

Pour résumer, les arbres de recherche ci-dessus sont liés les uns aux autres.

Cela se résume à l'index innodb dans MySQL. Il utilise un arbre B+, tel qu'un index clusterisé, qui agrège les données via la clé primaire et utilise un arbre B+ pour l'implémenter.

C'est un. index et également Une structure de stockage de données de mysql. Les nœuds feuilles contiennent toutes les données, et les nœuds non-feuilles ne servent que d'index (si

ne définit pas de clé primaire, innodb définira implicitement une clé primaire en tant que cluster. indice ).

Pour plus d'articles techniques liés à MySQL, veuillez visiter la colonne Tutoriel 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!