Eine kurze Diskussion über den MySQL B-Tree-Index und die Indexoptimierungszusammenfassung

Die MyISAM- und InnoDB-Engines von MySQL verwenden beide standardmäßig B+-Baumindizes (bei Abfragen als „BTREE“ angezeigt). In diesem Artikel werden zwei Probleme behandelt:

1. Warum wählen gängige Datenbanken wie MySQL die B+-Baumindexstruktur?
2. Wie versteht man allgemeine Ideen zur MySQL-Indexoptimierung basierend auf der Indexstruktur?

Warum passen nicht alle Indizes in den Speicher?

Bei der Wahl der Indexstruktur kommt folgende Eigenschaft zum Tragen: Bei großen Datenmengen kann der Index nicht vollständig in den Speicher geladen werden.

Warum passt der gesamte Index nicht in den Speicher? Unter der Annahme, dass der Index in einer Baumstruktur organisiert ist, lautet eine einfache Schätzung:

1. Angenommen, ein einzelner Indexknoten ist 12 Byte groß, es gibt 10 Millionen Datenzeilen und einen eindeutigen Index. Dann belegen die Blattknoten insgesamt etwa 100 MB und der gesamte Baum maximal 200 MB.
2. Unter der Annahme, dass eine Datenzeile 200 B einnimmt, belegen die gesamten Daten etwa 2 G.

Nehmen Sie an, der Index ist im Speicher gespeichert. Das heißt, jedes Mal, wenn 2 GB Daten auf der physischen Festplatte gespeichert werden, werden 200 MB Speicher belegt, und das Belegungsverhältnis Index:Daten beträgt etwa 1/10. Wird ein Belegungsverhältnis von 1/10 als groß angesehen? Physische Datenträger sind viel günstiger als Speicher. Nehmen wir als Beispiel einen Server mit 16 GB Speicher und einer 1-TB-Festplatte. Wenn Sie die 1-TB-Festplatte füllen möchten, benötigen Sie mindestens 100 GB Speicher, also viel mehr als 16 GB.

Wenn man berücksichtigt, dass eine Tabelle mehrere Indizes, gemeinsame Indizes und eine geringere Datenzeilenbelegung haben kann, ist das tatsächliche Belegungsverhältnis normalerweise größer als 1/10 und kann manchmal 1/3 erreichen. In einer indexbasierten Speicherarchitektur ist das Index:Daten-Verhältnis zu hoch, sodass der Index nicht vollständig in den Speicher geladen werden kann.

Andere strukturelle Probleme

Da es nicht in den Speicher geladen werden kann, ist es auf die Speicherung auf Festplatten (oder SSDs) angewiesen. Die Lese- und Schreibgeschwindigkeit des Speichers ist tausendmal so hoch wie die der Festplatte (je nach spezifischer Implementierung). Daher lautet das Kernproblem: „Wie kann die Anzahl der Lese- und Schreibvorgänge auf der Festplatte reduziert werden?“

Gehen Sie zunächst davon aus, dass jeder Lese- und Schreibvorgang direkt auf die Festplatte erfolgt, ohne den Seitentabellenmechanismus zu berücksichtigen. Dann:

1. Lineare Struktur: durchschnittlich O(n) Mal Lesen/Schreiben
2. Binärer Suchbaum (BST): Lesen/Schreiben im Durchschnitt O(log2(n))-mal; wenn der Baum unausgeglichen ist, im schlimmsten Fall O(n)-mal Lesen/Schreiben
3. Selbstausgleichender binärer Suchbaum (AVL): fügt einen selbstausgleichenden Algorithmus basierend auf BST hinzu, mit einer maximalen Lese-/Schreibzeit von O(log2(n))
4. Rot-Schwarz-Baum (RBT): Ein weiterer selbstausgleichender Suchbaum mit einer maximalen Lese-/Schreibzeit von O(log2(n))

BST, AVL und RBT optimieren die Anzahl der Lese- und Schreiboperationen von O(n) auf O(log2(n)). AVL und RBT verfügen im Vergleich zu BST über eine selbstausgleichende Funktion, die die Anzahl der Lese- und Schreiboperationen auf maximal O(log2(n)) reduziert.

