Warum verwendet der MySQL-Datenbankindex den B+-Baum?

Bevor wir weiter analysieren, warum der MySQL-Datenbankindex die Verwendung eines B+-Baums wählt, glaube ich, dass viele Freunde in Bezug auf den Baum in der Datenstruktur noch etwas vage sind. Deshalb werden wir den Evolutionsprozess des Baums Schritt für Schritt vom oberflächlichen zum tieferen Teil untersuchen und dann Schritt für Schritt den B-Baum vorstellen und erklären, warum der MySQL-Datenbankindex die Verwendung eines B+-Baums wählt!

Wer sich mit Datenstrukturen beschäftigt hat, verfügt im Allgemeinen über ein gewisses Verständnis des grundlegendsten Baums. Wir werden daher mit dem binären Suchbaum beginnen, der unserem Thema näher kommt.

1. Binärer Suchbaum

(1) Einführung in den Binärbaum:

Ein binärer Suchbaum wird auch als geordneter binärer Suchbaum bezeichnet. Er erfüllt die allgemeinen Eigenschaften eines binären Suchbaums, was bedeutet, dass ein leerer Baum die folgenden Eigenschaften hat:

1. Wenn der linke Teilbaum eines beliebigen Knotens nicht leer ist, ist der Wert des linken Teilbaums kleiner als der Wert des Wurzelknotens.

2. Wenn der rechte Teilbaum eines beliebigen Knotens nicht leer ist, ist der Wert des rechten Teilbaums größer als der Wert des Wurzelknotens.

3. Die linken und rechten Teilbäume eines beliebigen Knotens sind ebenfalls binäre Suchbäume.

4. Es gibt keine Knoten mit gleichen Schlüsselwerten;

Das obige Bild stellt einen gewöhnlichen binären Suchbaum dar. Gemäß der In-Order-Traversal-Methode kann die Ausgabe von klein nach groß sortiert werden: 2, 3, 5, 6, 7, 8.

Um beispielsweise den obigen Binärbaum zu durchsuchen und nach einem Datensatz mit dem Schlüsselwert 5 zu suchen, suchen Sie zuerst nach der Wurzel, deren Schlüsselwert 6 ist. 6 ist größer als 5, durchsuchen Sie also den linken Teilbaum von 6 und finden Sie 3. Da 5 größer als 3 ist, durchsuchen Sie seinen rechten Teilbaum. Insgesamt werden 3 Suchvorgänge durchgeführt. Wenn Sie dreimal in der Reihenfolge 2, 3, 5, 6, 7, 8 nach der gleichen Anforderung suchen. Verwenden Sie dieselbe Methode, um nach dem Datensatz mit dem Schlüsselwert 8 zu suchen. Diesmal sind 3 Suchvorgänge erforderlich, während bei einer sequentiellen Suche 6 Suchvorgänge erforderlich sind. Wenn wir die durchschnittliche Anzahl der Suchvorgänge berechnen, erhalten wir: Die durchschnittliche Anzahl der Suchvorgänge für die sequentielle Suche beträgt (1+2+3+4+5+6)/6 = 3,3 Mal, und die durchschnittliche Anzahl der Suchvorgänge für einen binären Suchbaum beträgt (3+3+3+2+2+1)/6 = 2,3 Mal. Die durchschnittliche Suchgeschwindigkeit eines binären Suchbaums ist schneller als die einer sequentiellen Suche.

(2) Einschränkungen und Anwendungsbereiche

Ein binärer Suchbaum besteht aus n zufällig angeordneten Knoten, sodass der binäre Suchbaum in einigen Fällen zu einer linearen Kette mit n Knoten degeneriert. Wie unten dargestellt:

Schauen Sie sich das Bild oben an. Wenn unser Wurzelknoten die kleinste oder größte Zahl ist, dann degeneriert der binäre Suchbaum vollständig in eine lineare Struktur. Die durchschnittliche Anzahl der Suchvorgänge in der obigen Abbildung beträgt (1+2+3+4+5+5)/6=3,16-mal, was der sequentiellen Suche ähnelt. Offensichtlich ist die Abfrageeffizienz dieses Binärbaums sehr gering. Wenn Sie also einen binären Suchbaum mit maximaler Leistung erstellen möchten, muss dieser Binärbaum ausgeglichen sein (der Ausgleich ist hier an einem signifikanten Merkmal zu erkennen, nämlich dass die Höhe dieses Baums größer ist als die Höhe des vorherigen Inputs, was bei denselben Knoten unausgeglichen ist), was zu einer neuen Definition führt – ausgeglichener Binärbaum AVL.

