Kurze Analyse des MySQL B-Tree-Index

B-Baum-Index

Verschiedene Speicher-Engines können auch unterschiedliche Speicherstrukturen verwenden. Beispielsweise verwendet die NDB-Cluster-Speicher-Engine intern eine T-Tree-Struktur zum Speichern dieses Indexes, obwohl ihr Name BTREE lautet; InnoDB verwendet einen B+Tree.

B-Tree speichert normalerweise alle Werte der Reihe nach und jede Blattseite hat den gleichen Abstand zur Wurzel. Das folgende Diagramm spiegelt grob die Funktionsweise von InnoDB-Indizes wider.

Warum verwendet MySQL für den Index einen B+-Baum statt eines B-Baums oder Rot-Schwarz-Baums?

Nach dem Lesen des obigen Artikels können Sie verstehen, warum der B-Tree-Index schnell auf Daten zugreifen kann. Da die Speicher-Engine keinen vollständigen Tabellenscan mehr durchführen muss, um die erforderlichen Daten zu erhalten, enthält der Blattknoten alle Elementinformationen und jeder Blattknotenzeiger zeigt auf den nächsten Knoten. Daher eignet er sich sehr gut zum Durchsuchen von Bereichsdaten.

Der Index ordnet mehrere Werte entsprechend der Reihenfolge an, in der sie in der CREATE TABLE-Anweisung definiert sind.

Die Indexsortierregel lautet dann Nachname, Vorname, Geburtsdatum.

Arten von Abfragen, die B-Tree-Indizes verwenden können
B-Tree-Indizes eignen sich für die Suche nach vollständigen Schlüsselwerten, Schlüsselwertbereichen oder Schlüsselpräfixen.
Die Schlüsselpräfixsuche wird nur für die Suche basierend auf dem äußersten linken Präfix verwendet.

Nehmen Sie ein Partikel:

CREATE TABLE Personen (
  Nachname VARCHAR ( 50 ) NICHT NULL,
  vorname VARCHAR ( 50 ) NICHT NULL,
  Geburtsdatum NICHT NULL,
  Geschlechtsaufzählung ('m', 'f') NICHT NULL,
SCHLÜSSEL (Nachname, Vorname, Geburtsdatum) 
);

Der Index dieser Tabelle lautet wie folgt:

Typ Ergebnis

Die Typergebniswerte vom besten bis zum schlechtesten sind:

System > const > eq_ref > ref > Volltext > ref_or_null > Index_Merge > eindeutige Unterabfrage > Index_Unterabfrage > Bereich > Index > ALLE

Generell muss darauf geachtet werden, dass die Abfrage mindestens die Bereichsebene, besser noch die Referenzebene erreicht, da es sonst zu Performanceproblemen kommen kann.

Possible_keys: von SQL verwendeter Index

Schlüssel: Zeigt den Schlüssel (Index), den MySQL tatsächlich verwenden wollte. Wenn kein Index ausgewählt ist, ist der Schlüssel NULL

(1) Vollständiger Wertabgleich. Vollständiger Wertabgleich bezieht sich auf den Abgleich aller Spalten im Index.

Beispielsweise kann der Index (Nachname, Vorname, Geburtsdatum) der obigen Tabelle „Personen“ verwendet werden, um Personen zu finden, deren Nachname = „Cuba Allen“, Vorname = „Chuang“ und Geburtsdatum = „01.01.1996“ ist. Dies bedeutet, dass alle Spalten im Index für den Abgleich verwendet werden, also ein vollständiger Werteabgleich erfolgt.

mysql> EXPLAIN select * from People where Nachname = 'aaa' und Vorname = 'bbb' und Geburtsdatum = '20.11.2020' \G;
*************************** 1. Reihe ***************************
     ID: 1
 select_type: EINFACH
    Tabelle: Personen
 Partitionen: NULL
    Typ: ref
mögliche Schlüssel: Nachname
     Schlüssel: Nachname <-----Sie können sehen, dass dieser Schlüssel der Index ist, den wir definiert haben. Schlüssellänge: 307
     Verweis: konstant, konstant, konstant
    Reihen: 1
  gefiltert: 100,00
    Extra: NULL