Unter der Annahme, dass ein automatisch inkrementierter Primärschlüssel verwendet wird, ist der Primärschlüssel selbst geordnet und die Anzahl der Lese- und Schreibvorgänge der Baumstruktur kann auf die Baumhöhe optimiert werden. Je niedriger die Baumhöhe, desto weniger Lese- und Schreibvorgänge; die Selbstbalancierung gewährleistet die Stabilität der Baumstruktur. Wenn Sie weiter optimieren möchten, können Sie B-Baum und B+-Baum einführen.

Welches Problem löst B-Tree?

In vielen Artikeln werden B-Bäume fälschlicherweise als B-(Reduktions-)Bäume bezeichnet, was auf einem Missverständnis des englischen Namens „B-Tree“ beruhen kann (schlimmer noch: B-Bäume werden als Binärbäume oder binäre Suchbäume bezeichnet). Insbesondere wenn man mit B+-Bäumen spricht. Es wird vorausgesetzt, dass es, wenn es einen B+ (Plus)-Baum gibt, auch einen B- (Minus)-Baum geben muss. Tatsächlich lautet der englische Name des B+-Baums „B+-Tree“.

Wenn wir die Wartungsvorgänge ignorieren, ist der B-Baum wie ein „m-Wege-Suchbaum“ (m ist die maximale Anzahl von Teilbäumen) mit einer Zeitkomplexität von O(logm(n)). Der B-Baum ist jedoch mit einem effizienten und einfachen Wartungsvorgang ausgestattet, um die Tiefe des B-Baums zwischen ungefähr log(ceil(m/2))(n) und logm(n) zu halten und so die Baumhöhe erheblich zu reduzieren.

Noch einmal,

Machen Sie sich keine Sorgen über die zeitliche Komplexität. Im Gegensatz zu einfachen Algorithmen sind die Datenträger-E/A-Zeiten ein größerer Faktor. Der Leser kann daraus schließen, dass die zeitliche Komplexität von B-Tree und AVL gleich ist, aber da B-Tree weniger Schichten und weniger Festplatten-E/A-Zeiten hat, ist die Leistung von B-Tree in der Praxis besser als die von Binärbäumen wie AVL.

Ähnlich wie bei einem binären Suchbaum speichert jeder Knoten mehrere Schlüssel und Teilbäume, und die Teilbäume und Schlüssel sind der Reihe nach angeordnet.

Das Verzeichnis der Seitentabelle dient dazu, den externen Speicher zu erweitern und das Lesen und Schreiben auf der Festplatte zu beschleunigen. Eine Seite ist normalerweise 4 KB groß (entspricht der Größe des Datenblocks auf der Festplatte, siehe Analyse von Inode und Block). Das Betriebssystem lädt den Inhalt jedes Mal in Seiteneinheiten von der Festplatte in den Speicher (um die Suchkosten zu verteilen). Nach der Änderung der Seite wird die Seite zum geeigneten Zeitpunkt wieder auf die Festplatte geschrieben. Unter Berücksichtigung der guten Eigenschaften der Seitentabelle kann die Größe jedes Knotens ungefähr gleich einer Seite gemacht werden (wodurch m sehr groß wird), sodass jede geladene Seite einen Knoten vollständig abdecken kann, um die nächste Ebene des Teilbaums auszuwählen; dasselbe gilt für Teilbäume. Für die Seitentabelle entspricht AVL (oder RBT) einem B-Baum mit 1 Schlüssel + 2 Unterbäumen. Da logisch benachbarte Knoten normalerweise nicht physisch benachbart sind, besteht der größte Teil des Speicherplatzes auf der Seite beim Einlesen einer 4k-Seite aus ungültigen Daten.

Unter der Annahme, dass der Schlüssel- und der Unterbaumknotenzeiger jeweils 4 B belegen, beträgt die maximale Größe des B-Baumknotens m * (4 + 4) = 8 MB; die Seitengröße beträgt 4 KB. Dann ist m = 4 * 1024 / 8m = 512, ein B-Baum mit 512 Verzweigungen, 10 Millionen Daten, die maximale Tiefe beträgt log(512/2)(10^7) = 3,02 ~= 4. Im Vergleich dazu beträgt die Tiefe von Binärbäumen wie AVL log(2)(10^7) = 23,25 ~= 24, also mehr als das Fünffache der Tiefe. Schock! Die Tiefe des B-Baum-Index ist so hoch!

