Was ist die Datenstruktur des MySQL-Index?

1. Einführung

Die Datenstruktur des MySQL-Index ist ein Baum, und die häufig verwendete Speicher-Engine innodb verwendet B+Tree. Hier finden Sie eine kurze Einführung in B+Tree und die zugehörigen

Suchbäume.

2. Verschiedene Suchbäume

1. Binärer Sortierbaum (auch binärer Suchbaum genannt)

Binärer Sortierbaum ist der einfachste Suchbaum.

a) Es ist ein Binärbaum

b) Der Wert aller Knoten des linken Teilbaums ist kleiner als der seines übergeordneten Knotens Der Wert aller Knoten im rechten Teilbaum ist größer als der Wert seines übergeordneten Knotens.

2. Ausgeglichener Binärbaum (auch bekannt als AVL-Baum)

Der ausgeglichene Binärbaum basiert auf dem binären Sortierbaum und begrenzt somit die Tiefe des Baums Reduzierung der Anzahl der Vergleiche,

Merkmale:

a) ist ein Binärbaum

b) der Wert aller Knoten im linken Teilbaum ist kleiner als der Wert seines übergeordneten Knotens ist der Wert aller Knoten des rechten Teilbaums größer als der Wert seines übergeordneten Knotens

c) Der Tiefenunterschied zwischen dem linken Teilbaum und dem rechten Teilbaum liegt innerhalb von -1, 0, 1, andernfalls ist der Teilbaum eine Rotationsanpassung.

3. B-Baum (B-Baum)

B-Baum ist ein mehrseitig ausgeglichener Suchbaum, der direkte untergeordnete Baum des übergeordneten Knotens Die Anzahl der Knoten ist nicht mehr auf 2 begrenzt.

kann m (benutzerdefiniert) angeben, sodass mehr Knoten gespeichert werden können, ohne die Tiefe des Baums stark zu erhöhen.

B-Tree wird häufig in Dateisystemen verwendet.

Eigenschaften:

a) Jeder Knoten des Baums hat höchstens m (benutzerdefinierte) untergeordnete Knoten;

b) Wenn der Wurzelknoten kein Blattknoten ist, dann Es gibt mindestens zwei untergeordnete Knoten.

c) Alle Nicht-Blattknoten außer dem Wurzelknoten, mindestens m/2, nehmen den gesamten untergeordneten Knoten an.

d) Übergeordneter Knoten Die Werte ​​aller Knoten im Unterbaum ganz links unten sind kleiner als der Mindestwert des übergeordneten Knotens,

die Werte aller Knoten im Unterbaum ganz rechts sind größer als der Maximalwert des übergeordneten Knotens,

und der Rest in der Mitte Die Werte aller Knoten im Teilbaum liegen zwischen den Werten auf beiden Seiten des übergeordneten Knotens des Zeigers

e) Alle Blattknoten liegen auf der gleichen Ebene;

Hinweis: Alle Knoten haben den Wert

B+Baum (B+Baum)

B+ Baum ist eine Variante Im Vergleich zum B-Baum umfasst der Wert des Blattknotens alle Werte und die Werte aller übergeordneten Knoten sind wiederholte Werte der Blattknoten Die Rolle der Indexsuche und alle Blattknoten bilden auch eine geordnete verknüpfte Liste.

Die Speicher-Engine in MySQL ist der Index von Innodb und die verwendete Datenstruktur ist der B+-Baum.

Funktionen:

a) Der übergeordnete Knoten mit m untergeordneten Knoten hat m Schlüsselwörter.

b) Alle Blattknoten enthalten alle Schlüsselwörter (Wert) und bilden eine geordnete Verknüpfung Liste von klein nach groß;

c) Alle Nicht-Blattknoten dienen als Indizes, und die Knoten enthalten nur den Maximalwert aller Knoten im Unterbaum;

d) Alle Blattknoten sind auf der gleichen Ebene;

Hinweis: Blattknoten enthalten alle Schlüsselwörter (Werte).

5. B*Tree (B*Tree)

B*-Baum ist eine Variante des B+-Baums und bietet Unterstützung für Nicht-Blätter Knoten derselben Ebene bilden ebenfalls eine verknüpfte Liste.

3. Zusammenfassung

Zusammenfassend lässt sich sagen, dass die oben genannten Suchbäume miteinander in Zusammenhang stehen.

Es kommt auf den Innodb-Index in MySQL an. Er verwendet einen B+-Baum, beispielsweise einen Clustered-Index, der Daten über Primärschlüssel aggregiert und den B+-Baum verwendet, um sie zu implementieren.

Dies ist ein Index und auch Eine Datenspeicherstruktur von MySQL. Blattknoten enthalten alle Daten, und Nicht-Blattknoten dienen nur als Indizes (wenn

keinen Primärschlüssel definiert, definiert innodb implizit einen Primärschlüssel als Clustered-Index ).

Weitere technische Artikel zu MySQL finden Sie in der Spalte

MySQL-Tutorial.

Das obige ist der detaillierte Inhalt vonWas ist die Datenstruktur des MySQL-Index?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!