Der Grund, warum MySQL den B+-Baum als zugrunde liegende Datenstruktur verwendet

Wir alle wissen, dass die zugrunde liegende Datenstruktur von MySQL ein B+-Baum ist. Warum also nicht einen Rot-Schwarz-Baum oder andere Datenstrukturen verwenden?

Der Rot-Schwarz-Baum ist ein selbstausgleichender binärer Suchbaum. Die Hashmap in Java8 verwendet den Rot-Schwarz-Baum, um ihre Abfrageeffizienz zu optimieren. Es ist ersichtlich, dass die Abfrageeffizienz des Rot-Schwarz-Baums immer noch relativ hoch ist. Aber warum verwendet MySQL in der untersten Ebene B+-Bäume anstelle von Rot-Schwarz-Bäumen?

Die folgende Abbildung zeigt die Situation, nachdem der Rot-Schwarz-Baum nacheinander in 1, 2, 3, 4, 5 und 6 eingefügt wurde:

Fügen Sie dann 7 in den obenstehenden rot-schwarzen Baum ein:

Es ist ersichtlich, dass, obwohl der Rot-Schwarz-Baum selbst ausgeglichen wurde, die Daten insgesamt immer noch zur rechten Seite des Baums tendieren. Wenn weitere Daten hinzugefügt werden, wird die Ebene des Baums nach der Hinzufügung von Millionen oder Zehnmillionen von Daten sehr hoch sein. Bei der Abfrage erfordert jede zusätzliche Ebene eine weitere IO. Wenn die Anzahl der Baumebenen zunimmt, wird die Suchleistung sehr langsam sein. An dieser Stelle könnte sich jemand fragen, warum nicht der ausgeglichenere AVL-Baum verwendet wird.

Der AVL-Baum sieht nach dem Einfügen von 1,2,3,4,5,6,7 auf einmal folgendermaßen aus:

Es sieht zwar viel besser aus und die Anzahl der Baumschichten hat abgenommen, aber AVL löst das grundlegende Problem immer noch nicht. Wenn die Datenmenge Millionen oder Zehnmillionen erreicht, wird die Anzahl der Baumschichten immer noch relativ groß sein. Ganz zu schweigen von den Kosten für die Aufrechterhaltung des Gleichgewichts des AVL-Baums. Die Anzahl der AVL-Baumschichten allein kann unsere Anforderungen nicht erfüllen.

Welche Art von Datenstruktur kann also die Anzahl der Ebenen gering halten, wenn das Datenvolumen Millionen, Zehnmillionen oder sogar noch mehr erreicht? Wenn wir die Anzahl der Schichten reduzieren möchten, müssen wir natürlich mehr Daten in jeder Schicht speichern. Egal wie ausgewogen ein binärer Baum ist, er kann an jedem Knoten nur zwei Verzweigungen haben. Die Datenmenge in jeder Schicht ist durch die Datenstruktur begrenzt, daher können wir nicht aus einem binären Baum auswählen. Diesmal wird also der Vorteil des B-Baums deutlich. Jeder Knoten des B-Baums kann mehrere Elemente speichern, und jedes Element kann eine Verzweigung haben. Die folgende Abbildung zeigt, dass jeder Knoten des B-Baums bis zu 3 Elemente speichern kann:

Es ist ersichtlich, dass die Baumebene auf zwei Ebenen reduziert wird. Wenn die maximale Anzahl von Elementen, die gleichzeitig in jedem Knoten gespeichert werden können, groß genug ist, kann die Baumebene auch dann in einem akzeptablen Bereich gesteuert werden, wenn die Datenmenge mehrere zehn Millionen erreicht.

Es gibt jedoch noch ein weiteres Problem mit B-Tree. Die folgende Abbildung zeigt die Situation, wenn der B-Tree drei Ebenen erreicht:

Wenn ich jetzt die Elemente 5 bis 10 herausnehmen muss, wenn ich Element 5 durch eine schichtweise Abfrage finde und dann feststelle, dass sich andere Elemente nicht in diesem Knoten befinden, muss ich andere Elemente durch lokales Durchlaufen der Reihenfolge abfragen. Nachdem ich 7 gefunden habe, muss ich dieselbe Operation ausführen, um 8, 9 und 10 zu finden, was die Anzahl der IO-Vorgänge erhöht, sodass ein B + -Baum entsteht.

