Welche Vorteile bietet die Verwendung von B+Tree als Index in MySQL?

Warum benötigen Datenbanken Indizes?

Wir alle wissen, dass Datenbankdaten auf der Festplatte gespeichert werden. Wenn unser Programm gestartet wird, entspricht dies einem Prozess, der im Speicher des Computers ausgeführt wird. Wenn unser Programm also Daten abfragen möchte, muss es aus dem Speicher auf die Festplatte gehen, um die Daten zu finden, und die Daten dann wieder in den Speicher schreiben. Allerdings ist die E/A-Effizienz der Festplatte weitaus geringer als die des Speichers, sodass die Geschwindigkeit der Datensuche direkte Auswirkungen auf die Effizienz des Programms hat.
Der Hauptzweck des Hinzufügens von Indizes zu einer Datenbank besteht darin, eine geeignete Datenstruktur zu verwenden, die die Datenabfrage effizienter macht, die Anzahl der Festplatten-E/A verringert und die Geschwindigkeit der Datensuche erhöht, anstatt eine unsinnige globale Durchquerung durchzuführen.

Warum verwendet der Index die B+Tree-Datenstruktur?

Wenn wir einfach darüber nachdenken und Daten schnell finden möchten, scheint die Hash-Tabelle am schnellsten zu sein. Hashen Sie sie gemäß dem Schlüssel in einen bestimmten Slot, und dann können wir den Speicherort der Daten mit nur einer Suche genau finden. Wie schnell ist das? Wenn wir jedoch geschäftlich tätig sind, benötigen wir oft nur ein Datenelement. Die meisten Anforderungen bestehen darin, einen Teil der Daten basierend auf bestimmten Bedingungen abzufragen. Zu diesem Zeitpunkt ist die Hash-Anzeige nicht sehr geeignet.

Betrachten wir Bäume wie Binärbäume, ausgeglichene Binärbäume, Rot-Schwarz-Bäume, B-Bäume usw. Sie alle verwenden die binäre Suche und sind schnell beim Auffinden von Zahlen. Unabhängig davon, ob es sich um einen ausgeglichenen Binärbaum oder einen optimierten Rot-Schwarz-Baum handelt, handelt es sich letztendlich immer um Binärbäume. Wenn mehr Knoten vorhanden sind, ist ihre Höhe höher. Lassen Sie mich einige Daten finden. Wenn der Stammknoten nicht vorhanden ist, suche ich nach der nächsten Ebene. Wenn die Daten in der nächsten Ebene immer noch nicht vorhanden sind, suche ich erneut nach der nächsten Ebene. Dies hat zur Folge, dass ich möglicherweise mehrmals nach einem Datenelement suchen muss und bei jedem Datenträger-E/A-Vorgang ausgeführt wird. Der Zweck unseres Index besteht darin, den Datenträger-E/A-Vorgang zu reduzieren, daher ist dieses Design nicht akzeptabel. Können wir also einfach die Höhe reduzieren?
Betrachten wir also noch einmal den B-Baum. Lassen Sie uns zunächst kurz die Datenstruktur des B-Baums vorstellen:
Sehen wir uns zunächst die Definition des B-Baums an.

1. Jeder Knoten hat höchstens m-1 Schlüsselwörter (Schlüssel-Wert-Paare, die gespeichert werden können).
2. Der Stammknoten kann mindestens ein Schlüsselwort haben.
3. Ein Nicht-Stammknoten hat mindestens m/2 Schlüsselwörter.
4. Die Schlüsselwörter in jedem Knoten sind in aufsteigender Reihenfolge angeordnet. Alle Schlüsselwörter im linken Teilbaum jedes Schlüsselworts sind kleiner als dieses und alle Schlüsselwörter im rechten Teilbaum sind größer als dieses.
5. Alle Blattknoten befinden sich in derselben Ebene, bzw. die Länge vom Wurzelknoten zu jedem Blattknoten ist gleich.
6. Jeder Knoten speichert Index und Daten, also den entsprechenden Schlüssel und Wert.
   

Daher beträgt der Bereich der Anzahl der Schlüsselwörter für den Stammknoten: 1 <= k <= m-1, und der Bereich der Anzahl der Schlüsselwörter für Nicht-Wurzelknoten beträgt: m/2 <= k <= m-1.

