MySQL-Index-Datenstruktur

1. Vorwort:

In unserem Leben exportieren wir Anwendungen, die den Indexeffekt sehen können, wie z. B. an Bahnhöfen angezeigte Zugfahrpläne, Wörterbuchverzeichnisse usw. Ihre Funktion ist die Funktion von Indizes. Sie filtern die endgültigen gewünschten Ergebnisse heraus, indem sie den Umfang der zu erhaltenden Daten kontinuierlich einschränken, und wandeln gleichzeitig zufällige Ereignisse in sequentielle Ereignisse um, dh wir verwenden zum Sperren immer dieselbe Suchmethode Daten (A-Z-Suche im Wörterbuch).

Lebensbeispiel – mit dem Zug fahren: Ich fahre mit dem Zug zurück in meine Heimatstadt. Wenn es keinen Zugfahrplan gibt, wenn ich den Zug nehmen möchte, ist das schlimmste Ergebnis, dass ich zu jedem Zug fahren muss Halten Sie an, um den Zug zu finden, den ich nehmen möchte. Mit dem Fahrplan kann ich schnell erkennen, wo der Zug, den ich nehmen möchte, hält, und ich kann direkt dorthin gehen, anstatt einzeln zu fahren, um zu sehen, ob der Zug, den ich nehmen möchte gehen zu, was meinen Besuch beschleunigt. Dieser Zugfahrplan ist der Index der Datenbank.

2. Disk-Prinzip:

Dieser Teil enthält viel Text und Theorie, und Sie können ihn lesen, wenn Sie ihn lesen Wenn Sie kein Interesse haben, denken Sie nur an eine Schlussfolgerung aus diesem Teil:

Lesen Sie Daten so oft wie möglich [Reduzieren Sie die Anzahl der E/A-Interaktionen mit Betriebssystem].

Okay, wenn Sie kein Interesse haben, können Sie es überspringen und mit dem nächsten Teil fortfahren.

Die Datenbankimplementierung ist relativ komplex. Um die Leistung zu verbessern, können wir jedes Mal einen Teil der Daten zur Berechnung in den Speicher einlesen Der Speicherzugriff auf die Festplatte ist etwa 100.000 Mal so groß, sodass ein einfacher Suchbaum schwierige Anwendungsszenarien erfüllen kann. Der Zugriff auf die Festplatte wurde bereits erwähnt. Hier finden Sie eine kurze Einführung in die Datenträger-E/A und das Vorlesen von Daten auf der Festplatte. Die Zeit, die beim Lesen von Daten aufgewendet wird, kann in drei Kategorien unterteilt werden: Suchzeit und Rotationsverzögerung und Übertragungszeit.
a)·Suchzeit: die Zeit, die der Magnetarm benötigt, um sich auf die angegebene Spur zu bewegen, bei herkömmlichen Festplatten liegt sie im Allgemeinen unter 5 ms. b) Rotationsverzögerung: Dies ist die Geschwindigkeit der Festplatte, die wir oft hören B. eine Festplatte mit 7200 U/min. Dies bedeutet, dass sie sich 7200 Mal pro Minute drehen kann, was bedeutet, dass sie sich 120 Mal pro Sekunde drehen kann und die Rotationsverzögerung 1/120/2 = 4,17 ms beträgt. c). Das Lesen von der Festplatte oder das Schreiben von Daten auf die Festplatte beträgt im Allgemeinen einige Zehntel Millisekunden, was im Vergleich zu den ersten beiden Zeiten vernachlässigbar ist.
(Ich habe einen sehr ausführlichen Artikel gelesen: http://wdxtub.com/2016/04/16/thin-csapp-3/)

Dann ist die Zeit, die für den Zugriff auf eine Festplatte benötigt wird, eine Festplatte IO Die Zeit beträgt ungefähr 5 + 4,17 = 9 ms, was ziemlich gut klingt, aber Sie müssen wissen, dass eine 500-MIPS-Maschine (Millionen Anweisungen pro Sekunde) 500 Millionen Anweisungen pro Sekunde ausführen kann, da Anweisungen auf der Natur der Elektrizität beruhen Mit anderen Worten: In der Zeit, die für die Ausführung einer E/A benötigt wird, können 400.000 Anweisungen ausgeführt werden. Die Datenbank enthält oft Hunderttausende, Millionen oder sogar Zehnmillionen von Daten, was offensichtlich eine Katastrophe ist.

Fazit also: Reduzieren Sie die Anzahl der E/A-Interaktionen des Betriebssystems.

(Wir rufen die von IO jedes Mal gelesenen Daten auf einer Seite auf. Die spezifische Größe der Daten auf einer Seite hängt vom Betriebssystem ab, normalerweise 4 KB oder 8 KB, das heißt, wir lesen die Daten auf einer Seite. Wann Daten werden generiert, nur ein IO findet tatsächlich statt)

3. Was ist ein Index:

Während der Nutzung des Datenbanksystems ist die Datenabfrage die am häufigsten verwendete Datenoperation.

Der einfachste Abfragealgorithmus ist natürlich die lineare Suche. Er durchläuft die Tabelle und prüft dann zeilenweise, ob der Zeilenwert mit dem zu findenden Schlüsselwort übereinstimmt. Allerdings können Algorithmen mit einer Zeitkomplexität von O(n) auch bei kleinen Tabellen und leicht belasteten Datenbanken eine gute Leistung erzielen. Aber wenn die Datenmenge zunimmt, ist der Algorithmus mit einer Zeitkomplexität von O(n) offensichtlich schlecht und die Leistung sinkt schnell.

Glücklicherweise hat die Entwicklung der Informatik viele bessere Suchalgorithmen hervorgebracht, wie z. B. die binäre Suche und die binäre Suche. Baumsuche) usw. Wenn Sie eine kleine Analyse durchführen, werden Sie feststellen, dass jeder Suchalgorithmus nur auf eine bestimmte Datenstruktur angewendet werden kann. Beispielsweise erfordert die binäre Suche, dass die abgerufenen Daten geordnet sind, während die binäre Baumsuche nur auf binäre Suchbäume angewendet werden kann. Aber die Daten selbst Die Organisationsstruktur kann verschiedene Datenstrukturen nicht vollständig erfüllen (z. B. ist es theoretisch unmöglich, beide Spalten gleichzeitig in der richtigen Reihenfolge zu organisieren). Daher verwaltet das Datenbanksystem zusätzlich zu den Daten auch Datenstrukturen, die bestimmte Anforderungen erfüllen Suchalgorithmen verweisen in irgendeiner Weise auf Daten, sodass erweiterte Suchalgorithmen auf diesen Datenstrukturen implementiert werden können. Diese Datenstruktur ist ein Index.

