Analyse der Gründe, warum das MySQL-Indexsystem den B + -Baum verwendet

1. Was ist ein Index?

Ein Index ist eine dezentrale Speicherstruktur, die erstellt wird, um das Abrufen von Datenzeilen in einer Tabelle zu beschleunigen. (Genau wie das Wörterbuch, das wir als Kinder benutzt haben, wäre es mit einem Wörterbuch schneller, das entsprechende Wort zu finden)

2. Warum brauchen wir Indizes?

Zuerst müssen wir einige Konzepte und Kenntnisse verstehen

1. Wo werden MySQL-Daten gespeichert? ----Scheibe
2. Wo liegt normalerweise das Problem, wenn die Datenabfrage langsam ist? ----IO
3. (Wir müssen also die IO-Effizienz verbessern. Wie können wir sie also verbessern? ---- Zwei Ebenen der Häufigkeit und Menge. Beispielsweise ist der Aufwand, Steine ​​einmal zu bewegen, unterschiedlich als der, sie zehnmal zu bewegen. Der Aufwand, einen Stein auf einmal zu bewegen, ist ebenfalls unterschiedlich (wobei IO-Ressourcen belegt werden). Daher versuchen wir, die Interaktion mit IO so weit wie möglich zu reduzieren und gleichzeitig unsere eigenen Anforderungen zu erfüllen.)
4. Lesen Sie beim Lesen von Daten von der Festplatte so viele wie nötig? ----Vorablesen der Festplatte
5. Vorablesen der Festplatte: Wenn Daten zwischen Speicher und Festplatte ausgetauscht werden, gibt es normalerweise eine kleinste logische Einheit, die als Seite oder Datenseite bezeichnet wird. Die Größe einer Seite wird im Allgemeinen vom Betriebssystem bestimmt und beträgt normalerweise 4 KB oder 8 KB. Wenn wir Daten austauschen, können wir Daten in ganzzahligen Vielfachen der Seite lesen. Die InnoDB-Speicher-Engine liest jedes Mal 16 KB Daten.
6. Lokalitätsprinzip: Daten und Programme neigen dazu, sich zu gruppieren, und zuvor abgerufene Daten können erneut abgefragt werden, was räumliche und zeitliche Lokalität mit sich bringt.

Durch die oben genannten Konzepte wissen wir ungefähr, wofür der Index verwendet wird – wir entwerfen das Indexsystem im Voraus und reduzieren die Interaktion mit IO, wenn wir Daten abfragen, um unsere Abfrageeffizienz zu verbessern.

3. Wie gestaltet man ein Indexsystem?

Lassen Sie uns zunächst einige Konzepte verstehen

• Wo werden Indizes gespeichert? ---- Festplatte , beim Abfragen von Daten wird zuerst der Index in den Speicher geladen
• Welche Informationen benötigt der Index zum Speichern? Welche Feldwerte müssen gespeichert werden?
  

—— Schlüssel : der in der tatsächlichen Datenzeile gespeicherte Wert - Dateiadresse (Zeiger, wir müssen uns auf die Dateiadresse verlassen, um herauszufinden, wo die Datendatei gespeichert ist)
—— Offset : Offset (wenn wir ein Datenstück in der Datei erhalten möchten, müssen wir den Offset verwenden)

• Welche Art von Datenstruktur sollte verwendet werden, um die Daten im oben genannten Format zu speichern?
  

—— Aus dem Obigen können wir erkennen, dass unser Datenformat vom Typ KV ist. Wenn wir die Daten im KV-Format kennen, wissen wir, welche Datenstruktur wir zum Speichern verwenden müssen, einschließlich Hash-Tabelle , Baum ( Binärbaum , binärer Suchbaum , binär ausgeglichener Baum , Rot-Schwarz-Baum , B-Baum , B+-Baum )
Zusammenfassend können wir die obige Datenstruktur verwenden, um unser Indexsystem zu entwerfen

4. Was ist das MySQL-Indexsystem?

Warum speichern Sie es nicht im oben genannten Format?