2. AVL-Baum

(1) Einleitung

Der AVL-Baum ist ein binärer Suchbaum mit einer Gleichgewichtsbedingung. Er verwendet im Allgemeinen die Gleichgewichtsfaktordifferenz, um zu bestimmen, ob er ausgeglichen ist, und erreicht das Gleichgewicht durch Rotation. Die Höhe der linken und rechten Teilbäume überschreitet 1 nicht. Verglichen mit dem Rot-Schwarz-Baum ist er ein streng ausgeglichener Binärbaum, und die Gleichgewichtsbedingung muss erfüllt sein (der Höhenunterschied der linken und rechten Teilbäume aller Knoten überschreitet 1 nicht). Unabhängig davon, ob wir Einfüge- oder Löschvorgänge durchführen, müssen wir, solange die oben genannten Bedingungen nicht erfüllt sind, das Gleichgewicht durch Rotation aufrechterhalten, und die Rotation ist sehr zeitaufwändig. Daraus können wir erkennen, dass der AVL-Baum für Situationen geeignet ist, in denen die Anzahl der Einfügungen und Löschungen relativ gering ist, aber viele Suchvorgänge durchgeführt werden.

Aus dem Obigen können wir erkennen, dass dies ein gewöhnlicher ausgeglichener Binärbaum ist. Aus diesem Bild können wir erkennen, dass der Unterschied in den Ausgleichsfaktoren zwischen den linken und rechten Teilbäumen eines beliebigen Knotens nicht größer als 1 ist.

(2) Beschränkungen

Da die Kosten für die Aufrechterhaltung dieses hohen Gleichgewichtsgrades höher sind als der daraus resultierende Effizienzgewinn, gibt es nicht viele praktische Anwendungen. An vielen Orten werden Rot-Schwarz-Bäume verwendet, die ein lokales statt eines sehr strengen Gesamtgleichgewichts anstreben. Wenn das Anwendungsszenario keine häufigen Einfügungen und Löschungen erfordert, aber hohe Anforderungen an die Suche stellt, ist AVL natürlich immer noch besser als der Rot-Schwarz-Baum.

(3) Anwendung

1. Weit verbreitet im Windows NT-Kernel;

3. Rot-Schwarzer Baum

(1) Einleitung

Ein binärer Suchbaum, aber mit einem zusätzlichen Bit an jedem Knoten, um die Farbe des Knotens darzustellen, die rot oder schwarz sein kann. Durch die Einschränkung der Art und Weise, wie Knoten auf jedem Pfad von der Wurzel zu einem Blatt eingefärbt werden können, stellt ein Rot-Schwarz-Baum sicher, dass kein Pfad doppelt so lang ist wie ein anderer Pfad. Es handelt sich um einen schwach ausgeglichenen Binärbaum (da er ausgeglichen ist, kann gefolgert werden, dass die Höhe des AVL-Baums unter denselben Knotenbedingungen niedriger ist als die des Rot-Schwarz-Baums). Im Vergleich zum streng erforderlichen AVL-Baum ist seine Anzahl an Rotationen reduziert, sodass wir bei vielen Such-, Einfüge- und Löschvorgängen den Rot-Schwarz-Baum verwenden.

(2) Natur

1. Jeder Knoten ist entweder rot oder schwarz;

2. Der Wurzelknoten ist schwarz;

3. Jeder Blattknoten (Blattknoten ist der NULL-Zeiger oder NULL-Knoten am Ende des Baums) ist schwarz;

4. Wenn ein Knoten rot ist, sind seine beiden Söhne schwarz;

5. Für jeden Knoten enthält jeder Pfad zum NULL-Zeiger des Blattbaums die gleiche Anzahl schwarzer Knoten.

6. Jeder Pfad enthält dieselben schwarzen Knoten;

(3) Anwendung

1. In C++ STL wird häufig verwendet. Map und Set werden beide mithilfe von Rot-Schwarz-Bäumen implementiert.

