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 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:
MySQL ändert den Namen der Datentabelle
MySQL erstellt eine gespeicherte Prozedur
Der Unterschied zwischen Mongodb und MySQL
So überprüfen Sie, ob das MySQL-Passwort vergessen wurde
MySQL-Datenbank erstellen
Was ist ein Index?
MySQL-Standard-Transaktionsisolationsstufe
Der Unterschied zwischen SQL Server und MySQL
