Welche Vorteile bietet die Verwendung des B+-Baumindex in MySQL?

Bevor wir dieses Problem verstehen, schauen wir uns zunächst die Speicherstruktur der MySQL-Tabelle an und vergleichen dann die Unterschiede zwischen Binärbäumen, Mehrfachbäumen, B-Bäumen und B+-Bäumen.

MySQL-Speicherstruktur

Tabellenspeicherstruktur

Einheit: Tabelle > Segment > Bereich > Seite > Zeile

Unabhängig davon, ob Sie in der Datenbank eine oder mehrere Zeilen lesen, werden die Seiten geladen, auf denen sich diese Zeilen befinden. Das bedeutet, dass die Basiseinheit für Speicherplatz die Seite ist.
Eine Seite ist ein Knoten eines B+-Baums. Die kleinste Einheit eines Datenbank-E/A-Vorgangs ist eine Seite, und der gesamte datenbankbezogene Inhalt wird in der Seitenstruktur gespeichert.

B+ Baumindexstruktur

1. In einem B+-Baum stellt jeder Knoten eine Seite dar. Jedes Mal, wenn ein neuer Knoten erstellt wird, wird ein Seitenspeicherplatz angefordert.
2. Die Knoten auf derselben Ebene liegen dazwischen, und durch die Seitenstruktur wird eine bidirektionale verknüpfte Liste gebildet.
3. Nicht-Blattknoten enthalten mehrere Indexzeilen, von denen jede den Indexschlüssel und einen Zeiger auf die Seite der nächsten Ebene speichert.
4. Der Blattknoten speichert Schlüsselwörter und Zeilendatensätze. Zwischen den Datensätzen innerhalb des Knotens (d. h. innerhalb der Seitenstruktur) besteht eine einseitig verknüpfte Liste.
   

B+ Baumseitenknotenstruktur

Es gibt mehrere Merkmale

1. Teilen Sie alle Datensätze in mehrere Gruppen auf. Jede Gruppe speichert mehrere Datensätze.
2. Das Seitenverzeichnis speichert Slots, die dem Index gruppierter Datensätze entsprechen. Jeder Slotzeiger zeigt auf den letzten Datensatz einer anderen Gruppe.
3. Wir lokalisieren die Gruppe über den Slot und sehen uns dann die Datensätze in der Gruppe an
   

Die Hauptfunktion einer Seite besteht darin, Datensätze zu speichern, und Datensätze werden auf einer Seite in Form einer einzelnen verknüpften Liste gespeichert.
Der Vorteil einer einfach verknüpften Liste besteht darin, dass sie leicht einzufügen und zu löschen ist, ihr Nachteil jedoch darin, dass die Abrufeffizienz gering ist und im schlimmsten Fall alle Knoten in der verknüpften Liste durchlaufen werden müssen. Daher wird im Seitenverzeichnis eine binäre Suchmethode bereitgestellt, um die Effizienz des Datensatzabrufs zu verbessern.

B+ Baumabrufprozess

Werfen wir einen Blick auf den Abrufvorgang des B+-Baums.

1. Suchen Sie ausgehend von der Wurzel des B+-Baums Schicht für Schicht nach den Blattknoten.
2. Suchen Sie den Blattknoten als entsprechende Datenseite, laden Sie das Datenblatt in den Speicher und verwenden Sie eine binäre Suche durch die Slots des Seitenverzeichnisses, um zunächst eine grobe Datensatzgruppierung zu finden.
3. Die Datensätze werden in der Gruppe durch Durchsuchen der verknüpften Liste gesucht.

Warum den B+-Baumindex verwenden?

Die Datenbank greift über Seiten auf Daten zu. Eine Seite ist ein B+-Baumknoten. Der Zugriff auf einen Knoten entspricht einer E/A-Operation. Je schneller der Knoten gefunden werden kann, desto besser ist die Suchleistung.
Die Eigenschaft des B+-Baums besteht darin, dass er kurz und dick genug ist, wodurch die Anzahl der Knotenzugriffe effektiv reduziert und somit die Leistung verbessert werden kann.

Als nächstes vergleichen wir einen Binärbaum, einen Multi-Fork-Baum, einen B-Baum und einen B+-Baum.

Binärer Baum

Ein Binärbaum ist ein binärer Suchbaum mit guter Suchleistung, der einer binären Suche entspricht.
Wenn N jedoch größer ist, ist die Tiefe des Baums höher. Die Zeit für die Datenabfrage hängt hauptsächlich von der Anzahl der Festplatten-E/A ab. Je tiefer der Binärbaum ist, desto mehr Suchvorgänge werden durchgeführt und desto schlechter ist die Leistung.
Im schlimmsten Fall degeneriert es zu einer verknüpften Liste, wie unten gezeigt

