Detaillierte Analyse der MySQL-Indexdatenstruktur

Überblick

Ein Index ist eine Struktur, die die Werte einer oder mehrerer Spalten einer Datenbanktabelle sortiert. Über einen Index kann schnell auf bestimmte Informationen in einer Datenbanktabelle zugegriffen werden.

Indexdatenstruktur

Binärer Baum

Ein binärer Baum ist ein geordneter Baum, bei dem der Grad der Knoten im Baum nicht höher als 2 ist. Es handelt sich um den einfachsten und wichtigsten Baum. Die rekursive Definition eines Binärbaums lautet: Ein Binärbaum ist ein leerer Baum oder ein nicht leerer Baum, der aus einem Wurzelknoten und zwei sich nicht überschneidenden linken und rechten Teilbäumen der Wurzel besteht; der linke und der rechte Teilbaum sind ebenfalls Binärbäume.

Für das Array {1,2,3,4,5} wird die Datenstruktur zu einer verknüpften Liste

Merkmale:

• Unter dem übergeordneten Knoten befinden sich zwei untergeordnete Knoten.
• Die Daten des rechten Knotens sind größer als die Daten des linken Knotens.
  

Binärer Baum.png

Rot-Schwarzer Baum

Ein Rot-Schwarz-Baum ist ein spezieller Typ eines Binärbaums, einer Struktur, die in der Informatik zum Organisieren von Datenblöcken, beispielsweise Zahlen, verwendet wird. Wenn ein binärer Suchbaum ein Rot-Schwarz-Baum ist, muss jeder seiner Teilbäume ein Rot-Schwarz-Baum sein.

Der Rot-Schwarz-Baum ist eine Variante eines ausgeglichenen binären Suchbaums. Der Höhenunterschied zwischen seinen linken und rechten Teilbäumen kann größer als 1 sein, sodass der Rot-Schwarz-Baum kein streng ausgeglichener binärer Baum (AVL) ist, aber die Kosten für seinen Ausgleich sind gering und seine durchschnittliche statistische Leistung ist besser als die des AVL.

Da jeder Rot-Schwarz-Baum ein binär sortierter Baum ist, kann bei der Suche nach einem Rot-Schwarz-Baum der Suchalgorithmus verwendet werden, der auf einen gewöhnlichen binär sortierten Baum angewendet wird. Farbinformationen werden während des Suchvorgangs nicht benötigt.

Die Datenstruktur des Rot-Schwarz-Baums ist wie folgt:

Rot-Schwarz-Baum-Datenstruktur.png

Merkmale:

• Ein Rot-Schwarz-Baum ist ein binärer Suchbaum, in dem jeder Knoten ein Farbattribut hat, entweder Rot oder Schwarz.
• Die Knoten sind rot oder schwarz.
• Der Wurzelknoten ist schwarz.
• Alle Blätter sind schwarz. (Blätter sind NIL-Knoten)
• Jeder rote Knoten hat zwei schwarze untergeordnete Knoten. (Auf keinem Pfad von jedem Blatt zur Wurzel können zwei aufeinanderfolgende rote Knoten vorhanden sein.)
• Alle Pfade von jedem Knoten zu jedem Blatt enthalten die gleiche Anzahl schwarzer Knoten.
• Diese Einschränkungen erzwingen eine Schlüsseleigenschaft von Rot-Schwarz-Bäumen: Der längstmögliche Pfad von der Wurzel zu einem Blatt ist nicht doppelt so lang wie der kürzestmögliche Pfad. Das Ergebnis ist ein ungefähr ausgeglichener Baum. Da Vorgänge wie das Einfügen, Löschen und Suchen eines Werts im schlimmsten Fall eine Zeit benötigen, die proportional zur Höhe des Baums ist, ermöglicht diese theoretische Obergrenze der Höhe, dass Rot-Schwarz-Bäume im schlimmsten Fall effizient sind, im Gegensatz zu gewöhnlichen binären Suchbäumen.
• Eigenschaft 4 stellt dieses Ergebnis sicher, da auf dem Pfad keine zwei aufeinanderfolgenden roten Knoten vorhanden sein können. Der kürzeste mögliche Pfad besteht ausschließlich aus schwarzen Knoten, und der längstmögliche Pfad besteht aus abwechselnd roten und schwarzen Knoten. Da gemäß Eigenschaft 5 alle längsten Pfade die gleiche Anzahl schwarzer Knoten haben, zeigt dies, dass kein Pfad mehr als doppelt so lang sein kann wie ein anderer Pfad.
• Da es sich beim Rot-Schwarz-Baum um einen spezialisierten binären Suchbaum handelt, sind die schreibgeschützten Operationen beim Rot-Schwarz-Baum dieselben wie beim normalen binären Suchbaum.

B-Baum

• Blattknoten haben die gleiche Tiefe und der Blattknotenzeiger ist leer
• Alle Elemente sind einzigartig
• Die Datenindizes in den Knoten sind aufsteigend von links nach rechts angeordnet.
  

B-Baum-Datenstruktur.png

B+Baum

