Details zur zugrundeliegenden Datenstruktur von MySQL-Indizes

1. Indextyp

1. B+ Baum

Warum B+-Baum statt B-Baum?

Sehen wir uns zunächst die strukturellen Unterschiede zwischen B-Baum und B+-Baum an.

B-Baum-Struktur:

B+ Baum:

Sie können sehen:

• Der B-Baum verfügt auf jedem Knoten über Satellitendaten (eine Datenzeile in der Datentabelle), während der B+-Baum nur auf den Blattknoten Satellitendaten aufweist. Dies bedeutet, dass der B+-Baum bei gleich großen Festplattensektoren mehr Blattknoten speichern kann und weniger Festplatten-E/A-Zeiten benötigt; außerdem bedeutet es, dass die Suchleistung des B+-Baums stabiler ist und die schnellste Zeitkomplexität der B-Baum-Datenabfrage O(1) beträgt.
• Jeder Knoten eines B-Baums kommt nur einmal vor, und alle Knoten eines B+-Baums erscheinen in Blattknoten. Alle Blattknoten des B + -Baums bilden eine aufsteigende verknüpfte Liste, die für die Intervallbereichssuche geeignet ist, während der B-Baum nicht geeignet ist.
  

2. Was sind die Unterschiede zwischen den B+-Baumindeximplementierungen von MyISAM und InnoDB (Clusterindex und Nicht-Clusterindex)?

Zuerst müssen Sie gruppierte und nicht gruppierte Indizes verstehen.

Gruppierter Index:

In einem gruppierten Index enthalten die Blattseiten alle Daten für die Zeile und die Knotenseiten die Indexspalten. InnoDB clustert Daten nach Primärschlüssel. Wenn kein Primärschlüssel definiert ist, wird stattdessen eine eindeutige, nicht leere Indexspalte ausgewählt. Wenn kein solcher Index vorhanden ist, definiert InnoDB implizit einen Primärschlüssel als Clusterindex.

Datenverteilung des Clustered-Index:

In einem Clustered-Index gibt es neben dem Primärschlüsselindex auch einen Sekundärindex. Die Blattknoten im sekundären Index speichern keine „Zeilenzeiger“, sondern Primärschlüsselwerte, die als „Zeiger“ auf die Zeilen verwendet werden. Dies bedeutet, dass die Speicher-Engine beim Suchen nach einer Zeile über einen Sekundärindex den Blattknoten des Sekundärindex finden muss, um den entsprechenden Primärschlüsselwert zu erhalten, und dann basierend auf diesem Wert nach der entsprechenden Zeile im Clustered-Index suchen muss, was auch als "zurück zur Tabelle" bezeichnet wird. Natürlich können Sie Tabellenwiederholungen vermeiden, indem Sie abdeckende Indizes oder adaptive Indizes von InnoDB verwenden, um solche sich wiederholenden Arbeiten zu reduzieren.

Hinweis : Jeder Blattknoten in einem gruppierten Index enthält nicht nur die vollständige Datenzeile, sondern auch die Transaktions-ID, den Rollback-Zeiger für Transaktionen und MVCC.

3. Nicht gruppierter Index

Der Primärschlüsselindex und der Sekundärindex eines nicht gruppierten Indexes unterscheiden sich in ihrer Struktur nicht; beide speichern „Zeilenzeiger“, die auf die physische Adresse der Daten auf den Blattknoten zeigen.

Primärschlüsselindex und Sekundärindex des gruppierten Indexes:

Primärschlüsselindex und Sekundärindex des nicht gruppierten Indexes:

4. Vor- und Nachteile des Clustered-Index

Vorteil:

Speichern Sie zusammengehörige Daten zusammen (gruppieren Sie beispielsweise alle E-Mails des Benutzers nach Benutzer-ID), da sonst jeder Datenlesevorgang zu einem Festplatten-E/A führen kann.
Schnellerer Datenzugriff. Speichern Sie Indizes und Daten im selben B+-Baum. Normalerweise ist es schneller, Daten aus einem gruppierten Index abzurufen als aus einem nicht gruppierten Index. Mithilfe einer überdeckenden Abfrage können Sie den Primärschlüsselwert direkt im Seitenknoten verwenden.

Mangel:

Wenn alle Daten im Speicher abgelegt werden können, ist ein sequentieller Zugriff nicht mehr erforderlich und gruppierte Indizes haben keinen Vorteil. Die Einfügegeschwindigkeit hängt von der Einfügereihenfolge ab. Zufälliges Einfügen kann zu Seitenaufteilungen und Löchern führen. Verwenden Sie OPTIMIZE TABLE, um die Tabelle neu zu erstellen. Jedes Einfügen, Aktualisieren und Löschen erfordert die Wartung von Indexänderungen, was sehr teuer ist. Sekundärindizes können größer als erwartet sein, da die Primärschlüsselspalten der referenzierten Zeilen im Knoten enthalten sind.

5. Hash-Index

Hash-Indizes werden auf Basis von Hash-Tabellen implementiert. Nur Abfragen, die mit allen Spalten des Indexes exakt übereinstimmen, sind gültig. Das bedeutet, dass Hash-Indizes für Abfragen mit gleichen Werten geeignet sind.

Konkrete Implementierung: Für jede Datenzeile berechnet die Speicher-Engine einen Hash-Code für alle Indexspalten. Der Hash-Index speichert alle Hash-Codes im Index und speichert einen Zeiger auf jede Datenzeile in der Hash-Tabelle.

In MySQL unterstützt nur die Memory Engine explizit Hash-Indizes, obwohl Memory Engine auch B-Baum-Indizes unterstützt.

Hinweis: Die Speicher-Engine unterstützt nicht eindeutige Hash-Indizes. Konflikte lassen sich lösen, indem mehrere Datensatzzeiger mit demselben Hash-Wert in Form einer verknüpften Liste gespeichert werden.

6. Adaptiver Hash-Index

Wenn InnoDB feststellt, dass bestimmte Indexwerte sehr häufig verwendet werden, erstellt es einen Hash-Index basierend auf dem B + -Baumindex im Speicher, sodass der B + -Baumindex auch einige Vorteile des Hash-Index bietet, z. B. die schnelle Hash-Suche.

Dies ist das Ende dieses Artikels über die Details der zugrunde liegenden Datenstruktur von MySQL-Indizes. Weitere Informationen zur zugrunde liegenden Datenstruktur von MySQL-Indizes 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!