Welche Vorteile bietet die Verwendung eines B+-Baums als Indexstruktur in MySQL?

Vorwort

In MySQL verwenden sowohl Innodb als auch MyIsam den B+-Baum als Indexstruktur (andere Indizes wie Hash werden hier nicht berücksichtigt). Dieser Artikel beginnt mit dem gebräuchlichsten binären Suchbaum und erläutert schrittweise die Probleme, die durch die verschiedenen Bäume gelöst werden, sowie die neuen Probleme, mit denen sie konfrontiert werden. Dadurch wird auch erklärt, warum MySQL den B+-Baum als Indexstruktur wählt.

1. Binärer Suchbaum (BST): Unausgeglichen

Ein binärer Suchbaum (BST), auch binär sortierter Baum genannt, muss basierend auf einem binären Baum die folgenden Bedingungen erfüllen: Die Werte aller Knoten im linken Teilbaum eines beliebigen Knotens sind nicht größer als der Wert des Wurzelknotens, und die Werte aller Knoten im rechten Teilbaum eines beliebigen Knotens sind nicht kleiner als der Wert des Wurzelknotens. Das Folgende ist ein BST:

Wenn eine schnelle Suche erforderlich ist, ist das Speichern von Daten in einem BST eine gängige Wahl, da die Abfragezeit von der Baumhöhe abhängt und die durchschnittliche Zeitkomplexität O(lgn) beträgt. Allerdings kann der BST schief werden und aus dem Gleichgewicht geraten, wie in der folgenden Abbildung dargestellt. Zu diesem Zeitpunkt degeneriert der BST zu einer verknüpften Liste und die zeitliche Komplexität degeneriert auf O(n).

Um dieses Problem zu lösen, wurde ein ausgeglichener Binärbaum eingeführt.

2. Balanced Binary Tree (AVL): Rotation zeitaufwändig

Der AVL-Baum ist ein streng ausgeglichener Binärbaum. Der Höhenunterschied zwischen den linken und rechten Teilbäumen aller Knoten kann 1 nicht überschreiten. Die Suche, Einfügung und Löschung des AVL-Baums sind sowohl im durchschnittlichen als auch im schlimmsten Fall O(lgn).

Der Schlüssel zum Erreichen des Gleichgewichts in AVL liegt im Rotationsvorgang: Einfügen und Löschen können das Gleichgewicht des Binärbaums zerstören. In diesem Fall sind eine oder mehrere Baumrotationen erforderlich, um den Baum wieder ins Gleichgewicht zu bringen. Beim Einfügen von Daten ist höchstens eine Rotation (Einzel- oder Doppelrotation) erforderlich. Beim Löschen von Daten ist der Baum jedoch unausgeglichen. AVL muss das Gleichgewicht aller Knoten auf dem Pfad vom gelöschten Knoten zum Stammknoten aufrechterhalten, und die Rotationsreihenfolge ist O (lgn).

Aufgrund der zeitaufwändigen Rotation ist der AVL-Baum beim Löschen von Daten sehr ineffizient. Bei vielen Löschvorgängen sind die Kosten für die Aufrechterhaltung des Gleichgewichts möglicherweise höher als die damit verbundenen Vorteile. Daher wird AVL in der Praxis nicht häufig verwendet.

3. Rot-schwarzer Baum: Der Baum ist zu hoch

Im Vergleich zu AVL-Bäumen streben Rot-Schwarz-Bäume keine strikte Balance an, sondern eine grobe Balance: Sie stellen lediglich sicher, dass der längstmögliche Pfad von der Wurzel zu einem Blatt nicht länger als doppelt so lang ist wie der kürzestmögliche Pfad. Aus Sicht der Implementierung besteht das größte Merkmal des Rot-Schwarz-Baums darin, dass jeder Knoten zu einer der beiden Farben (Rot oder Schwarz) gehört und die Aufteilung der Knotenfarben bestimmten Regeln entsprechen muss (die bestimmten Regeln werden weggelassen). Beispiele für Rot-Schwarz-Bäume sind:

Im Vergleich zum AVL-Baum verringert sich die Abfrageeffizienz des Rot-Schwarz-Baums, da der Baum weniger ausgewogen ist und eine größere Höhe aufweist. Die Löscheffizienz des Rot-Schwarz-Baums wird jedoch erheblich verbessert, da der Rot-Schwarz-Baum auch Farbe einführt. Beim Einfügen oder Löschen von Daten sind nur O(1) Rotationen und Farbänderungen erforderlich, um ein grundlegendes Gleichgewicht sicherzustellen, ohne dass O(lgn) Rotationen wie beim AVL-Baum erforderlich sind. Im Allgemeinen ist die statistische Leistung von Rot-Schwarz-Bäumen höher als die von AVL.

Daher werden AVL-Bäume in praktischen Anwendungen relativ selten verwendet, während Rot-Schwarz-Bäume sehr häufig verwendet werden. Beispielsweise verwendet TreeMap in Java Rot-Schwarz-Bäume zum Speichern sortierter Schlüssel-Wert-Paare; HashMap in Java8 verwendet verknüpfte Listen + Rot-Schwarz-Bäume zum Lösen von Hash-Kollisionsproblemen (wenn es weniger Konfliktknoten gibt, werden verknüpfte Listen verwendet, und wenn es mehr Konfliktknoten gibt, werden Rot-Schwarz-Bäume verwendet).

In Situationen, in denen sich Daten im Speicher befinden (wie bei den oben erwähnten TreeMap und HashMap), ist die Leistung von Rot-Schwarz-Bäumen hervorragend. Rot-Schwarz-Bäume eignen sich jedoch nicht gut für die Verarbeitung von Daten auf zusätzlichen Speichergeräten wie Festplatten (z. B. Datenbanken wie MySQL), da sie zu hoch wachsen. Wenn sich Daten auf der Festplatte befinden, wird die Festplatten-E/A zum größten Leistungsengpass. Das Designziel sollte darin bestehen, die Anzahl der E/A-Vorgänge zu minimieren. Je höher der Baum ist, desto mehr E/A-Vorgänge sind zum Hinzufügen, Löschen, Ändern und Prüfen erforderlich, was die Leistung erheblich beeinträchtigt.

4. B-Baum: Geboren für die Festplatte

B-Tree, auch B-Tree genannt (ohne Minuszeichen), ist ein mehrseitiger, ausgeglichener Suchbaum, der für zusätzliche Speichergeräte wie Festplatten entwickelt wurde. Im Vergleich zu einem Binärbaum kann jeder Nicht-Blattknoten des Baums mehrere Unterbäume haben. Daher ist die Höhe des B-Baums bei gleicher Gesamtzahl der Knoten viel kleiner als die des AVL-Baums und des Rot-Schwarz-Baums (der B-Baum ist ein „kleiner und dicker Mann“), und die Anzahl der Festplatten-E/A-Vorgänge wird erheblich reduziert.

Das wichtigste Konzept bei der Definition eines B-Baums ist die Ordnung. Für einen B-Baum der Ordnung m müssen die folgenden Bedingungen erfüllt sein:

• Jeder Knoten enthält höchstens m untergeordnete Knoten.
• Wenn der Stammknoten untergeordnete Knoten enthält, enthält er mindestens zwei untergeordnete Knoten. Mit Ausnahme des Stammknotens enthält jeder Nicht-Blattknoten mindestens m/2 untergeordnete Knoten.
• Ein Nicht-Blattknoten mit k untergeordneten Knoten enthält k - 1 Datensätze.
• Alle Blattknoten befinden sich in derselben Ebene.

Es ist ersichtlich, dass die Definition des B-Baums hauptsächlich dazu dient, die Anzahl der untergeordneten Knoten und Datensätze von Nicht-Blattknoten zu begrenzen.

Die folgende Abbildung ist ein Beispiel für einen B-Baum 3. Ordnung:

Der Vorteil des B-Baums liegt nicht nur in seiner geringen Baumhöhe, sondern auch in der Nutzung des Prinzips der Zugriffslokalität. Das sogenannte Lokalitätsprinzip bedeutet, dass bei der Verwendung eines Datenelements die Wahrscheinlichkeit höher ist, dass die Daten in der Nähe innerhalb kurzer Zeit verwendet werden. Der B-Baum speichert Daten mit ähnlichen Schlüsseln im selben Knoten. Wenn auf ein Datenelement zugegriffen wird, liest die Datenbank den gesamten Knoten in den Cache. Wenn als nächstes auf die angrenzenden Daten zugegriffen wird, können diese ohne Festplatten-E/A direkt aus dem Cache gelesen werden. Mit anderen Worten: Der B-Baum hat eine höhere Cache-Trefferquote.

