Detaillierte Einführung in den MySQL-Datenbankindex

Wenn Sie verstehen möchten, warum MySQL Daten schnell abrufen kann, müssen Sie das Indexprinzip von MySQL verstehen.

Mindmap

Einfaches Verständnis

Sie können sich den Index als das Inhaltsverzeichnis eines Buches vorstellen. Wir können den Index verwenden, um schnell die Daten zu finden, die wir benötigen. Das sieht ungefähr so ​​aus wie in der Abbildung unten. Der Index ist wie der Binärbaum auf der rechten Seite. Jeder Knoten zeigt auf die physische Adresse bestimmter Daten. Suchen Sie zuerst den Speicherort der Daten über den Binärbaum und holen Sie sich dann die Daten von der physischen Festplatte.

Allerdings haben verschiedene Binärbäume unterschiedliche Eigenschaften, und wir müssen auch einen geeigneten Baum als Index auswählen. Lernen wir also die Eigenschaften jedes Baums kennen.

Entwicklung von Indexierungsmodellen

Binärer Suchbaum

Ein binärer Suchbaum basiert auf einem Array und verwendet die binäre Suchtechnik, um die Zwischenknoten als Zeiger zu verwenden. Auf diese Weise ist der Wert des linken Teilbaums jedes Knotens kleiner als der Wert des Knotens und der Wert des rechten Teilbaums jedes Knotens größer als der Wert des Knotens. Bei der Suche nach einem Element können wir nach dem Vergleich mit dem Stammknoten jedes Mal fast die Hälfte des Suchbereichs entfernen, was die Suche erheblich beschleunigen kann.

Vorteil:

Einfach einzusetzen, keine Reihenanordnung nötig

Mit den einzigartigen Funktionen des Baums ist es sehr bequem zu suchen

Mangel:

Wenn jedes Mal der Maximalwert eingefügt wird, entsteht eine verknüpfte Liste und die Suchkomplexität erhöht sich.

Je mehr Elemente Sie einfügen, desto höher wird der Baum, was zu einer schlechteren Abfrageleistung führt.

Selbstausgleichender Binärbaum

Im Vergleich zu einem Binärbaum stellt ein selbstausgleichender Binärbaum durch Rotation nach links oder rechts sicher, dass der Höhenunterschied zwischen dem linken und dem rechten Teilbaum eins nicht überschreitet. Dadurch wird das Problem gelöst, einen binären Suchbaum in eine verknüpfte Liste umzuwandeln.

Bei mehr Elementen kann die Höhe des Baums jedoch leicht sehr groß werden, was die Abfrageeffizienz beeinträchtigt. Um dieses Problem zu lösen, wurde B-Tree entwickelt.

B-Baum

Der größte Unterschied beim B-Baum besteht darin, dass er nicht mehr auf nur einen Knoten beschränkt ist, sondern mehrere Knoten zulässt, d. h. einen Baum mit mehreren Verzweigungen. Und alle Blattknoten des B-Baumes müssen auf der gleichen Ebene liegen, das heißt, sie müssen die gleiche Tiefe haben

Wenn beispielsweise ein B-Baum mit Grad d N Schlüssel indiziert, dann ist die Obergrenze seiner Baumhöhe h logn(N/2). Die asymptotische Komplexität der Suche nach einem Schlüssel in der Anzahl der Knoten beträgt O(logn((N+1)/2)). Von diesem Punkt aus können wir erkennen, dass B-Tree eine sehr effiziente Indexdatenstruktur ist.

Lokalitätsprinzip

Diese Mehrknotenstruktur kann auch die Funktion zum Vorlesen der Festplatte gut nutzen.