1 Zeile im Satz, 1 Warnung (0,00 Sek.)

FEHLER: 
Keine Abfrage angegeben

(2) Für die Übereinstimmung mit dem äußersten linken Präfix können Sie nur die erste Spalte des Index verwenden.

Beispielsweise kann es verwendet werden, um Personen zu finden, deren Nachname = "aaa", also Personen, deren Nachname Zeng ist. Hier wird nur die äußerste linke Spalte des Index zum Abgleichen verwendet, also zum Abgleichen des äußersten linken Präfixes.

mysql> EXPLAIN select * from People where Nachname = 'aaa' \G;
*************************** 1. Reihe ***************************
     ID: 1
 select_type: EINFACH
    Tabelle: Personen
 Partitionen: NULL
    Typ: ref
mögliche Schlüssel: Nachname
     Schlüssel: Nachname <----Verwendeter Index Schlüssellänge: 152
     Verweis: const
    Reihen: 3
  gefiltert: 100,00
    Extra: NULL
1 Zeile im Satz, 1 Warnung (0,00 Sek.)

FEHLER: 
Keine Abfrage angegeben

(3) Das Zuordnen eines Spaltenpräfixes kann nur mit dem Anfangsteil des Wertes einer Spalte übereinstimmen.

Beispielsweise kann es verwendet werden, um Personen zu finden, deren Nachname WIE „a%“ ist, d. h. um alle Personen zu finden, deren Nachname mit Z beginnt. Hier wird für die Übereinstimmung nur das Präfix der äußersten linken Spalte des Index verwendet, d. h. es wird mit dem Spaltenpräfix abgeglichen.

mysql> EXPLAIN select * from People where Nachname = "a%" \G;
*************************** 1. Reihe ***************************
     ID: 1
 select_type: EINFACH
    Tabelle: Personen
 Partitionen: NULL
    Typ: ref
mögliche Schlüssel: Nachname
     Schlüssel: Nachname <--- verwendeter Index Schlüssellänge: 152
     Verweis: const
    Reihen: 1
  gefiltert: 100,00
    Extra: NULL
1 Zeile im Satz, 1 Warnung (0,00 Sek.)

FEHLER: 
Keine Abfrage angegeben

(4) Um einen Bereichswert abzugleichen, können Sie nur die erste Spalte des Index verwenden, um nach Daten zu suchen, die in einen bestimmten Bereich fallen.

Beispielsweise kann es verwendet werden, um Personen zu finden, deren Nachname zwischen „aaa“ und „aaabbbccc“ liegt. Hier wird nur das Präfix der äußersten linken Spalte des Index für die Bereichsübereinstimmung verwendet, d. h. für die Übereinstimmung mit dem Bereichswert.

mysql> EXPLAIN select * from People where Nachname ZWISCHEN ‚aaa‘ und ‚aaabbbccc‘\G;
*************************** 1. Reihe ***************************
     ID: 1
 select_type: EINFACH
    Tabelle: Personen
 Partitionen: NULL
    Typ: Bereich
mögliche Schlüssel: Nachname
     Schlüssel: Nachname <--- verwendeter Index Schlüssellänge: 152
     Ref: NULL
    Reihen: 3
  gefiltert: 100,00
    Extra: Indexbedingung verwenden
1 Zeile im Satz, 1 Warnung (0,00 Sek.)

FEHLER: 
Keine Abfrage angegeben

(5) Eine genaue Übereinstimmung einer Spalte und eine Bereichsübereinstimmung einer anderen Spalte kann zu einer vollständigen Übereinstimmung der ersten Spalte und einer Bereichsübereinstimmung der zweiten Spalte führen.

Beispielsweise kann es verwendet werden, um Personen mit Nachname = "aaa" und Vorname wie "b%" zu finden, also um Personen zu finden, deren Nachname Zeng ist und deren Vorname mit C beginnt. Hier wird die äußerste linke Spalte des Index für die exakte Übereinstimmung und die zweite Spalte für die Bereichsübereinstimmung verwendet.