B-Bäume werden in Datenbanken teilweise verwendet. Der Index von MongoDB verwendet beispielsweise die B-Baum-Struktur. In vielen Datenbankanwendungen wird jedoch eine Variante des B-Baums, der B+-Baum, verwendet.

5. B+ Baum

Der B+-Baum ist ebenfalls ein mehrseitiger balancierter Suchbaum. Die Hauptunterschiede zwischen diesem und dem B-Baum sind:

• Jeder Knoten im B-Baum (einschließlich Blattknoten und Nicht-Blattknoten) speichert echte Daten, während im B+-Baum nur Blattknoten echte Daten speichern und Nicht-Blattknoten nur Schlüssel speichern. In MySQL können die hier erwähnten tatsächlichen Daten alle Daten der Zeile (wie der gruppierte Index von Innodb), nur der Primärschlüssel der Zeile (wie der Hilfsindex von Innodb) oder die Adresse der Zeile (wie der nicht gruppierte Index von MyIsam) sein.
• Ein Datensatz in einem B-Baum kommt nur einmal vor und nicht wiederholt, während der Schlüssel eines B+-Baums wiederholt vorkommen kann – er kommt auf jeden Fall in einem Blattknoten vor und kann auch wiederholt in einem Nicht-Blattknoten vorkommen.
• Die Blattknoten des B+-Baums sind durch eine doppelt verkettete Liste verknüpft.
• In einem Nicht-Blattknoten in einem B-Baum ist die Anzahl der Datensätze um eins kleiner als die Anzahl der untergeordneten Knoten; in einem B+-Baum hingegen ist die Anzahl der Datensätze gleich der Anzahl der untergeordneten Knoten.

Daher hat der B+-Baum gegenüber dem B-Baum die folgenden Vorteile:

• **Weniger IO-Zeiten: **Nicht-Blattknoten des B+-Baums enthalten nur Schlüssel, keine echten Daten, daher ist die Anzahl der in jedem Knoten gespeicherten Datensätze viel größer als die B-Anzahl (d. h. die Ordnung m ist größer), sodass die Höhe des B+-Baums geringer ist und für den Zugriff weniger IO-Zeiten erforderlich sind. Da außerdem jeder Knoten mehr Datensätze speichert, wird das Zugriffslokalitätsprinzip besser ausgenutzt und die Cache-Trefferquote ist höher.
• **Besser geeignet für Bereichsabfragen: **Wenn Sie eine Bereichsabfrage in einem B-Baum durchführen, suchen Sie zuerst die zu durchsuchende Untergrenze und führen Sie dann eine geordnete Durchquerung des B-Baums durch, bis die Obergrenze gefunden ist. Bei einer Bereichsabfrage in einem B+-Baum müssen Sie dagegen nur die verknüpfte Liste durchlaufen.
• **Stabilere Abfrageeffizienz: **Die Abfragezeitkomplexität des B-Baums liegt zwischen 1 und der Baumhöhe (entspricht den Datensätzen im Stammknoten bzw. in den Blattknoten), während die Abfragekomplexität des B+-Baums auf der Baumhöhe stabil ist, da sich alle Daten in den Blattknoten befinden.

B+-Bäume haben auch Nachteile: Da Schlüssel wiederholt werden, benötigen sie mehr Platz. Im Vergleich zu den Leistungsvorteilen ist der Platznachteil jedoch oft akzeptabel, weshalb B+-Bäume in Datenbanken häufiger verwendet werden als B-Bäume.

6. Spüren Sie die Kraft des B+-Baumes

Wie bereits erwähnt, besteht der größte Vorteil von B-Baum/B+-Baum gegenüber binären Bäumen wie Rot-Schwarz-Bäumen darin, dass die Baumhöhe geringer ist. Tatsächlich beträgt die Baumhöhe beim B+-Index von Innodb im Allgemeinen 2–4 Schichten. Lassen Sie uns einige konkrete Schätzungen vornehmen.

