MySQL-Lernen (VII): Detaillierte Erläuterung des Implementierungsprinzips des Innodb Storage Engine-Index

Überblick

In einer Datenbank wird ein Index verwendet, um die Datensuche zu beschleunigen, genau wie ein Baumverzeichnis. Bei einer SQL-Abfrageoperation kann der Index verwendet werden, um schnell Daten herauszufiltern, die die Anforderungen nicht erfüllen, und Daten zu finden, die die Anforderungen erfüllen. Dadurch ist es nicht mehr nötig, die gesamte Tabelle zu durchsuchen, um die erforderlichen Daten zu erhalten.

In der InnoDB-Speicher-Engine basiert die Indizierung hauptsächlich auf B+-Bäumen. Indexschlüsselwörter werden in Nicht-Blattknoten gespeichert, und Datensätze oder Primärschlüsselwerte in Primärschlüsselindizes (oder gruppierten Indizes) werden in Blattknoten gespeichert. Alle Datensätze befinden sich in derselben Schicht, und Blattknoten, d. h. Datensätze, sind durch Zeiger direkt verbunden, um eine bidirektionale verknüpfte Liste zu bilden, die das Durchlaufen aller oder eines Bereichs von Datensätzen erleichtert.

B-Baum, B+Baum

Sowohl der B-Baum als auch der B+-Baum sind mehrseitig ausgeglichene Suchbäume, die die Höhe des Baums reduzieren, indem sie in jedem Knoten mehr Schlüsselwörter speichern und den Baum durch Rotations- und Aufteilungsvorgänge ausgewogen halten, wodurch die Anzahl der Festplattenzugriffe zum Abrufen von Daten reduziert wird.

Ein wesentlicher Unterschied zwischen dem B+-Baum und dem B-Baum besteht darin, dass die Blattknoten von B+ vorne und hinten über Zeiger verbunden sind, und zwar insbesondere über eine doppelt verknüpfte Liste, sodass er sich sehr gut für die Durchführung von Bereichssuchen eignet. Nähere Informationen finden Sie unter:

Datenstruktur - Baum (III): Mehrweg-Suchbaum B-Baum, B+ Baum

Die gruppierten und nicht gruppierten Indizes der InnoDB-Speicher-Engine werden basierend auf B+-Bäumen implementiert.
Primärschlüsselindex

Die InnoDB-Speicher-Engine verwendet den Primärschlüsselindex als Clusterindex der Tabelle. Die Eigenschaft des Clusterindex besteht darin, dass die Nicht-Blattknoten den Primärschlüssel als Suchbegriff speichern und die Blattknoten die eigentlichen Datensätze selbst (auch Datenseiten genannt) speichern. Datensätze werden in der Reihenfolge der Schlüsselwörter von links nach rechts gespeichert. Daher ist der Clusterindex tatsächlich die Art und Weise, wie Daten gespeichert werden. Daher kann jede Tabelle nur einen Clusterindex haben. Die Datentabelle der InnoDB-Speicher-Engine wird auch als indexorganisierte Tabelle bezeichnet. Der Aufbau ist wie folgt: (Bild aus „MySQL Technology Insider: Innodb Storage Engine“)

Wenn Sie in der Abfrage nach Daten per Primärschlüssel suchen, d. h. wenn der SQL-Schlüssel der Explain-Analyse PRIMARY anzeigt, ist die Suchleistung am höchsten, weil der Blattknoten den Datensatz selbst speichert und dieser daher wie bei einem nicht gruppierten Index direkt zurückgegeben werden kann, ohne dass eine zusätzliche Tabellenabfrage (im Primärschlüsselindex) erforderlich ist, um den Datensatz abzurufen.

Zweitens wird bei ORDER BY-Sortiervorgängen, egal ob ASC oder DESC, der B+-Baum entsprechend dem Primärschlüsselindex sortiert, wenn die ORDER BY-Spalte der Primärschlüssel ist, sodass die von der Speicher-Engine zurückgegebenen Daten bereits entsprechend dem Primärschlüssel sortiert sind und nicht auf MySQL-Serverebene sortiert werden müssen, was die Leistung verbessert. Wenn das SQL über Explain analysiert wird und zusätzlich „Filesort verwenden“ angezeigt wird, bedeutet dies, dass eine Sortierung auf MySQL-Serverebene erforderlich ist. Zu diesem Zeitpunkt müssen Sie möglicherweise eine temporäre Tabelle oder eine externe Dateisortierung verwenden. In diesem Fall müssen Sie im Allgemeinen einen Weg finden, dies zu optimieren.