Um zu verhindern, dass der Binärbaum zu einer verknüpften Liste degeneriert, hat man den AVL-Baum (Balanced Binary Search Tree) erfunden: Der Höhenunterschied zwischen dem linken und rechten Teilbaum eines beliebigen Knotens beträgt höchstens 1.

Mehrzweigiger Baum

Ein Multi-Fork-Baum kann M Knoten haben, wodurch die Höhe effektiv reduziert werden kann. Wenn die Höhe reduziert wird, verringert sich die Anzahl der Knoten und die E/A werden natürlich reduziert, und die Leistung ist besser als die eines Binärbaums.

B-Baum

Ein B-Baum ist einfach ein Baum mit mehreren Verzweigungen, wobei jedes Blatt Daten und einen Zeiger auf den nächsten Knoten speichert.

Um beispielsweise 9 zu finden, sind die Schritte wie folgt

1. Wir vergleichen es mit dem Schlüsselwort (17, 35) des Wurzelknotens. 9 ist kleiner als 17, also erhalten wir den Zeiger P1.
2. Folgen Sie dem Zeiger P1, um Festplattenblock 2 zu finden. Der Schlüssel ist (8, 12), da 9 zwischen 8 und 12 liegt. Daher erhalten wir den Zeiger P2.
3. Folgen Sie dem Zeiger P2, um den Datenträgerblock 6 zu finden. Der Schlüssel ist (9, 10), und dann finden wir Schlüssel 9.
   

B+ Baum

Der B+-Baum ist eine Verbesserung des B-Baums. Einfach ausgedrückt speichern nur Blattknoten Daten und Nicht-Blattknoten sind Speicherzeiger; alle Blattknoten bilden eine geordnete verknüpfte Liste.

Die internen Knoten des B+-Baums haben keine Zeiger auf die spezifischen Informationen des Schlüsselworts, daher sind seine internen Knoten kleiner als die des B-Baums. Wenn alle Schlüsselwörter desselben internen Knotens im selben Plattenblock gespeichert sind, kann der Plattenblock mehr Schlüsselwörter aufnehmen, und die Anzahl der Schlüsselwörter, die gleichzeitig durchsucht werden müssen, ist ebenfalls höher, was die relativen IO-Lese- und Schreibzeiten reduziert.

Um beispielsweise nach dem Schlüsselwort 16 zu suchen, sind die Schritte wie folgt

1. Vergleichen Sie mit dem Schlüsselwort des Stammknotens (1, 18, 35), 16 liegt zwischen 1 und 18, und erhalten Sie den Zeiger P1 (zeigt auf Datenträgerblock 2).
2. Suchen Sie nach Datenträgerblock 2, der Schlüssel ist (1, 8, 14), da 16 größer als 14 ist. Holen Sie sich daher den Zeiger P3 (der auf Datenträgerblock 7 zeigt).
3. Wir finden Datenträgerblock 7, der Schlüssel ist (14, 16, 17), und dann finden wir Schlüssel 16, sodass wir die Daten finden können, die Schlüssel 16 entsprechen.

Der Unterschied zwischen B+-Baum und B-Baum:

1. Nicht-Blattknoten von B+-Bäumen haben keine Daten, sondern nur Indizes. Nicht-Blattknoten von B-Bäumen speichern Daten.
2. B+-Baumabfrage ist effizienter. Der B+-Baum verwendet eine bidirektionale verknüpfte Liste, um alle Blattknoten zu verbinden. Dadurch werden Bereichsabfragen effizienter (da sich alle Daten in den Blattknoten des B+-Baums befinden und zum Scannen der Datenbank nur ein einmaliges Scannen der Blattknoten erforderlich ist). Allerdings erfordert der B-Baum eine geordnete Durchquerung, um den Suchbereich abzuschließen.
3. Die Effizienz der B+-Baumabfragen ist stabiler. Der B+-Baum muss jedes Mal den Blattknoten abfragen, um Daten zu finden. Die vom B-Baum abgefragten Daten befinden sich möglicherweise nicht im Blattknoten oder sie befinden sich im Blattknoten, was zu einer instabilen Abfrageeffizienz führt.
4. B+-Bäume weisen geringere Lese- und Schreibkosten auf der Festplatte auf. Die internen Knoten des B+-Baums haben keine Zeiger auf die spezifischen Informationen des Schlüsselworts, sodass seine internen Knoten kleiner sind als die des B-Baums. Normalerweise ist der B+-Baum kürzer und dicker, und die kleine Abfrage generiert weniger E/A.
   

Aus diesem Grund verwendet MySQL B+-Bäume, so einfach ist das!

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