Darüber hinaus sind B-Bäume sehr gut mit dem Lokalitätsprinzip vereinbar. Wenn der Schlüssel relativ klein ist (wie der selbstinkrementierende 4B-Schlüssel oben), kann der Cache zusätzlich zum Vorteil der Seitentabelle das Vorlesen weiter beschleunigen. Köstlich~

Welche Probleme löst der B+-Baum?

Das verbleibende Problem des B-Baumes

Wenn B-Tree jedoch tatsächlich auf Datenbankindizes angewendet werden soll, gibt es noch einige Probleme:

1. Nicht lokalisierte Datenzeile
2. Die Bereichsabfrage kann nicht verarbeitet werden.

Frage 1

Die Datensätze in einer Datentabelle haben mehrere Felder. Es reicht nicht aus, nur den Primärschlüssel zu finden, sondern Sie müssen auch die Datenzeile finden. Es gibt 3 Lösungen:

1. Speichern Sie die Datenzeile (möglicherweise mehrere Zeilen), die dem Schlüssel entspricht, direkt im untergeordneten Knoten.
2. Datenzeilen werden separat gespeichert; dem Knoten wird ein Feld hinzugefügt, um die Position der dem Schlüssel entsprechenden Datenzeile zu lokalisieren.
3. Ändern Sie die Beurteilungslogik des Schlüssels und des Teilbaums so, dass der Teilbaum größer oder gleich dem vorherigen Schlüssel und kleiner als der nächste Schlüssel ist. Schließlich fallen alle Zugriffe auf den Blattknoten; der Blattknoten speichert direkt die Datenzeile oder den Speicherort der Datenzeile.

Lösung 1 wird direkt weitergegeben. Durch das Speichern von Datenzeilen wird die Anzahl der Teilbäume auf der Seite reduziert und m wird verringert, während die Baumhöhe zunimmt.

In Lösung 2 wird dem Knoten ein Feld hinzugefügt. Angenommen, es handelt sich um einen 4B-Zeiger, dann ist das neue m = 4 * 1024 / 12m = 341,33 ~= 341 und die maximale Tiefe ist log(341/2)(10^7) = 3,14 ~= 4.

Der Knoten m und die Tiefe der Lösung 3 bleiben unverändert, aber die Zeitkomplexität wird stabil O(logm(n)).

Option 3 kann in Betracht gezogen werden.

Frage 2

Im tatsächlichen Geschäftsleben ist die Häufigkeit von Bereichsabfragen sehr hoch. B-Tree kann nur eine Indexposition lokalisieren (die mehreren Zeilen entsprechen kann), was die Verarbeitung von Bereichsabfragen erschwert. Die geringfügigen Änderungen sind 2

planen:

1. Keine Änderung. Suchen Sie bei der Suche zuerst nach der linken Grenze, dann nach der rechten Grenze und verwenden Sie anschließend DFS (oder BFS), um die Knoten zwischen der linken und der rechten Grenze zu durchlaufen.
2. Basierend auf „Problem 1 – Lösung 3“ sind die Blattknoten des B-Baums ebenfalls geordnet, da alle Datenzeilen in Blattknoten gespeichert sind. Es kann ein Zeiger hinzugefügt werden, der in der Reihenfolge des Primärschlüssels auf den nächsten Blattknoten des aktuellen Blattknotens zeigt. Überprüfen Sie bei der Abfrage zuerst die linke Grenze, dann die rechte Grenze und durchlaufen Sie dann linear von der linken Grenze zur begrenzten Grenze.

Auf den ersten Blick scheint Lösung 1 besser zu sein als Lösung 2 – die Zeitkomplexität und die konstanten Terme sind gleich und Lösung 1 muss nicht geändert werden. Aber vergessen Sie nicht das Prinzip der Lokalität. Unabhängig davon, ob der Knoten Datenzeilen oder Datenzeilenpositionen speichert, besteht der Vorteil von Lösung 2 darin, dass die Seitentabelle und der Cache weiterhin zum Vorablesen der Informationen des nächsten Knotens verwendet werden können. Lösung 1 hat jedoch den Nachteil, dass die Knoten logisch benachbart, aber physisch getrennt sind.

Einführung in B+ Tree