Aufgrund der Eigenschaften von Speichermedien ist der Festplattenzugriff selbst viel langsamer als der Hauptspeicher. Zusätzlich zum mechanischen Bewegungsverbrauch beträgt die Festplattenzugriffsgeschwindigkeit oft einige Hundertstel der Hauptspeichergeschwindigkeit. Um die Effizienz zu verbessern, sollte daher der Festplatten-E/A minimiert werden. Um dieses Ziel zu erreichen, wird die Platte oft nicht strikt bei Bedarf ausgelesen, sondern jedes Mal vorab. Selbst wenn nur ein Byte benötigt wird, startet die Platte an dieser Stelle und liest eine bestimmte Datenlänge sequenziell rückwärts in den Speicher ein. Die theoretische Grundlage hierfür ist das berühmte Lokalitätsprinzip der Informatik: Wenn ein Datenelement verwendet wird, werden in der Regel sofort auch die nahegelegenen Daten verwendet. Die während der Programmausführung benötigten Daten werden üblicherweise konzentriert. Da sequentielles Lesen auf der Festplatte sehr effizient ist (es ist keine Suchzeit und nur eine geringe Rotationszeit erforderlich), kann das Vorlesen die E/A-Effizienz für Programme mit Lokalität verbessern.

In einem B-Baum wird die Größe eines Knotens auf eine Seite festgelegt, sodass jeder Knoten mit nur einem I/O vollständig geladen werden kann. Um dieses Ziel zu erreichen, sind bei der tatsächlichen Implementierung von B-Tree die folgenden Techniken erforderlich: <br /> Jedes Mal, wenn ein neuer Knoten erstellt wird, wird direkt eine Seite Speicherplatz angefordert. Dadurch wird sichergestellt, dass ein Knoten physisch auf einer Seite gespeichert wird. Darüber hinaus wird die Computerspeicherzuweisung seitenweise ausgerichtet, sodass ein Knoten nur einen I/O benötigt.

Jeder Knoten des B-Baums enthält jedoch Daten (Index + Datensatz), und die Größe der Datensatzdaten des Benutzers übersteigt wahrscheinlich die Indexdaten bei weitem, sodass mehr Festplatten-E/A-Vorgänge erforderlich sind, um „nützliche Indexdaten“ zu lesen. Wenn wir außerdem einen Knoten auf der untersten Ebene abfragen (z. B. einen Datensatz A), werden die Datensatzdaten im „Nicht-A-Datensatzknoten“ von der Festplatte in den Speicher geladen, aber diese Datensatzdaten sind nutzlos. Wir möchten nur die Indexdaten dieser Knoten für Vergleichsabfragen lesen, und die Datensatzdaten im „Nicht-A-Datensatzknoten“ sind für uns nutzlos. Dies erhöht nicht nur die Anzahl der Festplatten-E/A-Vorgänge, sondern belegt auch Speicherressourcen.

B+ Baum

MySQL verwendet im Allgemeinen einen B + -Baum, um seine Indexstruktur zu implementieren. Im Vergleich zum B-Baum weist der B + -Baum die folgenden Unterschiede auf

Blattknoten (unterste Knoten) speichern tatsächliche Daten (Index + Datensatz), während Nicht-Blattknoten nur Indizes speichern.

Alle Indizes werden in Blattknoten angezeigt und die Blattknoten bilden eine geordnete verknüpfte Liste.

Der Index von Nicht-Blattknoten ist auch in den untergeordneten Knoten vorhanden und ist das Maximum (oder Minimum) aller Indizes in den untergeordneten Knoten.

Es gibt so viele Indizes wie untergeordnete Knoten in einem Nicht-Blattknoten.

Die Nicht-Blattknoten des B+-Baums speichern keine tatsächlichen Datensatzdaten, sondern nur Indizes. Wenn die Datenmenge gleich ist, können die Nicht-Blattknoten des B+-Baums im Vergleich zum B-Baum, der sowohl Indizes als auch Datensätze speichert, daher mehr Indizes speichern. Daher kann der B+-Baum „kürzer und dicker“ sein als der B-Baum, und die Anzahl der Festplatten-E/A-Vorgänge zum Abfragen der zugrunde liegenden Knoten ist geringer.

Als mehrzweigiger Baum verursacht B+ selbst bei einer großen Anzahl redundanter Knoten keine komplexe Baumverformung beim Löschen oder Einfügen von Knoten.

