Wie funktionieren die MySQL-Indizes?

Question

Ich bin wirklich daran interessiert, wie MySQL-Indizes funktionieren, genauer gesagt, wie können sie die angeforderten Daten zurückgeben, ohne die gesamte Tabelle zu scannen?

Ich weiß, dass das nicht zum Thema gehört, aber wenn es jemanden gibt, der mir das im Detail erklären kann, wäre ich sehr, sehr dankbar.

Answer 1

Im Grunde funktioniert ein Index in einer Tabelle wie ein Index in einem Buch (daher der Name):

Nehmen wir an, Sie haben ein Buch über Datenbanken und möchten Informationen über, sagen wir, die Speicherung finden. Ohne Index (und ohne andere Hilfsmittel wie z. B. ein Inhaltsverzeichnis) müssten Sie eine Seite nach der anderen durchblättern, bis Sie das Thema gefunden haben (das ist ein full table scan ). Andererseits enthält ein Index eine Liste von Schlüsselwörtern, so dass Sie den Index konsultieren und sehen, dass storage wird auf den Seiten 113-120, 231 und 354 erwähnt. Dann könnten Sie direkt zu diesen Seiten blättern, ohne zu suchen (das ist eine Suche mit einem Index, etwas schneller).

Wie nützlich der Index sein wird, hängt natürlich von vielen Dingen ab - ein paar Beispiele, um das obige Gleichnis zu verwenden:

• Wenn Sie ein Buch über Datenbanken hätten und das Wort "Datenbank" auf dem Index hätten, würden Sie sehen, dass es auf den Seiten 1-59, 61-290 und 292 bis 400 erwähnt wird. In einem solchen Fall ist der Index keine große Hilfe, und es ist vielleicht schneller, die Seiten einzeln durchzugehen (bei einer Datenbank ist das "schlechte Selektivität").
• Bei einem 10-seitigen Buch macht es keinen Sinn, einen Index zu erstellen, da Sie am Ende ein 10-seitiges Buch haben, dem ein 5-seitiger Index vorangestellt ist, was einfach nur albern ist - scannen Sie einfach die 10 Seiten und fertig.
• Der Index muss auch nützlich sein - es macht im Allgemeinen keinen Sinn, z. B. die Häufigkeit des Buchstabens "L" pro Seite zu indexieren.

Answer 2

Das erste, was Sie wissen müssen, ist, dass Indizes eine Möglichkeit sind, das Durchsuchen der gesamten Tabelle zu vermeiden, um das gewünschte Ergebnis zu erhalten.

Es gibt verschiedene Arten von Indizes, die in der Speicherebene implementiert werden, so dass es keinen Standard zwischen ihnen gibt, und sie hängen auch von der verwendeten Speichermaschine ab.

InnoDB und der B+Tree-Index

Bei InnoDB ist der gängigste Indextyp der B+Tree-basierte Index, der die Elemente in einer sortierten Reihenfolge speichert. Außerdem müssen Sie nicht auf die eigentliche Tabelle zugreifen, um die indizierten Werte zu erhalten, wodurch Ihre Abfrage viel schneller zurückkehrt.

Das "Problem" bei diesem Indextyp ist, dass Sie den Wert ganz links abfragen müssen, um den Index zu verwenden. Wenn Ihr Index also zwei Spalten hat, z. B. nachname_name und vorname_name, ist die Reihenfolge, in der Sie diese Felder abfragen ist sehr wichtig .

Die folgende Tabelle zeigt:

CREATE TABLE person (
    last_name VARCHAR(50) NOT NULL,
    first_name VARCHAR(50) NOT NULL,
    INDEX (last_name, first_name)
);

Diese Abfrage würde den Index ausnutzen:

SELECT last_name, first_name FROM person
WHERE last_name = "John" AND first_name LIKE "J%"

Aber die folgende würde nicht

SELECT last_name, first_name FROM person WHERE first_name = "Constantine"

Denn Sie fragen die first_name Spalte an erster Stelle steht und nicht die Spalte ganz links im Index ist.

Dieses letzte Beispiel ist noch schlimmer:

SELECT last_name, first_name FROM person WHERE first_name LIKE "%Constantine"

Denn jetzt vergleichen Sie den ganz rechten Teil des ganz rechten Feldes im Index.

Der Hash-Index

Dies ist ein anderer Indextyp, den leider nur das Speicher-Backend unterstützt. Er ist blitzschnell, aber nur für vollständige Lookups nützlich, was bedeutet, dass Sie ihn nicht für Operationen wie > , < o LIKE .

Da es nur für das Speicher-Backend funktioniert, werden Sie es wahrscheinlich nicht sehr oft verwenden. Der wichtigste Fall, der mir gerade einfällt, ist der, dass Sie eine temporäre Tabelle im Speicher mit einer Reihe von Ergebnissen aus einem anderen Select erstellen und eine Menge anderer Selects in dieser temporären Tabelle unter Verwendung von Hash-Indizes durchführen.