2. Der berühmte Linux-Prozessplaner Completely Fair Scheduler verwendet einen rot-schwarzen Baum, um den Prozesssteuerungsblock zu verwalten. Der virtuelle Speicherbereich des Prozesses wird in einem rot-schwarzen Baum gespeichert. Jeder virtuelle Adressbereich entspricht einem Knoten des rot-schwarzen Baums. Der linke Zeiger zeigt auf den virtuellen Speicherbereich mit der benachbarten Adresse und der rechte Zeiger auf den virtuellen Adressraum mit der benachbarten hohen Adresse.

3. Die Implementierung des IO-Multiplexings Epoll verwendet eine Rot-Schwarz-Baumorganisation zur Verwaltung von Sockfd, um schnelles Hinzufügen, Löschen, Ändern und Abfragen zu unterstützen.

4. Nginx verwendet einen Rot-Schwarz-Baum zur Verwaltung von Timern, da der Rot-Schwarz-Baum geordnet ist und der Timer mit dem geringsten Abstand zum aktuellen schnell abgerufen werden kann.

5. Implementierung von TreeMap in Java;

4. B/B+ Baum

Nachdem wir über die drei oben genannten Baumtypen gesprochen haben: binärer Suchbaum, AVL und Rot-Schwarz-Baum, haben wir anscheinend noch nicht herausgefunden, warum MySQL den B+-Baum als Indeximplementierung verwendet. Keine Sorge, lassen Sie uns zunächst besprechen, was ein B-Baum ist.

(1) Einleitung

Unsere Daten in MySQL werden im Allgemeinen auf der Festplatte gespeichert. Beim Lesen von Daten muss ein Vorgang ausgeführt werden, um auf die Festplatte zuzugreifen. Auf der Festplatte gibt es zwei mechanisch bewegliche Teile, nämlich die Rotation der Festplatte und die Bewegung des Magnetarms. Die Drehung des Plattentellers ist die auf dem Markt angegebene Anzahl von Umdrehungen pro Minute, während die Plattenbewegung erfolgt, wenn sich der Plattenteller in die angegebene Position dreht und den Magnetarm bewegt, um mit dem Lesen und Schreiben von Daten zu beginnen. Anschließend erfolgt der Prozess zum Lokalisieren des Blocks auf der Platte. Das Positionieren ist ein zeitaufwändiger Teil des Plattenzugriffs. Schließlich dauert die mechanische Bewegung viel länger als die elektronische Bewegung. Wenn große Datenmengen auf der Festplatte gespeichert sind, ist die Positionierung offensichtlich ein sehr zeitaufwändiger Prozess, aber wir können ihn durch B-Bäume optimieren, um die Effizienz der Positionierung beim Lesen von Festplatten zu verbessern.

Warum kann B-Baum optimiert werden? Basierend auf den Eigenschaften des B-Baums können wir einen mehrstufigen B-Baum erstellen und dann relevante Informationen auf so vielen Knoten wie möglich speichern. Dabei muss die Anzahl der Schichten so gering wie möglich sein, damit wir die Informationen später schneller finden können und auch weniger Festplatten-E/A-Vorgänge erforderlich sind. Darüber hinaus ist der B-Baum ein ausgeglichener Baum, und die Höhe von jedem Knoten bis zum Blattknoten ist gleich, was auch sicherstellt, dass jede Abfrage stabil ist.

Im Allgemeinen ist der B/B+-Baum ein ausgeglichener Mehrwege-Suchbaum, der für Festplatten oder andere Speichergeräte entwickelt wurde (im Vergleich zum Binärbaum hat jeder interne Knoten des B-Baums mehrere Zweige). Verglichen mit dem Rot-Schwarz-Baum ist die Höhe eines B/B+-Baums unter derselben Knotensituation viel kleiner als die Höhe eines Rot-Schwarz-Baums (siehe Leistungsanalyse des B/B+-Baums weiter unten). Die Zeit für Operationen an einem B/B+-Baum besteht normalerweise aus zwei Teilen: der Zeit für den Zugriff auf die Festplatte und der CPU-Berechnungszeit. Die CPU ist sehr schnell, daher hängt die Betriebseffizienz des B-Baums von der Anzahl der Zugriffe auf die Festplatte ab. Bei gleicher Gesamtzahl der Schlüsselwörter gilt: Je kleiner die Höhe des B-Baums, desto weniger Zeit wird für Festplatten-E/A benötigt.

