Mysql-index-BTree-Typ [vereinfacht]

Ich habe viele Zusammenfassungen über B-TREE im Internet gelesen, B-Baum, B-Baum, B+-Baum, B*-Baum (warum hat Emma immer noch 4? Sie ist fast verwirrt),

Einige davon sind wirklich spannend und bewundernswert, aber sie sind alle zu lang. Ein langer Textabschnitt ist entmutigend. Lassen Sie uns einfach eine vereinfachte Version der Zusammenfassung erstellen, sie auf einfache und mobile Weise vorstellen und über ihre Unterschiede sprechen.
1. B-Baum

Binärbaum ist ein Binärbaum. (Die Formeln für K, h und n werden hier nicht besprochen. Wenn Sie interessiert sind, können Sie selbst danach suchen.)

(1) Alle Nicht- Blattknoten Haben höchstens zwei Söhne (Links und Rechts);

(2) Alle KnotenspeicherEin Schlüsselwort;

(3) Der linke Zeiger eines Nicht-Blattknotens zeigt auf weniger als seinen Schlüssel Der Teilbaum eines Wortes, der rechte Zeiger zeigt auf den Teilbaum, der größer als sein Schlüsselwort ist (Einfach ausgedrückt: Die linke Seite ist kleiner als er selbst und die rechte Seite ist kleiner größer als sich selbst 🎜>

Abbildung

B-Baum

Two.B-Tree

Balance Binary Tree – AVL-Baum [Das B bedeutet hier eigentlich Balance~]

( 1) Die Tiefe des linken Teilbaums und des rechten Teilbaums des Wurzelknotens unterscheidet sich höchstens um 1 (Dadurch wird sichergestellt, dass das extreme Phänomen nicht auftritt rechte Seite des Bildes oben)

(2) Der linke Teilbaum und der rechte Teilbaum des Wurzelknotens sind beide ein ausgeglichener Binärbaum .

(3) Alle Knoten speichern Schlüsselwörter

Unabhängig von der eingefügten Sequenz können wir durch Anpassungen einen ausgeglichenen Binärbaum erstellen, um sicherzustellen, dass der Gleichgewichtsfaktor jedes Knotens im Binärbaum nicht größer als 1 ist, stellt sicher, dass die Tiefe des Baums am flachsten ist , sodass die Anzahl der Vergleiche geringer ist und die Zeitkomplexität verringert wird

Abbildung B-Baum

Three.B+Tree

Die Suche von B+ ist im Grunde die gleiche wie die von B-Baum. Der Unterschied besteht darin, dass der B+-Baum nur den Blattknoten trifft (B-Baum kann den Nicht-Blattknoten treffen)

(1) Alle Schlüsselwörter erscheinen in der verknüpften Liste der Blattknoten (dichter Index), und die Schlüsselwörter in der verknüpften Liste sind zufällig geordnet ( Nur der Wurzelknoten speichert das Schlüsselwort und das Ende des letzten Baums hat einen Wert )

(2) Nicht- Blattknoten entsprechen dem Blattknoten-Index (Sparse-Index), Blattknoten entsprechen der Datenschicht, in der (Schlüsselwort-)Daten gespeichert werden. (Nicht-Root-Knoten speichern tatsächlich den Index, der auf den Root-Knoten zeigt )

(3 ) Aufgrund der ersten beiden Punkte ist es für unmöglich, Daten in Nicht-Blattknoten zu speichern. (Der dritte Unterschied zwischen B-)

(4) Der Wurzelknoten hat auch einen horizontalen Kettenzeiger (dies ist bequem zu befolgen). die Hinweise schnell, aber es gibt keinen solchen Zeiger, selbst wenn der nächste Wert ein benachbarter Nachbar ist, muss man im Kreis laufen, um ihn zu bekommen)

Beachten Sie, dass sich die meisten Indexergebnisse, die wir im Allgemeinen verwenden, oder die B-TREE-Struktur, auf die wir uns normalerweise beziehen, auf die B+-Struktur beziehen~~

Bild B+Baum

Vier.B*-Baum
ist ein B+ Baumvariationen,

(1)B+Die Nicht-Wurzel- und Nicht-Blattknoten des Baums fügen Zeiger auf Brüder hinzu; [Vergleiche mit Punkt 4 von B+ oben im Nicht-Root-Knoten fügt auch eine horizontal verknüpfte Liste hinzu]

Bild B * Baum

5. Zusammenfassung:

B-Baum: Binärbaum,

jeder Knoten wird gespeichert. Wenn es gleich ist, wird es zum linken Knoten verschoben, wenn es größer ist, wird es zum rechten Knoten verschoben Aber nach mehreren Einfügungen und Löschungen kann der B-Baum zu unterschiedlichen Strukturen führen ), aus diesem Grund wird nach dem Hinzufügen des Ausgleichsalgorithmus ein ausgeglichener Binärbaum generiert, auch bekannt als B-Baum

B-Baum: Basierend auf dem B-Baum, plus Ausgleichsalgorithmus und Mehrpfad-Suchbaum ,

1. Jeder Knoten speichert M/ 2 bis M Schlüsselwörter,

2 Untergeordnete Knoten, die auf den Schlüsselwortbereich verweisen;

3. Das Schlüsselwort erscheint im gesamten Baum und erscheint nur einmal Blattknoten und Nicht-Blattknoten können getroffen werden (unabhängig davon, ob Daten gespeichert werden);

B+-Baum: Basierend auf B-Baum,

1. Verknüpfter Listenzeiger zum Blattknoten 2 Schlüsselwörter erscheinen in Blattknoten,

3. Nicht-Blattknoten dienen als Indizes von Blattknoten

4 der Blattknoten; :

Basierend auf dem B+-Baum wird der verknüpfte Listenzeiger

auch zu den

Nicht-Blattknoten hinzugefügt, was zunimmt die minimale Auslastung des Knotens wurde von 1/2 auf 2/3 erhöht

Frage: B* ist effizienter, aber warum werden B*-Bäume Ihrer Meinung nach weniger verwendet? ????Oder wo ist es nützlich? ?
Vielleicht sehe ich immer noch zu wenig. . Kinderschuhe, die mehr voneinander wissen, können voneinander lernen, bitte geben Sie mir einen Rat, vielen Dank im Voraus~

Antwort: Ich habe kürzlich erfahren, dass es eine Person gibt namens

Das Dateisystem von Reiser4 scheint diese Struktur zu verwenden. Sein AutorHans Reiser, Weil seine Frau ihn zum Hahnrei gemacht hatte, tötete er seine Frau und ging ins Gefängnis, was sich direkt auf den Fortschritt des Projekts auswirkte. . .

Einführung:

Linux-Dateisystem ReiserFS Nachdem der Autor Hans Reiser wegen Mordes an seiner Frau zu 15 Jahren Gefängnis verurteilt wurde, ist die Entwicklung von ReiserFS jedoch nicht gestoppt es wurde noch nicht zusammengeführt. Gehen Sie zum Linux-Hauptzweig. Eine kleine Gruppe von Entwicklern entwickelt immer noch die vierte Version von ReiserFS (kurz Reiser4) weiter. Sie haben letzten Monat die neue Version, unterstützt den Linux3.5.4-Kernel.

Das Obige ist der Inhalt des Mysql-index-BTree-Typs [vereinfacht]. Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website (www.php.cn). )!