Dabei stellt m die Reihenfolge dar, die angibt, wie viele Kindknoten ein Knoten höchstens hat, daher muss die Reihenfolge eines B-Baums bei der Beschreibung angegeben werden.

Nehmen wir ein weiteres Beispiel, um das obige Konzept zu veranschaulichen. Hier ist beispielsweise ein B-Baum der Ordnung 5 mit einem Wurzelknotennummernbereich von 1 <= k <= 4 und einem Nicht-Wurzelknotennummernbereich von 2 <= k <= 4.

Als Nächstes erläutern wir den Einfügevorgang des B-Baums anhand eines Einfügebeispiels und erläutern anschließend den Vorgang zum Löschen von Schlüsselwörtern.

B-Tree-Einfügung

Beim Einfügen müssen wir eine Regel beachten: Bestimmen Sie, ob die Anzahl der Schlüssel des aktuellen Knotens kleiner oder gleich m-1 ist. Wenn dies erfüllt ist, fügen Sie es einfach direkt ein. Wenn nicht, verwenden Sie den mittleren Schlüssel des Knotens, um den Knoten in zwei Teile zu teilen, und fügen Sie den mittleren Knoten in den übergeordneten Knoten ein.

Beispiel: In einem B-Baum der 5. Ordnung hat ein Knoten maximal 4 und minimal 2 Schlüssel (Hinweis: Die folgenden Knoten werden einheitlich durch einen Knoten dargestellt, der Schlüssel und Wert darstellt).

Einsatz 18, 70, 50, 40

Einsatz 22

Beim Einfügen von 22 wird festgestellt, dass das Schlüsselwort dieses Knotens bereits größer als 4 ist, sodass er aufgeteilt werden muss. Die Regeln für das Aufteilen wurden oben erwähnt. Nach dem Aufteilen ist es wie folgt.

Dann fügen Sie 23, 25, 39 ein

Teilen Sie es und erhalten Sie Folgendes.

Daher erhöht sich die Anzahl der Knoten in jeder Schicht des B-Baums. Bei gleicher Datenmenge ist der B-Baum niedriger als der Binärbaum und die Anzahl der erforderlichen E/A-Vorgänge wird reduziert, sodass er unseren Indizierungsanforderungen entspricht. Warum hat sich MySQL letztendlich für den B+-Baum entschieden? Inwiefern ist er besser als der B-Baum?
Schauen wir uns zunächst die Unterschiede zwischen B+-Bäumen und B-Bäumen an:

• Die Blattknoten des B+-Baums enthalten alle Schlüsselwerte des Baums. Nicht-Blattknoten speichern keine Daten, sondern nur Indizes. Daten werden in Blattknoten gespeichert. Im B-Baum speichert jeder Knoten Index und Daten.
• Jeder Blattknoten des B+-Baums speichert Zeiger auf benachbarte Blattknoten, und die Blattknoten selbst sind entsprechend der Größe des Schlüsselworts in aufsteigender Reihenfolge verknüpft.
  

Wie in der Abbildung gezeigt:

Erster Punkt: Wenn Nicht-Blattknoten nur Indexschlüssel, aber keine Daten speichern, kann der von Nicht-Blattknoten belegte Speicherplatz reduziert werden. Knoten mit derselben Kapazität können mehr Indizes speichern. Für denselben dreischichtigen B+-Baum erhöht sich die Anzahl der Ebenen und er kann mehr Daten speichern als der B-Baum.
Der zweite Punkt: B+-Baumblattknoten speichern Zeiger auf benachbarte Blattknoten. Um die Vorteile dieses Zeigers zu verstehen, müssen wir zunächst wissen, dass die Platte beim Lesen von Daten oft nicht streng auf Anforderung liest, sondern jedes Mal vorliest. Selbst wenn nur ein Byte benötigt wird, beginnt die Platte an dieser Position und liest eine bestimmte Datenlänge rückwärts in den Speicher. Die theoretische Grundlage hierfür ist das berühmte Lokalitätsprinzip der Informatik:

• Wenn ein Datenelement verwendet wird, werden die benachbarten Daten normalerweise sofort verwendet.
• Die während der Programmausführung benötigten Daten werden üblicherweise konzentriert.
  