Zusammenfassend lässt sich sagen, dass Lösung 2 für Problem 1 und Lösung 1 für Problem 2 in eine Lösung integriert werden können (basierend auf dem B-Baum-Index) und dass Lösung 3 für Problem 1 und Lösung 2 für Problem 2 in eine Lösung integriert werden können (basierend auf dem B+-Baum-Index). Tatsächlich verwenden einige Datenbanken und Dateisysteme B-Bäume, während andere B+-Bäume verwenden.

Aus Gründen, die manche Affen noch nicht verstehen, wählen gängige Datenbanken, einschließlich MySQL, hauptsächlich B+-Bäume. Im Augenblick:

Die wichtigsten Änderungen sind wie folgt:

1. Ändern Sie die Organisationslogik von Schlüsseln und Teilbäumen, um Indexzugriffe auf Blattknoten zu beschränken.
2. Fädeln Sie die Blattknoten der Reihe nach aneinander (für eine einfache Bereichsabfrage)

Der Prozess des Hinzufügens, Löschens und Überprüfens von B-Bäumen und B+-Bäumen

Der Vorgang des Hinzufügens und Löschens von B-Bäumen kann vorübergehend im Abschnitt „6. Einfüge- und Löschvorgänge von B-Bäumen“ von B-Baum, B+-Baum, B*-Baum bis R-Baum nachgelesen werden. Dasselbe gilt für das Hinzufügen und Löschen von B+-Bäumen. Auf die Einzelheiten werde ich hier nicht näher eingehen.

Mysql-Indexoptimierung

Basierend auf den Eigenschaften von B+-Bäumen lassen sich verschiedene gängige Ideen zur MySQL-Indexoptimierung leicht verstehen.

Auf die Unterschiede zwischen den verschiedenen Engines wollen wir hier einmal nicht näher eingehen.

Bevorzugte Verwendung des Auto-Increment-Schlüssels als Primärschlüssel

In der vorherigen Analyse kann m unter der Annahme, dass als Index ein 4B-Autoinkrementschlüssel verwendet wird, 512 erreichen und die Layerhöhe beträgt nur 3. Die Verwendung eines Auto-Inkrement-Schlüssels bietet zwei Vorteile:

Der Auto-Inkrement-Schlüssel ist im Allgemeinen ein ganzzahliger Typ wie int, und der Schlüssel ist relativ kompakt, sodass m sehr groß sein kann und der Index wenig Platz einnimmt. Im extremsten Beispiel, wenn ein 50B varchar (einschließlich Länge) verwendet wird, dann ist m = 4 * 1024 / 54m = 75,85 ~= 76 und die maximale Tiefe ist log(76/2)(10^7) = 4,43 ~= 5. Hinzu kommen die Kosten für Cache-Fehler und Zeichenfolgenvergleiche, und der Zeitaufwand erhöht sich erheblich. Gleichzeitig wächst der Schlüssel von 4 B auf 50 B und auch der vom gesamten Indexbaum belegte Speicherplatz wächst enorm (wenn der Sekundärindex den Primärschlüssel zum Suchen der Datenzeile verwendet, ist die Speicherplatzzunahme noch gravierender).

Die selbstinkrementierende Natur bedeutet, dass die Einfügeanforderung für neue Datenzeilen zwangsläufig auf die äußerste rechte Seite des Indexbaums fällt und die Häufigkeit der Knotenaufteilung gering ist. Im Idealfall kann der Indexbaum einen „vollen“ Zustand erreichen. Wenn der Indexbaum voll ist, ist die Ebenenhöhe geringer und die Häufigkeit der Knotenzusammenführung beim Löschen von Knoten ist ebenfalls geringer.

Optimierungserfahrung:

Ich habe einmal eine varchar(100)-Spalte als Primärschlüssel zum Speichern der Container-ID verwendet. Nach 3 oder 4 Tagen war die 100G-Datenbank voll. Die DBA-Dame drückte mir in einer E-Mail ihre Verachtung aus. . . Anschließend wurde eine Auto-Increment-Spalte als Primärschlüssel und containerId als eindeutiger Sekundärindex hinzugefügt. Die Zeit- und Platzoptimierungseffekte waren beträchtlich.

Ganz links stehendes Präfix passend