Wie wir alle wissen, verwendet das Indexsystem von MySQL einen B+-Baum . Warum ist es ein B+-Baum? Als nächstes analysieren wir nacheinander, warum andere Speicherstrukturen nicht funktionieren. Zuvor müssen wir noch zwei Voraussetzungen verstehen: OLAP und OLTP

Je mehr Daten wir speichern, desto größer wird der entsprechende Index sein. Wenn wir von der Festplatte in den Speicher lesen, treten IO-Probleme auf. Erstellen wir also Indizes für Indizes? Nein, MySQL verwendet den B+-Baum

5. Hash-Tabelle

Oben ist die Speicherstruktur der Hash-Tabelle. Lassen Sie uns die Vor- und Nachteile dieser Art von Speicherstruktur diskutieren:

• Hash-Kollisionen führen zu ungleichmäßigem Daten-Hashing und generieren eine große Anzahl linearer Abfragen, was zeitaufwändig ist.
• Bereichsabfragen werden nicht unterstützt . Bei der Durchführung von Bereichsabfragen müssen Sie jeden
• Der Speicherplatzbedarf ist relativ hoch (alle Daten müssen dem Speicher hinzugefügt werden)
  

Vorteil:
Wenn es sich um eine gleichwertige Abfrage handelt, wird es sehr schnell sein

Gibt es also einen Hash-Index in MySQL?

• Die Speicher-Speicher-Engine verwendet einen Hash-Index.
• InnoDB unterstützt adaptives Hashing

6. Baum

6.1 Binärer Baum

Der Binärbaum selbst ist ungeordnet. Wenn wir nach Daten suchen, müssen wir die Daten mit jedem Knoten einzeln vergleichen, um zu sehen, ob sie unseren Datenanforderungen entsprechen, was ineffizient ist.

6.2 Binärer Suchbaum (BST)

Merkmale des binären Suchbaums: Die Daten müssen in der richtigen Reihenfolge eingefügt werden, der linke Teilbaum muss kleiner als der Wurzelknoten sein und der rechte Teilbaum muss garantiert größer als der Wurzelknoten sein. Daher verbessert die Verwendung eines binären Suchbaums im Vergleich zu einem binären Baum offensichtlich die Abfrageeffizienz.
Wenn die Daten jedoch in aufsteigender oder absteigender Reihenfolge eingefügt werden, degeneriert der binäre Suchbaum zu einer verknüpften Liste und die Suchleistung verringert sich.

6.3 Ausgeglichener Binärbaum (AVL-Baum)

Entsprechend den durch den binären Suchbaum aufgedeckten Problemen verwenden wir den AVL-Baum, um den Baum durch Links- oder Rechtsrotation auszugleichen. Um jedoch ein Gleichgewicht zu gewährleisten, ist beim Einfügen von Daten eine Rotation erforderlich, bei der die Verbesserung der Abfrageleistung durch den Verlust der Einfügeleistung ausgeglichen wird . Es ist ok, wenn ich mehr lese und weniger schreibe, aber wenn ich die gleiche Anzahl an Lese- und Schreibanfragen habe, ist es nicht geeignet.

6.4 Rot-Schwarz-Bäume

Der rot-schwarze Baum wird auch durch Links- und Rechtsrotationen ausgeglichen und weist auch ein Farbwechselverhalten auf. Der längste Teilbaum muss nur nicht länger als doppelt so lang sein wie der kürzeste Teilbaum … daher können die Abfrageleistung und die Einfügeleistung ungefähr ausgeglichen werden . Beim Einfügen von Daten stellt sich jedoch heraus, dass die Tiefe des Baums größer wird. Je größer die Tiefe, desto mehr IO-Zeiten hat er, was sich auf die Effizienz des Datenlesens auswirkt.

6.5 B-Bäume

Wie können wir angesichts der durch den Rot-Schwarz-Baum aufgedeckten Probleme die Lese-Effizienz verbessern? Können wir von einem geordneten Binärbaum zu einem geordneten mehrverzweigten Baum wechseln, damit wir mehr Daten speichern können?

Ein Grad von 4 bedeutet, dass ein Knoten drei Datenwerte speichert und alle darüber hinausgehenden Werte transformiert werden müssen. Wie werden also die eigentlichen Daten gespeichert? Wir benötigen den Schlüssel und die komplette Datenzeile