Bei Bereichssuchen auf Basis von Primärschlüsseln können Datensätze in einem bestimmten Bereich schnell gefunden werden, da die Blattknoten des gruppierten Indexes über eine bidirektionale verknüpfte Liste entsprechend der Reihenfolge der Primärschlüssel verbunden sind.

Hilfsindex

Ein Hilfsindex, auch Sekundärindex genannt, ist ein nicht gruppierter Index, der im Allgemeinen dazu dient, die Effizienz bestimmter Abfragen zu verbessern. Das heißt, bei Abfragen mithilfe der Indexspalte wird der Hilfsindex verwendet, um einen vollständigen Tabellenscan zu vermeiden. Da der Hilfsindex kein gruppierter Index ist, kann jede Tabelle mehrere Hilfsindizes mit der folgenden Struktur haben:

Die Nicht-Blattknoten des Hilfsindex speichern die Schlüsselwörter der Indexspalte, und die Blattknoten speichern die Primärschlüsselwerte des entsprechenden gruppierten Index (oder Primärschlüsselindex). Das heißt, wenn nach dem Auffinden der erforderlichen Daten über den Hilfsindex die erforderlichen Spalten nicht durch den Index abgedeckt werden können, d. h. um alle für die Abfrage erforderlichen Datenspalten über die Hilfsindexspalte zu erhalten, muss der Primärschlüssel im Clusterindex über den Primärschlüsselwert des entsprechenden Clusterindex gefunden werden und dann die entsprechende Blattseite im Clusterindex über den Primärschlüsselwert gefunden werden, um den entsprechenden Datensatz zu erhalten. Daher umfasst der gesamte Prozess zwei Prozesse: zuerst die Suche im Hilfsindex und dann die Suche im Clusterindex (d. h. im Primärschlüsselindex) (Backtable-Abfrage).

Zum Beispiel:

1. Die Höhe des B+-Baums, der dem Hilfsindex entspricht, beträgt 3, sodass 3 Festplatten-E/A-Vorgänge erforderlich sind, um den Blattknoten zu lokalisieren, wobei der Blattknoten einen Primärschlüsselwert des entsprechenden gruppierten Index enthält.
2. Anschließend wird der entsprechende Datensatz im Clustered-Index über den Primärschlüsselwert des entsprechenden Clustered-Index des Blattknotens gefunden. Das heißt, wenn die Höhe des dem Clustered-Index entsprechenden B+-Baums ebenfalls 3 beträgt, sind auch 3 Festplatten-E/A-Vorgänge erforderlich, um die Blattseite des Clustered-Index zu lokalisieren und so den tatsächlichen Datensatz auf der Blattseite zu erhalten.

Der obige Vorgang erfordert insgesamt 6 Festplatten-E/A. Wenn daher viele Datenzeilen abgefragt werden müssen, steigt die erforderliche Festplatten-E/A exponentiell an und die Abfrageleistung nimmt ab. Daher ist es notwendig, Hilfsindizes für Spalten mit einem hohen Filterungsgrad zu erstellen, d. h. für Spalten mit weniger doppelten Daten.

Kardinalität: Die Datenverdoppelung der Indexspalte

Aus der obigen Analyse können wir ersehen, dass bei Abfragen über Hilfsindizes, wenn Sie die Tabelle zurück abfragen müssen und viele Datenzeilen abzufragen sind, eine große Menge an Festplatten-E/A erforderlich ist, um Daten abzurufen. Daher verbessert dieser Index nicht nur nicht die Abfrageleistung, sondern verringert auch die Abfrageleistung. Wenn der MySQL-Optimierer außerdem viele Datenzeilen zurückgeben muss, gibt er die Verwendung des Indexes auf und führt direkt einen vollständigen Tabellenscan durch. Daher müssen die vom Hilfsindex ausgewählten Spalten Spalten mit geringer Duplizierung sein, d. h. nach einer allgemeinen Abfrage müssen nur eine oder zwei Datenzeilen zurückgegeben werden. Wenn diese Spalte zu viele doppelte Werte enthält, müssen Sie in Erwägung ziehen, auf die Erstellung eines sekundären Indexes für diese Spalte zu verzichten.

Insbesondere können Sie SHOW INDEX FROM verwenden, um den Kardinalitätswert zu bestimmen:

mysql> INDEX AUS store_order ANZEIGEN;
+---------------+------------+------------+-----------+--------------+---------------+--------------+-------------+-----------+----------+--------+---------+---------+---------+---------+---------+---------+-----------+
| Tabelle | Nicht_eindeutig | Schlüsselname | Sequenz_im_Index | Spaltenname | Sortierung | Kardinalität | Unterteil | Gepackt | Null | Indextyp | Kommentar | Indexkommentar |
+---------------+------------+------------+-----------+--------------+---------------+--------------+-------------+-----------+----------+--------+---------+---------+---------+---------+---------+---------+-----------+
| store_order | 0 | PRIMARY | 1 | store_id | A | 201 | NULL | NULL | | BTREE | | |
| store_order | 1 | idx_expire | 1 | expire_date | A | 68 | NULL | NULL | JA | BTREE | | |
| store_order | 1 | idx_ul | 1 | ul | A | 22 | NULL | NULL | JA | BTREE | | |
+---------------+------------+------------+-----------+--------------+---------------+--------------+-------------+-----------+----------+--------+---------+---------+---------+---------+---------+---------+-----------+
3 Zeilen im Satz (0,01 Sek.)

Die Kardinalität gibt die geschätzte Anzahl eindeutiger Werte in der Indexspalte an. Wenn sie nahe an der Anzahl der Datenzeilen liegt, bedeutet dies, dass die Spalte nur wenige doppelte Werte enthält und die Spalte eine gute Filterleistung aufweist. Wenn der Unterschied zu groß ist, d. h. der Wert der Kardinalität/Gesamtzahl der Datenzeilen zu klein ist, z. B. wenn die Spalte „Geschlecht“ nur zwei Werte enthält, „männlich“ und „weiblich“, bedeutet dies, dass die Spalte eine große Anzahl doppelter Werte enthält und Sie überlegen müssen, ob Sie den Index löschen möchten.

Abdeckungsindex

1. Da der Overhead einer Tabellenrückgabeabfrage groß ist, können alle für die Abfrage erforderlichen Spalten zum Hilfsindex hinzugefügt werden, um die Anzahl der Tabellenrückgabeabfragen zu verringern, z. B. durch Verwendung eines gemeinsamen Indexes. Auf diese Weise können alle für die Abfrage erforderlichen Daten aus dem Hilfsindex abgerufen werden (da die Blattseite des Hilfsindexes den Primärschlüsselwert enthält, wird ein überdeckender Index verwendet, wenn nur der Primärschlüsselwert und die Indexspalte zurückgegeben werden müssen, auch wenn der Index keinen Primärschlüsselwert hat). Es ist nicht erforderlich, zur Tabelle zurückzukehren, um die vollständige Datenzeile abzufragen, wodurch die Leistung verbessert wird. Dieser Mechanismus wird als überdeckender Index bezeichnet.
2. Wenn bei der Verwendung von „Explain“ zur Analyse der SQL-Abfrage zusätzlich der „Using“-Index angezeigt wird, bedeutet dies, dass zur Datenrückgabe ein überdeckender Index verwendet wird und die Abfrageleistung hoch ist.
3. Da das Vorhandensein von Indizes den Aufwand für die Datenaktualisierung erhöht, müssen beim Aktualisieren von Daten, z. B. beim Hinzufügen und Löschen von Datenzeilen, die entsprechenden Hilfsindizes aktualisiert werden. Daher muss im spezifischen Design ein Kompromiss zwischen beiden geschlossen werden.

Der gemeinsame Index entspricht dem am weitesten links stehenden Stempel.

1. Ein gemeinsamer Index verwendet mehrere Spalten als Indizes, z. B. (a, b, c), was bedeutet, dass die Spalten a, b und c als Indizes verwendet werden. Gemäß den Eigenschaften des B+-Baums müssen die Indizes mit dem am weitesten links stehenden Vorwärts-Sigma übereinstimmen, sodass dies tatsächlich dem Erstellen von drei Indizes entspricht: a, (a, b) und (a, b, c).
2. Daher müssen Sie beim Entwerfen eines gemeinsamen Indexes nicht nur überlegen, ob er zu einem abdeckenden Index optimiert werden kann, sondern auch die Reihenfolge mehrerer Spalten berücksichtigen. Die allgemeine Erfahrung ist, dass die Spalte mit der höchsten Abfragehäufigkeit und der besten Filterfähigkeit (weniger doppelte Werte) vorne, also links, platziert wird.

Kombinierte Indexoptimierung Sortierreihenfolge nach

Darüber hinaus können Sie die Verwendung eines gemeinsamen Indexes in Betracht ziehen, um die Sortierung auf MySQL-Serverebene zu reduzieren. Beispielsweise enthält die Benutzerbestelltabelle einen gemeinsamen Index (user_id, buy_date) und einen einspaltigen Index (user_id): (Beachten Sie, dass dies nur zur Demonstration des gemeinsamen Indexes dient. In tatsächlichen Projekten wird nur ein gemeinsamer Index benötigt. Wie oben erwähnt, entspricht (a,b) zwei Indizes a und (a,b)):