Der B+-Baum ist eine Optimierung des B-Baums, hauptsächlich aus zwei Aspekten:

Die erste Optimierung besteht darin, zwischen jedem Blattknoten einen bidirektionalen Zeiger hinzuzufügen, der auf die benachbarten Knoten zeigt. Dadurch wird das oben erwähnte Problem der Bereichsabfrage gelöst. Wenn sich die Bereichsabfrage über mehrere Knoten erstreckt, können die benachbarten Knoten über diesen bidirektionalen Zeiger schnell gefunden werden, ohne dass eine lokale In-Order-Traversierung erforderlich ist, wodurch die Anzahl der IO-Zeiten reduziert wird. Die folgende Abbildung zeigt den B+-Baum:

Was aber, wenn das gesuchte Element nicht im Blattknoten enthalten ist? Keine Sorge, eine weitere Optimierung des B+-Baums besteht darin, dass die Blattknoten alle Elemente des Baums enthalten! Die Nicht-Blattknoten des B+-Baums speichern die Daten oder Zeiger der Elemente nicht mehr, sondern dienen nur als redundante Indizes, um einen vollständigen B+-Baum für eine einfache Abfrage zu bilden. Es ist ersichtlich, dass Element 15 in der obigen Abbildung nicht nur in Nicht-Blattknoten, sondern auch in Blattknoten vorhanden ist. Obwohl dieses Design viele redundante Indizes mit sich bringt, entfällt die Notwendigkeit, bei Bereichsabfragen nach Nicht-Blattknoten nach oben zu suchen. Darüber hinaus erhöht sich die Anzahl der Indizes, die auf jeder Ebene gespeichert werden können, sodass die Datenbank bei jeder IO-Durchführung mehr Indexelemente abfragen kann. Schließlich ist unter normalen Umständen der von Daten belegte Speicherplatz viel größer als der von Indizes belegte. (Es ist zu beachten, dass, obwohl sowohl die InnoDB- als auch die MyISAM-Engine B+-Bäume verwenden, der gruppierte Index und die Daten von InnoDB zusammen gespeichert werden, während MyISAM den gruppierten Index und den entsprechenden Datenzeiger zusammen speichert und der Index und die Daten getrennt sind. Der B+-Baum unter der MyISAM-Engine speichert Datenzeiger auch nur in Blattknoten.)

Aus der obigen Analyse können wir erkennen, dass der Grund, warum der B+-Baum als zugrunde liegende Schicht von MySQL gewählt wurde, darin besteht, die Anzahl der IO-Operationen zu reduzieren. Warum gehen wir also nicht bis zum Äußersten und verwenden Hashes, um Daten oder Indizes zu speichern? Tatsächlich unterstützt MySQL Hash-Typ-Indizes.

Hash-Indizes werden jedoch im Allgemeinen nicht verwendet, hauptsächlich weil Hash-Indizes Hash-Codes speichern und die Speicherreihenfolge nichts mit der Wertegröße der Indexspalte zu tun hat. Daher sind Hash-Indizes nur bei der Durchführung exakter Suchen wirksam, und bei Bereichsabfragen wird ein vollständiger Tabellenscan durchgeführt. Gleichzeitig steigt die Anzahl der Hash-Kollisionen, wenn die Datenmenge in der Tabelle sehr groß ist, und die Effizienz einer einzelnen Suche ist möglicherweise nicht höher als die des B + -Baums.

Kurz zusammengefasst: Im Vergleich zu anderen Bäumen kann jeder Knoten des B+-Baums mehr Elemente speichern, was die Anzahl der für Abfragen erforderlichen IO-Vorgänge erheblich reduzieren kann. Das Design von Nicht-Blattknoten, die weder Daten noch Zeiger speichern, kann die Anzahl der in jedem Knoten gespeicherten Elemente erhöhen, und die bidirektionalen Zeiger der Blattknoten können die Effizienz von Bereichsabfragen verbessern.

Damit ist dieser Artikel darüber, warum MySQL den B+-Baum als zugrunde liegende Datenstruktur verwendet, abgeschlossen. Weitere Informationen zum MySQL B+-Baum finden Sie in früheren Artikeln auf 123WORDPRESS.COM oder in den folgenden verwandten Artikeln. Ich hoffe, Sie werden 123WORDPRESS.COM auch in Zukunft unterstützen!