Ein Index kann so einfach wie eine einzelne Spalte (a) oder so komplex wie mehrere Spalten (a, b, c, d) sein, d. h. ein gemeinsamer Index. Handelt es sich um einen gemeinsamen Index, setzt sich der Schlüssel ebenfalls aus mehreren Spalten zusammen. Gleichzeitig kann über den Index nur ermittelt werden, ob der Schlüssel vorhanden ist (Gleichheit). Wird eine Bereichsabfrage (>, <, between, wie left match) gefunden, ist kein weiteres Matching mehr möglich und es verkommt in der Folge zu einer linearen Suche. Daher bestimmt die Reihenfolge, in der die Spalten angeordnet sind, die Anzahl der Spalten, die den Index treffen können.

Wenn ein Index (a, b, c, d) vorhanden ist und die Abfragebedingung a = 1 und b = 2 und c > 3 und d = 4 ist, werden in jedem Knoten nacheinander a, b und c getroffen, d jedoch nicht. Dies ist das Prinzip der Übereinstimmung des Präfixes ganz links.

=、in der Reihenfolge der automatischen Optimierung

Sie müssen die Reihenfolge von =, in usw. nicht berücksichtigen. MySQL optimiert die Reihenfolge dieser Bedingungen automatisch, um möglichst viele Indexspalten abzugleichen.

Wenn ein Index (a, b, c, d) vorhanden ist, sind die Abfragebedingungen c > 3 und b = 2 und a = 1 und d < 4 und a = 1 und c > 3 und b = 2 und d < 4 alle möglich. MySQL optimiert automatisch auf a = 1 und b = 2 und c > 3 und d < 4 und trifft nacheinander auf a, b und c.

Indexspalten können nicht in Berechnungen verwendet werden

Abfragebedingungen, die Indexspalten in Berechnungen einbeziehen, sind nicht indexfreundlich (oder können nicht einmal Indizes verwenden), wie z. B. „from_unixtime(create_time) = '2014-05-29'“.

Der Grund ist einfach. Wie findet man den entsprechenden Schlüssel im Knoten? Bei einem linearen Scan muss die Berechnung jedes Mal neu durchgeführt werden, was zu aufwändig ist, bei einer binären Suche muss das Größenverhältnis für die Methode from_unixtime ermittelt werden.

Daher können Indexspalten nicht an Berechnungen teilnehmen. Die obige Anweisung from_unixtime(create_time) = '2014-05-29' sollte als create_time = unix_timestamp('2014-05-29') geschrieben werden.

Erstellen Sie keine neuen Indizes, wenn Sie erweitern können

Wenn Sie bereits einen Index (a) haben und einen Index (a, b) erstellen möchten, versuchen Sie, den Index (a) in den Index (a, b) zu ändern.

Die Kosten für die Erstellung eines neuen Indexes sind leicht zu verstehen. Wenn der Index (a) in den Index (a, b) geändert wird, kann MySQL den B+-Baum des Index a durch Aufteilen, Zusammenführen usw. direkt in den Index (a, b) ändern.

Es ist nicht erforderlich, einen Index mit einer Präfix-Einschlussbeziehung zu erstellen

Wenn Sie bereits über einen Index (a, b) verfügen, müssen Sie Index (a) nicht erstellen. Falls erforderlich, sollten Sie jedoch dennoch die Erstellung von Index (b) in Betracht ziehen.

Spalten mit hoher Trennschärfe als Index auswählen

Sehr leicht zu verstehen. Wenn beispielsweise das Geschlecht als Index verwendet wird, kann der Index 10 Millionen Datenzeilen nur in zwei Teile aufteilen (z. B. 5 Millionen Männer und 5 Millionen Frauen) und ist nahezu wirkungslos.

Die Formel für die Unterscheidung lautet count(distinct <col>) / count(*), was den Anteil eindeutiger Felder angibt. Je größer der Anteil, desto besser die Unterscheidung. Der eindeutige Schlüssel weist eine Unterscheidung von 1 auf, während einige Status- und Geschlechtsfelder angesichts großer Datenmengen eine Unterscheidung nahe 0 aufweisen können.

Dieser Wert ist schwer zu bestimmen. Im Allgemeinen muss das zu verknüpfende Feld über 0,1 liegen, was bedeutet, dass durchschnittlich 1 Scan 10 Datensätze erfordert.

Das Obige ist der vollständige Inhalt dieses Artikels. Ich hoffe, er wird für jedermanns Studium hilfreich sein. Ich hoffe auch, dass jeder 123WORDPRESS.COM unterstützen wird.