Das Prinzip des MySQL-Index

MySQL-Datenbank unterstützt eine Vielzahl von Indizes, wie B-Tree-Indizes, Hash-Indizes, Volltext-Indizes usw. Dieser Artikel konzentriert sich auf B-Tree-Indizes. (Empfohlen: „MySQL-Tutorial“)

Indexprinzip und Essenz

Offizielle Erklärung von MySQL: Index sind Daten, die die Effizienz der Datenerfassung verbessern für MySQL. Struktur zur schnellen Abfrage von Daten. Indizes sind Datenstrukturen, die einem bestimmten Suchalgorithmus genügen. Diese Datenstrukturen verweisen auf bestimmte Weise auf Daten, um eine effiziente Datensuche zu erreichen.

B+-Baum

MySQL verwendet im Allgemeinen den B+-Baum als Indexstruktur. Was sind also die Merkmale des B+-Baums?

Wenn der Baumgrad n ist, beträgt die Obergrenze jedes Knotenzeigers 2n+1

Nicht-Blattknoten speichern keine Daten, nur Zeigerindizes speichern alle Daten, nicht Zeiger

Ein sequenzieller Zugriffszeiger wird basierend auf dem klassischen B+-Baum hinzugefügt. Jeder Blattknoten hat einen Zeiger auf den nächsten benachbarten Blattknoten, wie in der Abbildung gezeigt. Hauptsächlich zur Verbesserung der Leistung des Intervallzugriffs. Wenn Sie beispielsweise alle Daten mit den Schlüsseln 20 bis 50 finden möchten, müssen Sie gemäß der sequentiellen Zugriffsroute nur auf alle Datenknoten gleichzeitig zugreifen.

B+-Baumdiagramm mit sequentiellem Zugriff

Lokalitätsprinzip und Festplatten-Read-Ahead

Warum also Datenbank? Verwenden Systeme im Allgemeinen B+-Bäume als Indexstrukturen anstelle anderer Strukturen wie Rot-Schwarz-Bäume?

Lassen Sie uns zunächst das Prinzip der Lokalität und das Konzept des Festplatten-Vorauslesens vorstellen.

Im Allgemeinen ist der Index selbst groß und wird nicht vollständig im Speicher gespeichert, sondern in Form einer Indexdatei auf der Festplatte. Daher finden während des Indexsuchvorgangs Festplatten-E/A-Vorgänge statt, und Festplatten-E/A ist im Vergleich zum Speicherzugriff sehr langsam. Daher sollte die Indexstruktur die Anzahl der Festplatten-E/A-Zugriffe minimieren.

Um die Festplatten-IO zu reduzieren, führt die Festplatte häufig ein Vorlesen der Daten durch, beginnend an einer bestimmten Position und liest eine bestimmte Datenlänge rückwärts in den Speicher, was das Prinzip der Lokalität darstellt. Da das sequentielle Lesen der Festplatte effizienter ist und keine Suchzeit erfordert, kann die E/A-Effizienz verbessert werden.

Die Read-Ahead-Länge ist im Allgemeinen ein ganzzahliges Vielfaches der Seite, und der Hauptspeicher und die Datenträgeraustauschdaten werden in Seiteneinheiten angegeben. Wenn sich die zu lesenden Daten nicht im Speicher befinden, wird ein Seitenfehler-Interrupt ausgelöst. Das System sendet eine Anforderung zum Lesen der Daten auf der Festplatte. Die Festplatte findet die Startposition der Daten und liest kontinuierlich eine oder mehrere mehrere Seiten mit Daten rückwärts und lädt sie in den Speicher. Dann kehrt der Interrupt zurück und das System läuft weiter. Beim Entwurf eines allgemeinen Datenbanksystems wird die Größe des B+-Baumknotens auf eine Seite festgelegt, sodass zum Laden jedes Knotens nur ein IO erforderlich ist.

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