mysql> EXPLAIN select * from People where Nachname = 'aaa' und Vorname wie 'b%'\G;
*************************** 1. Reihe ***************************
     ID: 1
 select_type: EINFACH
    Tabelle: Personen
 Partitionen: NULL
    Typ: Bereich
mögliche Schlüssel: Nachname
     Schlüssel: Nachname <--- verwendeter Index Schlüssellänge: 304
     Ref: NULL
    Reihen: 1
  gefiltert: 100,00
    Extra: Indexbedingung verwenden
1 Zeile im Satz, 1 Warnung (0,00 Sek.)

FEHLER: 
Keine Abfrage angegeben

(6) Abfragen, die nur auf Indizes zugreifen: Abfragen müssen nur auf Indizes zugreifen, ohne auf Datenzeilen zuzugreifen.

Wählen Sie beispielsweise „Nachname, Vorname“ aus, wobei „Nachname='aaa'“ ist. Hier werden nur die im Index enthaltenen Spalten „Nachname“ und „Vorname“ abgefragt. Ein Lesen der Datenzeilen ist daher nicht erforderlich.

mysql> erklären Sie select Nachname, Vorname, Geburtsdatum aus Personen, wobei Nachname = 'aaa'
*************************** 1. Reihe ***************************
      ID: 1
 select_type: EINFACH
    Tabelle: Personen
  Partitionen: NULL
     Typ: ref
mögliche Schlüssel: Nachname
     Schlüssel: Nachname
   Schlüssellänge: 152
     Verweis: const
     Reihen: 1
   gefiltert: 100,00
    Extra: Index verwenden
1 Zeile im Satz, 1 Warnung (0,00 Sek.)

FEHLER: 
Keine Abfrage angegeben

Einschränkungen von B-Bäumen

(1) Die Suche kann nur beginnend in der äußersten linken Spalte des Index erfolgen.
Beispielsweise kann der Index in der Tabelle „Personen“ nicht verwendet werden, um Personen zu finden, deren Vorname „bbb“ ist, noch kann er verwendet werden, um Personen mit einem bestimmten Geburtstag zu finden, da keine dieser Spalten die Spalte ganz links ist.

(2) Nur das am weitesten links stehende Präfix der am weitesten links stehenden Spalte des Index kann abgeglichen werden.
Beispielsweise kann der Index in der Tabelle „Personen“ keine Personen finden, deren Nachname WIE „%b“ ist. Obwohl Nachname die Spalte ganz links in diesem Index ist, kann der MySQL-Index keine Datensätze finden, deren Nachname mit „b“ endet.

(3) Der Abgleich kann nur von links nach rechts in der durch den Index festgelegten Reihenfolge durchgeführt werden, und Spalten im Index können nicht übersprungen werden.
Beispielsweise kann der Index in der Tabelle „Personen“ nicht verwendet werden, um nach Personen mit Nachname='a' UND Name='1996-01-01' zu suchen, da MySQL keine Spalte im Index überspringen und die äußerste linke Spalte und die letzte Spalte im Index zur Kombination verwenden kann. Wenn Sie die mittlere Spalte im Index nicht angeben, kann MySQL nur die äußerste linke Spalte des Index verwenden, also die erste Spalte.

(4) Wenn eine Abfrage eine Bereichsabfrage für eine Spalte enthält, können alle Spalten rechts davon nicht mittels Indexoptimierung gefunden werden.
Beispielsweise gibt es eine Abfrage wie diese: where last_name='a' AND first_name LIKE 'b%' AND dob='1996-01-01'; Diese Abfrage kann nur die ersten beiden Spalten des Index verwenden, da LIKE hier eine Bereichsbedingung ist und die Indexspalten nach first_name ungültig wären. (Optimierungspunkt: Vermeiden Sie in der Indexspalte möglichst die Verwendung von Bereichsbedingungen wie LIKE. Verwenden Sie stattdessen mehrere gleiche Bedingungen, um sicherzustellen, dass die nachfolgenden Indexspalten wirksam werden können.)

Oben finden Sie eine kurze Analyse der Details des MysQL B-Tree-Index. Weitere Informationen zum MysQL B-Tree-Index finden Sie in den anderen verwandten Artikeln auf 123WORDPRESS.COM!