Die Länge des Vorlesens beträgt im Allgemeinen ein ganzzahliges Vielfaches einer Seite. Eine Seite ist ein logischer Block des Computerverwaltungsspeichers. Hardware und Betriebssysteme unterteilen Hauptspeicher und Festplattenspeicherbereiche häufig in zusammenhängende Blöcke gleicher Größe. Jeder Speicherblock wird als Seite bezeichnet (in vielen Betriebssystemen beträgt die Seitengröße normalerweise 4 KB). Hauptspeicher und Festplatte tauschen Daten in Seiteneinheiten aus. Wenn die Daten, die das Programm lesen möchte, nicht im Hauptspeicher sind, wird eine Seitenfehlerausnahme ausgelöst. Zu diesem Zeitpunkt sendet das System ein Lesesignal an die Festplatte. Die Festplatte findet die Startposition der Daten und liest kontinuierlich eine oder mehrere Seiten und lädt sie in den Speicher. Dann wird die Ausnahme zurückgegeben und das Programm wird weiter ausgeführt.

Schauen wir uns nun den Zeiger des untergeordneten Knotens des B + -Baums an und verstehen wir seine Verwendung. Beim Lesen im Voraus kann er sicherstellen, dass die fortlaufend gelesenen Daten in der richtigen Reihenfolge sind.

Einige Studenten haben möglicherweise den B*-Baum erwähnt, der auf dem B+-Baum basiert und verknüpfte Listenzeiger für Nicht-Blattknoten hinzufügt. Persönlich denke ich, dass der B-Stern-Baum unnötig ist, da wir keine Daten in Nicht-Blattknoten speichern. Die Daten befinden sich alle in den Blattknoten und die verknüpften Listenzeiger in Nicht-Blattknoten werden nicht verwendet.

Einige ausgefallene Konzepte

Clustered-Index und nicht-Clustered-Index: Wie oben erwähnt, speichern die Blattknoten des B+-Baums die Daten des Indexschlüssels, aber verschiedene MySQL-Engines haben unterschiedliche Möglichkeiten zum Speichern von Daten. MyISAM speichert die Indexdatei und die eigentliche Datendatei in zwei Dateien. Die in der Indexdatei gespeicherten Daten sind der Adresswert der Daten, die dem Indexschlüssel in der Datendatei entsprechen, während InnoDB die formalen Daten in den Blattknoten speichert. Daher dient Clustering und Nicht-Clustering dazu, zu unterscheiden, ob die in den Blattknoten gespeicherten Daten real sind (kann man das so verstehen, ob die Blattknoten überfüllt sind?).

Zurück zur Tabelle: Auch das Zurück zur Tabelle ist einfach, aber Sie müssen zuerst den Primärschlüsselindex und den normalen Index verstehen. Die oben erwähnten Blattknoten speichern echte Daten, die nur im Primärschlüsselindex gespeichert sind. Die im normalen Index gespeicherten Daten sind der Schlüssel des Primärschlüsselindex. Dann ist es für uns leichter zu verstehen. Beispielsweise habe ich einen normalen Index für das Namensfeld einer Tabelle erstellt. Ich möchte * aus der Tabelle auswählen, in der Name = „Test“ ist. Wenn wir den Testknoten finden, ist der Schlüssel, den wir erhalten, nur der Primärschlüssel, der dieser Datenzeile entspricht. Wenn wir die Daten der gesamten Zeile abrufen möchten, können wir nur diesen Schlüssel verwenden, um den Primärschlüsselindexbaum erneut zu durchsuchen. Dieser Vorgang wird als Tabellenrückgabe bezeichnet.

Prinzip der Übereinstimmung ganz links: Wenn wir einen neuen zusammengesetzten Index erstellen, z. B. (Name + Alter), wird bei der Abfrage mit „wo Name = xx und Alter = xx“ der zusammengesetzte Index verwendet, während „wo Alter = xx und Name = xx“ nicht verwendet wird. Dies liegt daran, dass die Regel von MySQL zum Erstellen eines gemeinsamen Index darin besteht, zuerst das ganz linke Feld des gemeinsamen Index zu sortieren und dann das zweite Feld basierend auf der Sortierung des ersten Felds zu sortieren.

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