Beachten Sie, dass ein B-Baum ein B-Baum ist und das - nur ein Symbol ist.

(2) Eigenschaften des B-Baumes

1. Definieren Sie, dass jeder Nicht-Blattknoten höchstens M Söhne hat und M>2;

2. Die Anzahl der Söhne des Wurzelknotens ist [2, M];

3. Die Anzahl der Söhne von Nicht-Blattknoten außer dem Wurzelknoten beträgt [M/2, M];

4. Jeder Knoten speichert mindestens M/2-1 (aufgerundet) und höchstens M-1 Schlüsselwörter; (mindestens 2 Schlüsselwörter)

5. Die Anzahl der Schlüsselwörter von Nicht-Blattknoten = die Anzahl der Zeiger auf Söhne - 1;

6. Schlüsselwörter von Nicht-Blattknoten: K[1], K[2], …, K[M-1]; und K[i] < K[i+1];

7. Zeiger auf Nicht-Blattknoten: P[1], P[2], …, P[M]; P[1] zeigt auf den Teilbaum, dessen Schlüssel kleiner als K[1] ist, P[M] zeigt auf den Teilbaum, dessen Schlüssel größer als K[M-1] ist, und das andere P[i] zeigt auf den Teilbaum, dessen Schlüssel zu (K[i-1], K[i]) gehört;

8. Alle Blattknoten befinden sich in derselben Schicht;

Dies ist nur ein einfacher B-Baum. In der Praxis gibt es in den B-Baumknoten viele Schlüsselwörter. In der obigen Abbildung stellt beispielsweise Knoten 35 einen Schlüssel (Index) dar, und der kleine schwarze Block stellt den tatsächlichen Speicherort des Inhalts dar, auf den dieser Schlüssel, der ein Zeiger ist, zeigt.

5. B+ Baum

(1) Einleitung

Der B+-Baum ist eine Variante des B-Baums, der vom Dateisystem generiert wird (Dateiverzeichnisse werden Ebene für Ebene indiziert, und nur die untersten Blattknoten (Dateien) speichern Daten). Nicht-Blattknoten speichern nur Indizes, keine tatsächlichen Daten. Daten werden in Blattknoten gespeichert. Werden Dateisystemdateien nicht auf diese Weise durchsucht?

Nehmen wir ein Beispiel für eine Dateisuche: Es gibt drei Ordner a, b und c, a enthält b, b enthält c und eine Datei yang.c. a, b, c sind Indizes (gespeichert in Nicht-Blattknoten), a, b, c sind nur die Schlüssel von yang.c, die gefunden werden müssen, und die eigentlichen Daten von yang.c sind in den Blattknoten gespeichert.

Alle Nicht-Blattknoten können als Indexteile betrachtet werden!

(2) Eigenschaften von B+-Bäumen (die unten genannten Eigenschaften unterscheiden sich von denen von B-Bäumen)

1. Der Teilbaumzeiger von Nicht-Blattknoten entspricht der Anzahl der Schlüsselwörter.

2. Der Teilbaumzeiger p[i] des Nicht-Blattknotens zeigt auf den Teilbaum, dessen Schlüsselwert zu [k[i], k[i+1]] gehört. (B-Baum ist ein offenes Intervall, was bedeutet, dass B-Baum keine Schlüsselduplizierung zulässt, während B+-Baum eine Duplizierung zulässt);

3. Fügen Sie allen Blattknoten einen Linkzeiger hinzu.

4. Alle Schlüsselwörter erscheinen in Blattknoten (dichter Index). (Und die Schlüsselwörter in der verknüpften Liste sind zufällig in der richtigen Reihenfolge);

5. Nicht-Blattknoten entsprechen dem Index von Blattknoten (spärlicher Index), und Blattknoten entsprechen der Datenschicht zum Speichern von (Schlüsselwort-)Daten.

6. Besser geeignet für Dateisysteme;

Ein Nicht-Blattknoten (wie 5, 28, 65) ist nur ein Schlüssel (Index). Die in den Blattknoten (5, 8, 9) gespeicherten tatsächlichen Daten sind die realen Daten oder ein Zeiger auf die realen Daten.

