Type Mysql-index-BTree [simplifié]

J'ai lu beaucoup de résumés sur B-TREE sur Internet, b-tree, B-tree, B-tree, B*-tree (pourquoi Emma en a encore 4 ? Elle est presque confuse),

Certains d'entre eux sont vraiment passionnants et admirables, mais ils sont tous trop longs. Un long paragraphe de texte est intimidant. Faisons simplement une version simplifiée du résumé, présentons-le de manière simple et mobile et parlons de leurs différences.
1. L'arbre B

L'arbre binaire est un arbre binaire. (Les formules pour K, h et n ne seront pas abordées ici. Si vous êtes intéressé, vous pouvez les rechercher vous-même..)

(1) Tous les non- nœuds feuilles Avoir au plus deux fils (Gauche et Droite

(2) Tous); stockage de nœudsUn mot-clé;

(3) Le pointeur gauche d'un nœud non-feuille pointe vers moins que sa clé Le sous-arbre d'un mot, le pointeur droit pointe vers le sous-arbre plus grand que son mot-clé (En termes simples, Le côté gauche est plus petit que lui et le côté droit est plus grand que lui)

FigurineArbre B

Deux.B-Tree

Arbre binaire d'équilibre --Arbre AVL [Le B ici signifie en fait équilibre~]

( 1) La profondeur du sous-arbre gauche et du sous-arbre droit du nœud racine diffère au maximum de 1 (cela garantit qu'il ne se produira pas de phénomène extrême sur le. côté droit de l'image ci-dessus)

(2) Le sous-arbre gauche et le sous-arbre droit du nœud racine sont tous deux un arbre binaire équilibré .

(3) Tous les nœuds stockent mots-clés ;

Quelle que soit la séquence insérée, nous pouvons construire un arbre binaire équilibré grâce à des ajustements pour garantir que le facteur d'équilibre de chaque nœud de l'arbre binaire ne sera pas supérieur à 1,

garantit que la profondeur de l'arbre atteint le moins profond , donc le nombre de comparaisons sera moindre et la complexité temporelle sera réduite

Figure B-Tree

Arbre Trois.B

La recherche de B est fondamentalement la même que celle de B-tree. La différence est que B-tree n'atteint que le nœud feuille (B-tree peut frapper des nœuds non-feuilles)

(1) Tous les mots-clés apparaissent dans la liste chaînée des nœuds feuilles (index dense), et les mots-clés de la liste chaînée sont ordonnés ( ; Seul le nœud racine stocke le mot-clé et la fin du dernier arbre a une valeur )

(2) Non- les nœuds feuilles sont équivalents aux nœuds feuilles Index (index clairsemé), les nœuds feuilles sont équivalents à la couche de données qui stocke les données (mot-clé). ( les nœuds non racine stockent en fait l'index pointant vers le nœud racine )

(3 ) En raison des deux premiers points, il est impossible pour de stocker des données dans des nœuds non feuilles. (La troisième différence entre B-)

(4) Le nœud racine a également un pointeur de chaîne horizontalement (il est pratique de suivre les indices rapidement, mais un tel pointeur n'existe pas, même si la valeur suivante est un voisin adjacent, il faut courir en cercle pour l'obtenir)

Notez que la plupart des résultats d'index que nous utilisons généralement, ou la structure B-TREE à laquelle nous faisons habituellement référence, font référence à la structure B~~

Image B Arbre

L'arbre Quatre B*
est un B Variations de l'arbre,

(1)B Les nœuds non-racine et non-feuille de l'arbre ajoutent des pointeurs vers les frères [Comparez au point 4 de B ci-dessus, dans le non-root Le nœud ajoute également une liste chaînée horizontale]

Photo B * Arbre

5. Résumé :

Arbre B : arbre binaire,

chaque nœud Un seul mot-clé est stocké. S'il est égal, il frappera. S'il est plus petit, il ira au nœud de gauche, s'il est plus grand, il ira au nœud de droite ( Mais après plusieurs insertions et suppressions, le B-tree peut conduire à des structures différentes ), pour cette raison, un arbre binaire équilibré est généré après l'ajout de l'algorithme d'équilibrage, également connu sous le nom de B-tree

B-tree : basé sur le B-tree, plus l'algorithme d'équilibrage et l'arbre de recherche multi-chemins ,

1. Chaque nœud stocke M/ 2 à M mots-clés,

2. nœuds enfants pointant vers la plage de mots-clés ;

3. Tous Le mot-clé apparaît dans l'ensemble de l'arborescence et n'apparaît qu'une seule fois,

4. les nœuds feuilles et les nœuds non feuilles peuvent être touchés (que les données soient stockées

) ;

B-tree : basé sur B-tree,

1. Ajouter un pointeur de liste chaînée au nœud feuille

2. Tous les mots-clés apparaissent dans les nœuds feuilles,

3. Les nœuds non-feuilles servent d'index aux nœuds feuilles

4. le nœud feuille ; :

Basé sur le B-tree, le pointeur de liste chaînée

est également ajouté aux

nœuds non-feuilles, et l'utilisation minimale du nœud est augmentée de 1/2 à 2/3

Question :
B* est plus efficace, mais pourquoi pensez-vous que les arbres b* sont moins utilisés ? ????Ou où est-ce utile ? ?

Peut-être que je vois encore trop peu. . Les chaussures pour enfants qui savent quelque chose peuvent apprendre les unes des autres, donnez-moi quelques conseils, merci d'avance ~

Réponse :

J'ai récemment appris qu'il y avait une personne nommée

Le système de fichiers de Reiser4 semble utiliser cette structure. Son auteurHans Reiser, parce que sa femme l'a fait cocu, il a tué sa femme et est allé en prison, ce qui a directement affecté l'avancement du projet. . .

Introduction :

Système de fichiers Linux ReiserFS Après que l'auteur Hans Reiser ait été condamné à 15 ans de prison pour le meurtre de sa femme, le développement de ReiserFS ne s'est pas arrêté, bien que il n'a pas encore été fusionné. Accédez à la branche principale Linux. Un petit groupe de développeurs continue de développer la quatrième version de ReiserFS (Reiser4 en abrégé), Ils ont publié la nouvelle version le mois dernier, prend en charge le noyau Linux3.5.4.

Ce qui précède est le contenu du type Mysql-index-BTree [simplifié]. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois (www.php.cn )!