Wenn Sie eine große VARCHAR Feld können Sie die Verwendung eines Hash-Index "emulieren", wenn Sie einen B-Baum verwenden, indem Sie eine weitere Spalte erstellen und einen Hash des großen Wertes darin speichern. Nehmen wir an, Sie speichern eine URL in einem Feld und die Werte sind ziemlich groß. Sie könnten auch ein Integer-Feld namens url_hash und verwenden Sie eine Hash-Funktion wie CRC32 oder eine andere Hash-Funktion, um die Url beim Einfügen zu hashen. Wenn Sie dann diesen Wert abfragen müssen, können Sie etwas wie folgt tun:

SELECT url FROM url_table WHERE url_hash=CRC32("http://gnu.org");

Das Problem bei dem obigen Beispiel ist, dass die CRC32 Funktion einen recht kleinen Hash erzeugt, kommt es zu vielen Kollisionen in den gehashten Werten. Wenn Sie genaue Werte benötigen, können Sie dieses Problem wie folgt lösen:

SELECT url FROM url_table 
WHERE url_hash=CRC32("http://gnu.org") AND url="http://gnu.org";

Es lohnt sich immer noch, Dinge zu hashen, selbst wenn die Kollisionszahl hoch ist, weil Sie nur den zweiten Vergleich (den mit der Zeichenkette) gegen die wiederholten Hashes durchführen.

Leider müssen Sie bei dieser Technik immer noch auf die Tabelle zugreifen, um die url Feld.

Einpacken

Einige Fakten, die Sie jedes Mal berücksichtigen sollten, wenn Sie über Optimierung sprechen wollen:

1. Integer-Vergleich ist viel schneller als String-Vergleich. Dies lässt sich am Beispiel der Emulation des Hash-Indexes in InnoDB .

2. Vielleicht macht das Hinzufügen zusätzlicher Schritte in einem Prozess diesen schneller, nicht langsamer. Dies kann durch die Tatsache veranschaulicht werden, dass man einen Prozess optimieren kann SELECT durch Aufteilung in zwei Schritte, wobei im ersten Schritt Werte in einer neu erstellten In-Memory-Tabelle gespeichert werden und anschließend die schwereren Abfragen an dieser zweiten Tabelle ausgeführt werden.

MySQL hat auch andere Indizes, aber ich denke, der B+Tree ist der am meisten benutzte überhaupt und der Hash-Index ist gut zu wissen, aber Sie können die anderen Indizes in der MySQL-Dokumentation .

Ich empfehle Ihnen dringend, das Buch "High Performance MySQL" zu lesen, die obige Antwort basierte definitiv auf dem Kapitel über Indizes.

Answer 3

Im Grunde ist ein Index eine Karte mit allen Schlüsseln, die nacheinander sortiert sind. Mit einer Liste in Ordnung, dann statt der Überprüfung jeder Schlüssel, kann es etwas wie dieses tun:

1: Gehe zur Mitte der Liste - ist sie höher oder niedriger als das, wonach ich suche?

2: Wenn höher, gehen Sie zum mittleren Punkt zwischen Mitte und unten, wenn niedriger, Mitte und oben

3: Ist höher oder niedriger? Springe wieder zum mittleren Punkt, usw.

Mit dieser Logik können Sie ein Element in einer sortierten Liste in etwa 7 Schritten finden, anstatt jedes Element zu überprüfen.

Natürlich gibt es noch mehr Komplexität, aber das gibt Ihnen die grundlegende Idee.

Answer 4

Werfen Sie einen Blick auf diesen Link: http://dev.mysql.com/doc/refman/5.0/en/mysql-indexes.html

Wie sie funktionieren, ist ein zu umfangreiches Thema, um es in einem SO-Beitrag zu behandeln.

Aquí ist eine der besten Erklärungen zu Indizes, die ich kenne. Leider ist sie für SQL Server und nicht für MySQL. Ich bin nicht sicher, wie ähnlich die beiden sind...

Answer 5

In MySQL InnoDB gibt es zwei Arten von Indizes.

1. Primärschlüssel, der als geclusterter Index bezeichnet wird. Index-Schlüsselwörter werden mit echten Datensatzdaten im B+Tree-Blattknoten gespeichert.

2. Sekundärschlüssel, der ein nicht geclusterter Index ist. Diese Indizes speichern nur die Schlüsselwörter des Primärschlüssels zusammen mit ihren eigenen Indexschlüsselwörtern in den B+Tree-Blattknoten. Bei der Suche im sekundären Index werden also zuerst die Schlüsselwörter des Primärschlüssels gefunden und der B+Tree des Primärschlüssels gescannt, um die tatsächlichen Datensätze zu finden. Dadurch wird der Sekundärindex im Vergleich zur Suche im Primärindex langsamer. Wenn jedoch der select Spalten sind alle im sekundären Index, dann muss der primäre Index B+Tree nicht noch einmal nachgeschlagen werden. Dies wird als abdeckender Index bezeichnet.