4. MySQLs B-Tree-Index (technisch gesehen B+Tree)

Okay, hier kommt der Kern dieses Artikels!

In MySQL gibt es vier Haupttypen von Indizes, nämlich: B-Tree-Index, Hash-Index, Volltext-Index und R-Tree-Index. Wir analysieren hauptsächlich B-Tree-Indizes. (B: Balance bedeutet Balance, nicht Binärbaum)

1. Detaillierte Erläuterung der B+-Baum-Datenstruktur

Das Bild oben ist ein B + -Baum (unter der Innodb-Engine unterscheidet er sich von der B + -Struktur unter der Myisam-Engine. Um es klar auszudrücken: Es ist der Unterschied zwischen Clustered-Index und Nicht-Clustered-Index. Weitere Informationen , siehe:

Mysql-Clustered Index

Der hellblaue Block wird als Festplattenblock bezeichnet. Sie können sehen, dass jeder Festplattenblock mehrere Datenelemente enthält (dargestellt in Dunkelblau, Bereich: [( M/2)-1, M-1] M sind die Gesamtdaten und Zeiger (dargestellt in Gelb). Plattenblock 1 enthält beispielsweise die Datenelemente 17 und 35, einschließlich der Zeiger P1, P2 und P3 Blöcke kleiner als 17. P2 stellt Plattenblöcke zwischen 17 und 35 dar, und P3 stellt Plattenblöcke größer als 35 dar. Die realen Daten liegen in Blattknoten vor, nämlich 3, 5, 9, 10, 13, 15, 28, 29, 36, 60, 75, 79, 90, 99. Nicht-Blattknoten speichern keine echten Daten (Merkmale von B+), sondern nur Datenelemente, die die Suchrichtung bestimmen. Beispielsweise sind 17 und 35 tatsächlich nicht in der Datentabelle vorhanden. 🎜>

2. Der Suchvorgang des B+-Baums

Wenn Sie wie in der Abbildung gezeigt das Datenelement 29 finden möchten, wird Festplattenblock 1 von der Festplatte in den Speicher geladen Erstens, und dies geschieht einmal IO, verwenden Sie die binäre Suche im Speicher, um 29 zwischen 17 und 35 zu ermitteln, sperren Sie den P2-Zeiger von Plattenblock 1, die Speicherzeit ist vernachlässigbar, da sie sehr kurz ist (im Vergleich zum IO der Festplatte), Übergeben Sie den P2-Zeiger von Plattenblock 1 an die Festplatte. Die Adresse lädt Plattenblock 3 in den Speicher. Der zweite E/A-Wert liegt zwischen 26 und 30. Der P2-Zeiger von Plattenblock 3 wird gesperrt Der Speicher durch den Zeiger tritt gleichzeitig auf. Führen Sie eine binäre Suche durch, um 29 zu finden, und führen Sie insgesamt drei E/As aus -layer b+ tree kann Millionen von Daten darstellen, es sind nur drei IOs erforderlich. Wenn kein Index vorhanden ist, erfolgt ein IO für jedes Datenelement, also insgesamt Offensichtlich sind die Kosten sehr, sehr hoch (Frage???), wie oben erwähnt, ist der B+-Baum von INNOBD ein Clustered-Index-Typ und die realen Daten werden zusammen mit dem Indexblatt platziert Die Frage ist also: Wenn ich mehrere Indizes habe, ist es möglich, dass unter jedem Index Daten gespeichert werden? Wenn nicht, wird vermutlich ein Zeiger verwendet, um auf die Vergangenheit zu verweisen eine Datenstruktur? )

Antwort: Jede Tabelle kann nur einen Hilfsindex haben. Der Hilfsindex ist auch ein Sekundärindex zum Primärindex, in dem die Daten gespeichert sind

3.b+Baumeigenschaften

1). Angenommen, die Daten in der aktuellen Datentabelle sind N und die Anzahl der Datenelemente in jedem Plattenblock ist m, dann ist h = ㏒ (m + 1) N, wenn die Datenmenge N konstant ist. je größer m ist, desto kleiner ist h, während m = Die Größe des Festplattenblocks/die Größe des Datenelements. Die Größe des Festplattenblocks ist die Größe einer Datenseite. Wenn der vom Datenelement belegte Speicherplatz kleiner ist, beträgt die Anzahl der Datenelemente mehr und die Höhe h des Baumes ist geringer. Es gibt auch weniger I/O. Aus diesem Grund muss jedes Datenelement, also das Indexfeld, so klein wie möglich sein.