• Nicht-Blattknoten speichern keine Daten, sondern nur Indizes (Redundanz) und können mehr Indizes speichern
• Blattknoten enthalten alle Indexfelder
• Blattknoten werden mit Zeigern verknüpft, um die Leistung des Intervallzugriffs zu verbessern (was die Effizienz der Bereichssuche verbessern kann).
  

B+ Baumdatenstruktur.png

Schlüsselwörter: Reihenfolge innerhalb von Knoten, Blattknotenzeigerlinks, Nicht-Blattknoten-Speicherindex (redundant)

Abfrage der Größe der Datenseite des MySQL-Index:

mysql> globalen Status wie „Innodb_page_size“ anzeigen;
+------------------+--------+
| Variablenname | Wert |
+------------------+--------+
| Innodb_Seitengröße | 16384 |
+------------------+--------+

Warum 16kb einstellen?

Hash

• Durch eine Hash-Berechnung des Indexschlüssels kann der Standort des Datenspeichers ermittelt werden.
• Hash-Indizes sind häufig effizienter als B+-Baum-Indizes.
• Es wird nur „=“ unterstützt. „in“ unterstützt keine Bereichsabfragen.
• Es liegt ein Hash-Konfliktproblem vor
  

Hash-Datenstruktur.png

Index

InnoDB-Indeximplementierung (Clustering)

Die Tabellendatendatei selbst ist eine Indexstrukturdatei, die von B+Tree organisiert wird

Clustered Index - Blattknoten enthalten vollständige Datensätze

Warum muss eine InnoDb-Tabelle einen Primärschlüssel haben, und wird die Verwendung eines ganzzahligen, automatisch inkrementierenden Primärschlüssels empfohlen?

• Wenn kein Index festgelegt ist, wählt MySQL eine Spalte mit eindeutigen Daten als Primärschlüsselindex aus, wenn keine solche Spalte gefunden wird. Ich würde eine ausgeblendete Spalte wie „rowid“ erstellen.
• Die Tabellendatendatei wird gemäß der B+Tree-Datenstruktur verwaltet und der Blattknoten verwaltet die Daten der Zeile. Es muss also einen Primärschlüssel geben.
• Ganzzahlen sind für die B+Tree-Sortierung praktischer. Wenn sie selbsterhöhend sind, kann die Datenstruktur schneller und sequentiell gespeichert werden, ohne dass eine große Anzahl von Baumausgleichsoperationen erforderlich ist.
  

Warum speichern Blattknoten von Nicht-Primärschlüssel-Indexstrukturen Primärschlüsselwerte?

• Konsistenz: Lassen Sie zuerst den Primärschlüsselindex erfolgreich sein und aktualisieren Sie dann die Nicht-Primärschlüsselindexbeziehung
• Sparen Sie Speicherplatz.
  

Primärschlüsselindex-Diagramm:

InnoDB-Indeximplementierung.png

Nicht-Primärschlüssel-Indexdiagrammbild

Wenn die Abfrage auf Name = Alice basiert:

1. Verwenden Sie den Nicht-Primärschlüsselindex zum Abfragen und Abrufen der Informationen (Alice, 18) nach der Abfrage. Tatsächlich ist dies auch ein nicht gruppierter Index
2. Führen Sie anschließend eine Back-Table-Abfrage durch und fragen Sie die Tabelle mit dem Primärschlüssel erneut ab.
   

Zwei Datendateien:

.frm speichert hauptsächlich Informationen zur Tabellenstruktur

.ibd speichert hauptsächlich Indizes und Daten

MyISAM-Indexdateien (nicht gruppiert)

Indexdateien und Datendateien sind getrennt (nicht gruppiert)

MyISAM-Speicher-Engine index.png

Drei Datendateien:

.frm-Datenstrukturdatei

.myd-Dateien werden hauptsächlich zum Speichern von Daten verwendet

.myi-Dateien speichern hauptsächlich Indexinformationen

Gruppierte und nicht gruppierte Indizes

Besonderheit:

Clustering/Nicht-Clustering bezieht sich hauptsächlich darauf, ob die Indexdatei zusammen mit der Datendatei vorliegt.

Im Hinblick auf die Abfrageeffizienz führen Cluster-Indizes keine dateiübergreifenden Abfragen durch, was schneller ist.

Gemeinsame/zusammengesetzte Indizes

Mehrere Felder werden in einem gemeinsamen Index organisiert

Kombinierter Index.png

Warum wird das Prinzip des ganz linken Präfixes auf diese Weise verwendet?

Die indizierten Daten sind sortiert und können nicht verwendet werden, wenn Felder übersprungen werden.

Beispiel:

wobei Name = 'Jeff' und Alter = 22 -- trifft den Index wobei Alter = 30 und Postatin = 'Manager' -- trifft den Index nicht wobei Postation = 'dev' -- trifft den Index nicht

Verweise

Baidu-Enzyklopädie

Zusammenfassen

Dies ist das Ende dieses Artikels über die MySQL-Indexdatenstruktur. Weitere relevante Inhalte zur MySQL-Indexdatenstruktur finden Sie in den vorherigen Artikeln von 123WORDPRESS.COM oder in den folgenden verwandten Artikeln. Ich hoffe, dass jeder 123WORDPRESS.COM in Zukunft unterstützen wird!