Detaillierte Einführung in den MySQL Innodb Index-Mechanismus

1. Was ist ein Index?

Ein Index ist eine Datenstruktur, die von der Speicher-Engine zum schnellen Auffinden von Datensätzen verwendet wird.

2. Welche Datenstrukturen hat der Index?

• Sequentielle Suchstruktur: Diese Sucheffizienz ist sehr niedrig und die Komplexität ist O(n). Bei großen Datenmengen ist die Abfrageeffizienz sehr gering.
• Geordnete Datenanordnung: Die binäre Suche wird auch Halbsuche genannt.

Durch einen einmaligen Vergleich wird der Suchbereich auf die Hälfte reduziert. Die Daten in MySQL sind keine geordnete Sequenz.

• Binärer Suchbaum: Der Schlüsselwert des linken Teilbaums ist immer kleiner als der Schlüsselwert der Wurzel, und der Schlüsselwert des rechten Teilbaums ist immer größer als der Schlüsselwert der Wurzel. Die durch In-Order-Traversierung erhaltene Sequenz ist eine geordnete Sequenz, aber wenn der binäre Suchbaum nicht gut aufgebaut ist, unterscheidet sie sich nicht von einer sequentiellen Suche.

• Ausgeglichener Binärbaum: Wenn der binäre Suchbaum ausgeglichen werden muss, wird ein ausgeglichener Binärbaum abgeleitet. Ein balancierter Binärbaum muss erstens die Definition eines binären Suchbaums erfüllen und zweitens muss der maximale Höhenunterschied zwischen den beiden Teilbäumen eines beliebigen Knotens 1 betragen. Offensichtlich ist der obige Baum kein balancierter Binärbaum. Ein Beispiel für einen balancierten Binärbaum ist wie folgt:

Die zeitliche Komplexität eines ausgeglichenen binären Suchbaums beträgt O(logN). Die Abfragegeschwindigkeit ist zwar sehr hoch, aber die Kosten für die Pflege eines ausgeglichenen binären Baums sind auch sehr hoch. Normalerweise sind eine oder mehrere Links- und Rechtsdrehungen erforderlich, um nach einer Einfügung oder Aktualisierung das Gleichgewicht zu erreichen.

• B-Baum: Der Unterschied zwischen B-Baum und balanciertem Binärbaum besteht darin, dass der B-Baum ein Mehrwegebaum ist, auch als balancierter Mehrwegesuchbaum bezeichnet:

1. Der Stammknoten hat mindestens zwei untergeordnete Knoten (jeder Knoten hat M-1 Schlüssel, in aufsteigender Reihenfolge angeordnet) und andere Knoten haben mindestens M/2 untergeordnete Knoten.
2. Die Blattknoten liegen alle auf derselben Ebene.

• B+ Baum

Der B+-Baum ist eine Variante des B-Baums, die sich aus dem B-Baum und der Methode des indexsequentiellen Zugriffs entwickelt hat (der B-Baum wird im wirklichen Leben selten verwendet).
Der B+-Baum ist ein ausgeglichener Suchbaum, der für Festplatten oder andere Zusatzgeräte zur direkten Speicherung entwickelt wurde.
In einem B+-Baum werden alle Datensatzknoten in der Reihenfolge ihrer Schlüsselwerte auf den Blattknoten derselben Ebene platziert und durch Blattknotenzeiger verbunden.
Alle Abfragen müssen Blattknoten finden und die Abfrageleistung ist stabil.
Alle Blattknoten bilden eine geordnete verknüpfte Liste, um Bereichsabfragen zu erleichtern. Jeder Blattknoten speichert Zeiger auf benachbarte Blattknoten, und die Blattknoten selbst sind entsprechend der Größe des Schlüsselworts in aufsteigender Reihenfolge verknüpft (bidirektionale verknüpfte Liste).

3. Warum verwendet Innodb den B+-Baum als Index?

1. Das System kann die Blockleseeigenschaften der Festplatte effektiv nutzen, um beim Lesen desselben Festplattenblocks möglichst viele Indexdaten zu laden und so die Indextreffereffizienz zu verbessern und so die Anzahl der Festplatten-E/A-Lesevorgänge zu verringern (Lokalitätsprinzip und Festplattenvorlesen).
2. Die Lese- und Schreibkosten für die Festplatte eines B+-Baums sind geringer: Die internen Knoten eines B+-Baums haben keine Zeiger auf die spezifischen Informationen der Schlüsselwörter (nur Blattknoten speichern sie), sodass seine internen Knoten kleiner sind als die eines 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.
3. Die Abfrageeffizienz des B+-Baums ist stabiler. Da der Nicht-Endpunkt nicht der Knoten ist, der letztendlich auf den Dateiinhalt verweist, handelt es sich lediglich um einen 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.
4. B+-Bäume unterstützen Bereichsabfragen, B-Bäume hingegen nicht.

4. Indexklassifizierung

Klassifizierung anhand der Speicherstruktur: BTree-Index, Hash-Index, Volltext-Index

Klassifizierung aus der Anwendung: Primärschlüsselindex, eindeutiger Index, zusammengesetzter Index

Aus Sicht der physischen Speicherung: Clustered-Index und Nicht-Clustered-Index (Hilfsindex)

Lassen Sie uns darüber sprechen, was ein gruppierter Index und was ein nicht gruppierter Index ist:

• Gruppierter Index

Ein B+-Baum wird entsprechend dem Primärschlüssel jeder Tabelle erstellt und die Zeilendatensätze der gesamten Tabelle werden im Blattknoten gespeichert. Die Blattknoten des gruppierten Index werden auch Datenseiten genannt, und jede Datenseite ist über eine doppelt verknüpfte Liste verknüpft.

Clustered-Indizes sind für sortierte und Bereichssuchen des Primärschlüssels sehr schnell.

• Hilfsindex

Zusätzlich zur Speicherung der Indexspalte wird auch der Zeiger auf den Blattknoten gespeichert.

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.