Als negatives Beispiel belegt int 4 Bytes, was halb so viel ist wie bigint 8 Bytes. Aus diesem Grund erfordert der B+-Baum, dass reale Daten in Blattknoten statt in inneren Knoten platziert werden. Sobald sie in inneren Knoten platziert werden, werden die Datenelemente der Plattenblöcke erheblich sinken (siehe das Prinzip in Teil 2 oben), was dazu führt, dass der Baum Erhöhung der Höhe. Wenn das Datenelement gleich 1 ist, degeneriert es in eine lineare Tabelle. Wie folgt:

Wenn es sich um die Struktur auf der linken Seite handelt, beträgt die Anzahl der E/As das Dreifache; wenn es sich um die lineare Tabelle auf der rechten Seite handelt, beträgt die Anzahl I/Os beträgt 6 Mal. Es ist offensichtlich, dass die IO-Änderungen zwei Schlussfolgerungen zuordnen:

1 als Index muss klein sein;

2. Führen Sie eine Vereinigung durch. Bei der Indizierung sollte auch die Anzahl der gemeinsamen Felder geringer sein

2). Wenn es sich bei den Datenelementen des b+-Baums um zusammengesetzte Datenstrukturen (mehrspaltiger Index) handelt, z. B. (Name, Alter, Geschlecht), werden b+-Nummern verwendet, um den Suchbaum in der Reihenfolge von links nach zu erstellen Rechts.

Wenn beispielsweise Daten wie (Zhang San, 20, F) abgerufen werden, vergleicht der b+-Baum zuerst den Namen, um die nächste Suchrichtung zu bestimmen. Wenn die Namen gleich sind, werden Alter und Geschlecht ermittelt Nacheinander verglichen und schließlich Die abgerufenen Daten werden erhalten. Wenn jedoch Daten ohne Namen wie (20, F) eingehen, weiß der B + -Baum nicht, welcher Knoten als nächstes überprüft werden soll, da der Name beim Erstellen des Suchbaums der erste Vergleichsfaktor ist , und es muss „Suche nach Name zuerst“ erfolgen, um zu wissen, wo als Nächstes gesucht werden muss.

Zum Beispiel kann der b+-Baum beim Abrufen von Daten wie (Zhang San, F) den Namen verwenden, um die Suchrichtung anzugeben, aber das nächste Feldalter fehlt, sodass er nur die Daten abrufen kann, deren Name lautet gleich Zhang San. Finden Sie die Daten, deren Geschlecht F ist, und gleichen Sie sie ab. Dies ist eine sehr wichtige Eigenschaft, nämlich das am weitesten links liegende Übereinstimmungsmerkmal des Index.

bildet zwei Schlussfolgerungen ab:

1. Das am weitesten links stehende Matching-Merkmal wird von links nach rechts gelesen

2 Wenn es einen mehrspaltigen Index gibt, muss der Index von links nach rechts nicht erstellt werden (a, b, c), dann muss (a), (a, b) nicht erstellt werden

3. Weitere Schlussfolgerungen: Mysql-Index-Zusammenfassung http://blog.csdn.net/ty_hf/article/details/53526405

Das Obige ist der Inhalt der MySQL-Index-Datenstruktur. Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website (www .php.cn)!