Quel est le principe de l'index btree

Le principe de l'index btree est que l'arbre binaire conduit à une hauteur d'arbre très élevée. Les nœuds qui sont très proches logiquement sont très éloignés physiquement et ne peuvent pas profiter de la localité. Le nombre d'IO est élevé et le nombre d'IO est élevé. l'efficacité de la recherche est faible ; Btree est un arbre de recherche "m" équilibré, qui peut utiliser plusieurs nœuds de branche pour réduire le nombre de nœuds rencontrés lors de l'interrogation des données.

Principe de l'index BTree

L'arbre binaire entraîne une hauteur d'arbre très élevée et des nœuds logiquement proches, physiquement très loin, incapable de profiter de la localité, des temps d'E/S élevés, une faible efficacité de recherche

Btree est un arbre de recherche m-way équilibré, qui peut utiliser plusieurs nœuds de branche (nœuds de sous-arbre) pour réduire les requêtes Le nombre de nœuds que les données ont connu, économisant ainsi le temps d'accès. m est appelé le degré du B-Tree.

L'arbre B peut être vu comme une extension de l'arbre de recherche 2-3, c'est-à-dire qu'il permet à chaque nœud d'avoir des nœuds enfants M-1.

Caractéristiques

• a un nœud racine, le nœud racine n'a qu'un seul enregistrement et deux enfants ou le nœud racine est vide

  ;

• La clé et le pointeur dans chaque enregistrement de nœud sont espacés les uns des autres, et le pointeur pointe vers le nœud enfant

• d représente la largeur de ; l'arbre, à l'exception des nœuds feuilles, autres Chaque nœud a [d/2,d-1] enregistrements, et les clés de ces enregistrements sont classées par taille de gauche à droite, et il y a [d/2+1,d] children;

• Dans un nœud, toutes les clés du n-ème sous-arbre sont inférieures à la n-ème clé de ce nœud et supérieures à la n-1ème clé ; 🎜>

Tous les nœuds feuilles doivent être au même niveau, c'est-à-dire qu'ils ont la même profondeur
En raison des caractéristiques de B-Tree, l'algorithme ; pour récupérer des données par clé dans B-Tree est très intuitif : Effectuez d'abord une recherche binaire à partir du nœud racine. S'il est trouvé, les données du nœud correspondant sont renvoyées. Sinon, le nœud pointé par le pointeur dans l'intervalle correspondant est recherché. récursivement jusqu'à ce que le nœud soit trouvé ou que le pointeur nul soit trouvé. La première recherche réussit et la seconde échoue.
Recommandé : "

"

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!