Das obige Bild zeigt, wie der B-Baum tatsächlich Daten speichert. Jeder Knoten hat drei Elemente: Schlüssel , Zeiger und Daten .
Wenn ich beispielsweise die Daten 28 finden möchte, beginne ich zunächst mit Datenträgerblock 1 und stelle fest, dass sie nicht gelesen werden können. Nach dem Vergleich des Bereichs mit Datenträgerblock 3, auf den der Zeiger p2 zeigt, können sie immer noch nicht gefunden werden. Dann finde ich 28 gemäß dem Zeiger p2 von Datenträgerblock 3, der auf Datenträgerblock 8 zeigt. Lassen Sie uns das analysieren. Jeder Festplattenblock ist 16 KB groß . Wir müssen nur 48 KB lesen, um drei Festplattenblöcke zu durchsuchen. Wie viele Datensätze kann ein dreischichtiger B-Baum speichern ?

Idealisieren wir es und nehmen an, dass Schlüssel und Zeiger keinen Platz beanspruchen und ein Datenelement 1 KB Speicherplatz beansprucht. Dann kann Datenträger 1 16 Datenelemente speichern, Datenträger 3 hat ebenfalls 16 Datenelemente und Datenträger 8 hat ebenfalls 16 Datenelemente. In diesem Fall können wir nur 16 + 16 + 16 = 4096 Datensätze speichern, was offensichtlich etwas zu wenig ist. Tatsächlich beanspruchen Schlüssel und Zeiger auch Speicherplatz.

Daher fragen wir uns unweigerlich: Warum ist die Menge der gespeicherten Daten so gering?
Wir stellen fest, dass die Größe jeder Speicherebene durch Daten belegt ist. Können wir also nur Schlüssel und Zeiger speichern? Aus diesem Grund wird der B+-Baum eingeführt

6.6 B+Baum

Die Entwicklung vom B-Baum zum B+-Baum: Nicht-Blattknoten speichern keine Daten, nur Blattknoten speichern Daten

In der obigen Abbildung können wir davon ausgehen, dass p1 und 28 eine Gruppe von 10 Bytes sind, sodass die erste Schicht eine Größe von 16000/10 = 1600 speichern kann, die zweite Schicht ebenfalls 1600 und die Daten der dritten Schicht 1 KB belegen, was 16 Datensätzen entspricht. Der Gesamtspeicherplatz beträgt also 1600 1600 16 = 40960000 ( 40,96 Millionen ) Datensätze.

Die MySQL-Indexstruktur besteht im Allgemeinen aus drei bis vier Ebenen, es gibt jedoch ein Problem, das beachtet werden muss. Angenommen, wir haben eine dreischichtige Speicherstruktur. Wie können wir mehr Daten speichern?
Wir haben gerade angenommen, dass p1 und 28 10 Byte groß sind. Was ist, wenn sie 1 Byte groß sind? Dann beträgt die gesamte Speicherkapazität 16000 16000 10=4096000000. Dies führt zu der Frage, die in Interviews immer gestellt wird: Ist es besser, zum Erstellen von Indizes int oder var zu verwenden?

Antwort: Je kürzer die Schlüssellänge, desto besser. Für varchar mit einer Länge von weniger als 4 Bytes verwenden Sie varchar; für varchar mit einer Länge von mehr als 4 Bytes verwenden Sie int.

Gemäß den Eigenschaften des B+-Baums verfügt er über eine große Speicherkapazität und ermöglicht schnelle Abfragen, daher verwendet MySQL den B+-Baum.

Zusammenfassen

Damit ist die Erklärung, warum das MySQL-Indexsystem B+-Bäume verwendet, abgeschlossen. Wenn ich etwas Falsches gesagt habe, hoffe ich, dass Sie mich daran erinnern und es korrigieren können.

Damit ist dieser Artikel darüber, warum das MySQL-Indexsystem B+-Bäume verwendet, abgeschlossen. Weitere Informationen zu MySQL-Index-B+-Bäumen 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!