In der Datenbank wird ebenfalls eine Optimierung auf Basis des B+-Baums durchgeführt und es werden sequentielle Zugriffszeiger hinzugefügt. Der Zweck dieser Optimierung besteht darin, die Leistung des Intervallzugriffs zu verbessern. Wenn Sie beispielsweise alle Datensätze mit Schlüsseln von 18 bis 49 abfragen möchten, müssen Sie nach dem Finden von 18 nur die Knoten und Zeiger durchlaufen, um auf alle Datenknoten gleichzeitig zuzugreifen, was die Effizienz der Intervallabfrage erheblich verbessert. <br />Der B-Baum hat keine Struktur, die alle Blattknoten in Reihe mit einer verknüpften Liste verbindet. Bereichsabfragen können daher nur durch Durchlaufen des Baums abgeschlossen werden, was Festplatten-E/A-Operationen auf mehreren Knoten erfordert. Die Effizienz der Bereichsabfrage ist nicht so gut wie die des B+-Baums. Daher eignen sich B+-Bäume für Szenarien mit einer großen Anzahl von Bereichsabrufen, beispielsweise Datenbanken. Für Szenarien mit einer großen Anzahl einzelner Indexabfragen können Sie B-Tree-Modelle wie MongoDB von NoSQL in Betracht ziehen.

In MySQL sind die Blattknoten des B+-Baums durch eine „bidirektionale verknüpfte Liste“ verbunden, die den Vorteil hat, dass sie sowohl von rechts als auch von links durchlaufen werden kann.

Clustered-Index und Sekundärindex

Clustered Index (Primärschlüsselindex): fügt Daten und Index zusammen. Die Blattknoten der Indexstruktur speichern Zeilendaten. Beim Suchen des Index werden auch die Daten gefunden.

Sekundärindex (Nicht-Primärschlüsselindex): Daten und Index werden getrennt gespeichert. Die Blattknoten der Indexstruktur speichern den Primärschlüsselwert.

Wenn InnoDB einen gruppierten Index erstellt, wählt es je nach Szenario unterschiedliche Spalten als Indizes aus:

Wenn ein Primärschlüssel vorhanden ist, wird dieser standardmäßig als Indexschlüssel des gruppierten Indexes verwendet.

Wenn kein Primärschlüssel vorhanden ist, wählen Sie die erste eindeutige Spalte, die keine NULL-Werte enthält, als Indexschlüssel des gruppierten Index aus.

Wenn die beiden oben genannten Fälle nicht vorliegen, generiert InnoDB automatisch eine implizite Auto-Increment-ID-Spalte als Indexschlüssel des gruppierten Index.

Da die Daten in der Tabelle in den Blattknoten des Clusterindex gespeichert sind, erstellt die InnoDB-Speicher-Engine definitiv einen Clusterindex für die Tabelle. Und da nur eine Kopie der Daten physisch gespeichert wird, kann nur ein Clusterindex vorhanden sein, es können jedoch mehrere sekundäre Indizes erstellt werden.

Beispielsweise sind die (ID, k)-Werte in der Abbildung (100, 1), (200, 2), (300, 3), (500, 5) und (600, 6).

Der Unterschied bei der Abfrage:

Wenn die Anweisung „select * from T where ID=500“ lautet, also die Abfragemethode für Primärschlüssel, muss nur der B+-Baum der ID durchsucht werden.

Wenn die Anweisung „select * from T where k=5“ lautet, also der normalen Indexabfragemethode, müssen Sie zuerst den k-Indexbaum durchsuchen, um den ID-Wert 500 zu erhalten, und dann den ID-Indexbaum erneut durchsuchen. Dieser Vorgang wird als Tabellenrückgabe bezeichnet.

Mit anderen Worten: Abfragen, die auf Nicht-Primärschlüsselindizes basieren, müssen einen weiteren Indexbaum scannen. Daher sollten wir versuchen, in unseren Anwendungen Primärschlüsselabfragen zu verwenden.

Zusammenfassen

Dies ist das Ende dieses Artikels über die detaillierte Einführung in den MySQL-Datenbankindex. Weitere relevante MySQL-Indexinhalte finden Sie in früheren Artikeln auf 123WORDPRESS.COM oder in den verwandten Artikeln weiter unten. Ich hoffe, dass jeder 123WORDPRESS.COM in Zukunft unterstützen wird!