Die Höhe des Baums wird durch die Reihenfolge bestimmt. Je größer die Reihenfolge, desto kürzer der Baum. Die Reihenfolge hängt davon ab, wie viele Datensätze jeder Knoten speichern kann. Jeder Knoten in Innodb verwendet eine Seite mit einer Seitengröße von 16 KB, von denen Metadaten nur etwa 128 Bytes belegen (einschließlich Dateiverwaltungskopfinformationen, Seitenkopfinformationen usw.) und der größte Teil des Speicherplatzes zum Speichern von Daten verwendet wird.

• Bei Nicht-Blattknoten enthält der Datensatz nur den Indexschlüssel und einen Zeiger auf den Knoten der nächsten Ebene. Unter der Annahme, dass auf jeder Nicht-Blattknotenseite 1000 Datensätze gespeichert sind, nimmt jeder Datensatz ungefähr 16 Byte ein. Diese Annahme ist sinnvoll, wenn der Index eine Ganzzahl oder eine kurze Zeichenfolge ist. Um dies zu erweitern, hören wir oft Vorschläge, dass die Indexspaltenlänge nicht zu groß sein sollte. Dies ist der Grund: Wenn die Indexspalte zu lang ist, enthält jeder Knoten zu wenige Datensätze, was dazu führt, dass der Baum zu hoch ist, der Indexeffekt stark reduziert wird und der Index mehr Platz verschwendet.
• Bei Blattknoten enthalten die Datensätze den Indexschlüssel und den Wert (der Wert kann der Primärschlüssel der Zeile, eine vollständige Datenzeile usw. sein, Einzelheiten finden Sie im vorherigen Artikel) und die Datenmenge ist größer. Hier wird angenommen, dass auf jeder Blattknotenseite 100 Datensätze gespeichert sind (tatsächlich kann diese Zahl unter 100 liegen, wenn es sich bei dem Index um einen gruppierten Index handelt; wenn es sich bei dem Index um einen sekundären Index handelt, kann diese Zahl viel über 100 liegen; dies kann anhand der tatsächlichen Bedingungen geschätzt werden).

Bei einem dreischichtigen B+-Baum verfügt die erste Schicht (Wurzelknoten) über 1 Seite, auf der 1000 Datensätze gespeichert werden können; die zweite Schicht verfügt über 1000 Seiten, auf denen 1000 * 1000 Datensätze gespeichert werden können; die dritte Schicht (Blattknoten) verfügt über 1000 * 1000 Seiten, auf jeder Seite können 100 Datensätze gespeichert werden, sodass 1000 * 1000 * 100 Datensätze oder 100 Millionen Datensätze gespeichert werden können. Für einen binären Baum sind zum Speichern von 100 Millionen Datensätzen etwa 26 Ebenen erforderlich.

VII. Fazit

Abschließend wollen wir noch einmal zusammenfassen, welche Probleme die verschiedenen Bäume gelöst haben und welche neuen Probleme sich ihnen stellen:

1. Binärer Suchbaum (BST): Er löst das grundlegende Sortierproblem, kann aber zu einer verknüpften Liste verkommen, da er keine Ausgewogenheit garantieren kann.
2. Balanced Binary Tree (AVL): Das Balanceproblem wird durch Rotation gelöst, aber die Effizienz der Rotationsoperation ist zu gering.
3. Rot-Schwarz-Baum: Durch das Aufgeben des strikten Gleichgewichts und die Einführung von Rot-Schwarz-Knoten wird das Problem der geringen AVL-Rotationseffizienz gelöst. In Szenarien wie Festplatten ist der Baum jedoch immer noch zu hoch und die IO-Zeiten sind zu hoch.
4. B-Baum: Durch die Änderung des Binärbaums in einen mehrseitig ausgeglichenen Suchbaum wird das Problem des zu hohen Baums gelöst.
5. B+-Baum: Basierend auf dem B-Baum werden Nicht-Blattknoten in reine Indexknoten umgewandelt, die keine Daten speichern, wodurch die Höhe des Baums weiter reduziert wird; außerdem werden Blattknoten mithilfe von Zeigern zu einer verknüpften Liste verbunden, was Bereichsabfragen effizienter macht.

Oben finden Sie ausführliche Informationen zu den Vorteilen der Verwendung von B+-Baum als Indexstruktur von MySQL. Weitere Informationen zur MySQL B+-Baumindexstruktur finden Sie in den anderen verwandten Artikeln auf 123WORDPRESS.COM!