SCHLÜSSEL `idx_user_id` (`Benutzer-ID`),
SCHLÜSSEL `idx_user_id_buy_date` (`Benutzer-ID`,`Kaufdatum`)

Wenn Sie nur die Bestellungen eines Benutzers abfragen, verwendet InnoDB den user_id-Index wie folgt:

mysql> erläutern Sie „select user_id, order_id from t_order where user_id = 1;“
+----+----------+---------+------------+------+----------------------------------+-------------+---------+-----------+-------+----------+-------------+
| ID | Auswahltyp | Tabelle | Partitionen | Typ | mögliche Schlüssel | Schlüssel | Schlüssellänge | Ref. | Zeilen | gefiltert | Extra |
+----+----------+---------+------------+------+----------------------------------+-------------+---------+-----------+-------+----------+-------------+
| 1 | SIMPLE | t_order | NULL | ref | idx_user_id,idx_user_id_buy_date | idx_user_id | 4 | const | 4 | 100,00 | Index wird verwendet |
+----+----------+---------+------------+------+----------------------------------+-------------+---------+-----------+-------+----------+-------------+
1 Zeile im Satz, 1 Warnung (0,00 Sek.)

Wenn Sie jedoch nach dem Kaufdatum buy_date sortieren und die Kaufdatensätze des Benutzers in den letzten drei Tagen abrufen müssen, können sowohl der einspaltige Index user_id als auch der gemeinsame Index (user_id, buy_date) verwendet werden. InnoDB wird den gemeinsamen Index verwenden, da buy_date bereits im gemeinsamen Index sortiert ist. Daher muss auf MySQL-Serverebene nicht erneut sortiert werden, wodurch die Leistung wie folgt verbessert wird:

mysql> erläutern Sie „select user_id, order_id from t_order“, wobei user_id = 1, Bestellung nach Kaufdatumslimit 3;
+----+----------+---------+------------+------+----------------------------------+----------------------+----------+----------+----------+----------+----------+--------------+
| ID | Auswahltyp | Tabelle | Partitionen | Typ | mögliche Schlüssel | Schlüssel | Schlüssellänge | Ref. | Zeilen | gefiltert | Extra |
+----+----------+---------+------------+------+----------------------------------+----------------------+----------+----------+----------+----------+----------+--------------+
| 1 | SIMPLE | t_order | NULL | ref | idx_user_id,idx_user_id_buy_date | idx_user_id_buy_date | 4 | const | 4 | 100,00 | Mit where; Mit index |
+----+----------+---------+------------+------+----------------------------------+----------------------+----------+----------+----------+----------+----------+--------------+
1 Zeile im Satz, 1 Warnung (0,01 Sek.)

Wenn der gemeinsame Index idx_user_id_buy_date gelöscht wird, wird Using filesort angezeigt:

mysql> Tabelle ändern, t_order, Index idx_user_id_buy_date löschen;
Abfrage OK, 0 Zeilen betroffen (0,02 Sek.)
Datensätze: 0 Duplikate: 0 Warnungen: 0

mysql> erläutern Sie „select user_id, order_id from t_order“, wobei user_id = 1, Bestellung nach Kaufdatumslimit 3;
+----+----------+---------+------------+------+---------------+-----+---------+------+---------+------+----------+----------+-------------+-------------+
| ID | Auswahltyp | Tabelle | Partitionen | Typ | mögliche Schlüssel | Schlüssel | Schlüssellänge | Ref. | Zeilen | gefiltert | Extra |
+----+----------+---------+------------+------+---------------+-----+---------+------+---------+------+----------+----------+-------------+-------------+
| 1 | SIMPLE | t_order | NULL | ALL | idx_user_id | NULL | NULL | NULL | 4 | 100,00 | Where verwenden; Filesort verwenden |
+----+----------+---------+------------+------+---------------+-----+---------+------+---------+------+----------+----------+-------------+-------------+
1 Zeile im Satz, 1 Warnung (0,00 Sek.)

Oben finden Sie eine ausführliche Erklärung und Integration der vom Herausgeber eingeführten Implementierung des Innodb-Speicher-Engine-Index. Ich hoffe, es wird allen helfen. Wenn Sie Fragen haben, hinterlassen Sie mir bitte eine Nachricht und der Herausgeber wird Ihnen rechtzeitig antworten. Ich möchte auch allen für ihre Unterstützung der Website 123WORDPRESS.COM danken!