(3) Anwendung

1. B- und B+-Bäume werden hauptsächlich für die Indizierung in Dateisystemen und Datenbanken wie MySQL verwendet.

6. B/B+-Baum-Leistungsanalyse

Die Höhe eines ausgeglichenen Binärbaums mit n Knoten beträgt H (d. h. logn), während die Höhe eines B/B+-Baums mit n Knoten logt((n+1)/2)+1 beträgt;

Als In-Memory-Lookup-Tabelle ist ein B-Baum nicht unbedingt besser als ein ausgeglichener Binärbaum, insbesondere wenn m groß ist. Denn die CPU-Zeit für Suchvorgänge auf B-Bäumen beträgt O(mlogtn)=O(lgn(m/lgt)) und m/lgt>1; wenn also m groß ist, ist O(mlogtn) viel länger als die Operationszeit eines ausgeglichenen Binärbaums. Daher muss bei Verwendung eines B-Baums im Speicher ein kleineres m verwendet werden. (Normalerweise wird der Minimalwert m=3 genommen. Zu diesem Zeitpunkt kann jeder interne Knoten im B-Baum 2 oder 3 untergeordnete Knoten haben. Dieser B-Baum dritter Ordnung wird als 2-3-Baum bezeichnet.)

7. Warum ist ein B+-Baum für einen Datenbankindex besser geeignet als ein B-Baum?

1. Die Lese- und Schreibkosten für die Festplatte des B+-Baums sind geringer: Die internen Knoten des B+-Baums haben keine Zeiger auf die spezifischen Informationen der Schlüsselwörter, daher sind seine internen Knoten kleiner als die des B-Baums. Wenn alle Schlüsselwörter desselben internen Knotens im selben Festplattenblock gespeichert sind, kann der Festplattenblock mehr Schlüsselwörter aufnehmen und es müssen gleichzeitig mehr Schlüsselwörter im Speicher gesucht werden, sodass die relativen IO-Lese- und Schreibzeiten reduziert werden.

2. Die Abfrageeffizienz des B+-Baums ist stabiler: da der Nicht-Endpunkt nicht der Knoten ist, der letztendlich auf den Dateiinhalt verweist, sondern nur der Index des Schlüsselworts im Blattknoten. Daher muss jede Schlüsselwortsuche einen Pfad vom Stammknoten zum Blattknoten nehmen. Die Pfadlängen aller Keyword-Abfragen sind gleich, was zu einer vergleichbaren Abfrageeffizienz für jedes Datenelement führt.

3. Da die Daten des B+-Baums in den Blattknoten gespeichert sind und die Zweigknoten Indizes sind, ist es praktisch, die Datenbank zu scannen. Sie müssen die Blattknoten nur einmal scannen. Da die Zweigknoten des B-Baums jedoch auch Daten speichern, müssen wir eine In-Order-Traversierung durchführen, um zu scannen und bestimmte Daten zu finden. Daher ist der B+-Baum besser für Intervallabfragen geeignet, sodass B+-Bäume normalerweise für Datenbankindizes verwendet werden.

PS: Ich habe jemanden das hier auf Zhihu sagen sehen und ich denke, es macht Sinn:

Sie glauben, dass der Hauptgrund für die Verwendung von B+-Bäumen in Datenbankindizes darin liegt, dass B-Bäume zwar die IO-Leistung verbessern, aber das Problem der ineffizienten Elementdurchquerung nicht lösen. Genau um dieses Problem zu lösen, wurden B+-Bäume erstellt. Der B+-Baum muss nur die Blattknoten durchlaufen, um den gesamten Baum zu durchlaufen. Darüber hinaus sind bereichsbasierte Abfragen in Datenbanken sehr häufig, aber B-Bäume unterstützen solche Operationen nicht oder sind zu ineffizient.

Zusammenfassen

Das Obige ist der vollständige Inhalt dieses Artikels. Ich hoffe, dass der Inhalt dieses Artikels einen gewissen Lernwert für Ihr Studium oder Ihre Arbeit hat. Vielen Dank für Ihre Unterstützung von 123WORDPRESS.COM. Wenn Sie mehr darüber erfahren möchten, schauen Sie sich bitte die folgenden Links an