Was ist ein Index in MySQL? Kurze Analyse des Indexspeichermodells

Die folgende Spalte „MySQL-Tutorial“ bietet Ihnen eine detaillierte Analyse der Indizes in MySQL und vermittelt Ihnen einige Kenntnisse über MySQL-Indizes.

MySQL-Datenbank sollte eine der am häufigsten verwendeten Datenbanken sein. Es zeigt sich in verschiedenen großen und kleinen Unternehmen. Wie gut beherrschen Sie die MySQL-Datenbank? Wenn wir es besser nutzen wollen, müssen wir es zuerst verstehen. Wie das Sprichwort sagt: Wenn ein Arbeiter seine Arbeit gut machen will, muss er zuerst seine Werkzeuge schärfen.

Dieser Artikel führt Sie zu einer eingehenden Analyse einiger Kenntnisse über MySQL-Indizes. Lassen Sie uns zunächst verstehen, was ein Index ist und wie das Indexspeichermodell abgeleitet wird. Warum wird die zugrunde liegende Datenstruktur ausgewählt? ? Was ist ein Index?

Eine Tabelle enthält 5 Millionen Daten. Führen Sie eine Where-Abfrage für das Namensfeld ohne Index aus:

select * from user_innodb where name ='小马';

Was ist, wenn es einen Index für das Namensfeld gibt? Erstellen Sie einen Index für das Namensfeld und führen Sie dieselbe Abfrage erneut aus.

ALTER TABLE user_innodb DROP INDEX idx_name; 
ALTER TABLE user_innodb ADD INDEX idx_name (name);

Im Vergleich zu Abfragen ohne Indizes ist die Effizienz von Abfragen mit Indizes um ein Vielfaches unterschiedlich.

In diesem Fall sollten Sie intuitiv spüren, dass die Indizierung die Leistung des Datenabrufs erheblich verbessern kann.

Was genau ist ein Index? Warum kann es einen so großen Einfluss auf unsere Anfragen haben? Was passiert, wenn der Index erstellt wird?

Indexdefinition

Ein Datenbankindex ist eine sortierte Datenstruktur in einem Datenbankverwaltungssystem (DBMS), die beim schnellen Abfragen und Aktualisieren von Daten in Datenbanktabellen hilft.

Daten werden in Form von Dateien auf der Festplatte gespeichert, und jede Datenzeile hat ihre Festplattenadresse. Wenn kein Index vorhanden ist, müssen wir ein Datenelement aus 5 Millionen Datenzeilen abrufen und können nur alle Daten in dieser Tabelle durchlaufen, bis wir dieses Datenelement finden.

Aber nachdem wir den Index haben, müssen wir diese Daten nur noch im Index abrufen, da es sich um eine spezielle Datenstruktur handelt, die für den schnellen Abruf entwickelt wurde. Nachdem wir die Festplattenadresse gefunden haben, auf der die Daten gespeichert sind, können wir sie abrufen die Daten.

Indextypen

In InnoDB gibt es drei Indextypen: gewöhnlicher Index, eindeutiger Index (Primärschlüsselindex ist ein spezieller eindeutiger Index) und Volltextindex.

Normal

: Wird auch als nicht eindeutiger Index bezeichnet und ist der gebräuchlichste Index ohne Einschränkungen.

Unique

: Ein eindeutiger Index erfordert, dass Schlüsselwerte nicht wiederholt werden können. Darüber hinaus ist zu beachten, dass der Primärschlüsselindex ein spezieller eindeutiger Index ist. Er unterliegt außerdem einer zusätzlichen Einschränkung, die erfordert, dass der Schlüsselwert nicht leer sein darf. Primärschlüsselindizes werden mithilfe von Primärschlüsseln erstellt.

Volltext

: Wenn Sie bei relativ großen Datenmengen, beispielsweise wenn wir Nachrichteninhalte und mehrere KB an Daten speichern, das Problem der geringen Abfrageeffizienz lösen möchten, können Sie einen Volltextindex erstellen. Volltextindizes können nur für Texttypfelder wie char, varchar und text erstellt werden. Ein Index ist eine Datenstruktur. Welche Art von Datenstruktur sollte er also wählen, um einen effizienten Datenabruf zu erreichen?

Abzug des Indexspeichermodells

Binäre Suche

Nach Double Eleven hat deine Freundin ein Ratespiel mit dir gespielt. Rate mal, wie viel ich gestern gekauft habe, und gebe dir fünf Chancen.

10000? Niedrig. 30000? Hoch. Was werden Sie als nächstes erraten? 20000. Warum haben Sie nicht 11.000 oder 29.000 erraten? Dies ist eine Idee der binären Suche, auch Halbsuche genannt. Jedes Mal reduzieren wir die Kandidatendaten um die Hälfte. Diese Methode ist effizienter, wenn die Daten sortiert wurden.

Also können wir zunächst die Verwendung eines geordneten Arrays als indizierte Datenstruktur in Betracht ziehen.

Gleiche Abfragen und Vergleichsabfragen geordneter Arrays sind sehr effizient, es gibt jedoch ein Problem beim Aktualisieren von Daten. Möglicherweise müssen große Datenmengen verschoben werden (Index ändern), sodass sie nur zum Speichern statischer Daten geeignet sind.

Um häufige Änderungen wie das Einfügen von Daten zu unterstützen, müssen wir verknüpfte Listen verwenden. Bei verknüpften Listen ist die Sucheffizienz immer noch nicht hoch genug, wenn es sich um eine einfach verknüpfte Liste handelt.

Gibt es also eine verknüpfte Liste, die die binäre Suche verwenden kann?

Um dieses Problem zu lösen, wurde BST (Binary [ˈbaɪnəri] Search Tree) geboren, den wir einen binären Suchbaum nennen.

Binärer Suchbaum (Binärer Suchbaum)

Alle Knoten im linken Teilbaum sind kleiner als der übergeordnete Knoten, und alle Knoten im rechten Teilbaum sind größer als der übergeordnete Knoten. Nach der Projektion auf eine Ebene wird daraus eine geordnete lineare Tabelle.

二叉查找树既能够实现快速查找，又能够实现快速插入。

但是二叉查找树有一个问题：查找耗时是和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成 O(n)。

什么情况是最坏的情况呢？

还是刚才的这一批数字，如果我们插入的数据刚好是有序的，2、10、12、15、 21、28

这个时候 BST 会变成链表（ “斜树”），这种情况下不能达到加快检索速度的目的，和顺序查找效率是没有区别的。

造成它倾斜的原因是什么呢？

因为左右子树深度差太大，这棵树的左子树根本没有节点——也就是它不够平衡。

所以，我们有没有左右子树深度相差不是那么大，更加平衡的树呢？

这个就是平衡二叉树，叫做 Balanced binary search trees，或者 AVL 树。

平衡二叉树（AVL Tree）

平衡二叉树的定义：左右子树深度差绝对值不能超过 1。

是什么意思呢？比如左子树的深度是 2，右子树的深度只能是 1 或者 3。

这个时候我们再按顺序插入 1、2、3、4、5、6，一定是这样，不会变成一棵“斜树”。

那 AVL 树的平衡是怎么做到的呢？怎么保证左右子树的深度差不能超过 1 呢？ 例如：插入 1、2、3。

当我们插入了 1、2 之后，如果按照二叉查找树的定义，3 肯定是要在 2 的右边的，这个时候根节点 1 的右节点深度会变成 2，但是左节点的深度是 0，因为它没有子节点，所以就会违反平衡二叉树的定义。

那应该怎么办呢？因为它是右节点下面接一个右节点，右-右型，所以这个时候我们要把 2 提上去，这个操作叫做左旋。

同样的，如果我们插入 7、6、5，这个时候会变成左左型，就会发生右旋操作，把 6 提上去。

所以为了保持平衡，AVL 树在插入和更新数据的时候执行了一系列的计算和调整的操作。

平衡的问题我们解决了，那么平衡二叉树作为索引怎么查询数据？ 在平衡二叉树中，一个节点，它的大小是一个固定的单位，作为索引应该存储什么内容？

第一个：索引的键值。比如我们在 id 上面创建了一个索引，我在用 where id =1 的条件查询的时候就会找到索引里面的 id 的这个键值。

第二个：数据的磁盘地址，因为索引的作用就是去查找数据的存放的地址。

第三个因为是二叉树，它必须还要有左子节点和右子节点的引用，这样我们才能找到下一个节点。比如大于 26 的时候，走右边，到下一个树的节点，继续判断。

如果是这样存储数据的话，我们来看一下会有什么问题。

首先，索引的数据，是放在硬盘上的。查看数据和索引的大小：

select CONCAT(ROUND(SUM(DATA_LENGTH/1024/1024),2),'MB') AS data_len, 
CONCAT(ROUND(SUM(INDEX_LENGTH/1024/1024),2),'MB') as index_len 
from information_schema.TABLES 
where table_schema='gupao' and table_name='user_innodb';

当我们用树的结构来存储索引的时候，因为拿到一块数据就要在 Server 层比较是不是需要的数据，如果不是的话就要再读一次磁盘。访问一个节点就要跟磁盘之间发生一次 IO。InnoDB 操作磁盘的最小的单位是一页（或者叫一个磁盘块），大小是 16K(16384 字节)。

Dann ist ein Baumknoten 16 KB groß. Wenn wir nur einen Schlüsselwert + Daten + Referenz in einem Knoten speichern, z. B. in einem Ganzzahlfeld, werden möglicherweise nur ein Dutzend oder Dutzende Bytes verwendet, was weit von der 16-KB-Kapazität entfernt ist, also beim Zugriff auf einen Baumknoten Bei einem IO wird viel Platz verschwendet.

Wenn also jeder Knoten zu wenig Daten speichert, müssen wir auf mehr Knoten zugreifen, um die benötigten Daten aus dem Index zu finden, was bedeutet, dass es zu viele Interaktionen mit der Festplatte gibt.

Im Zeitalter mechanischer Festplatten dauert es jedes Mal etwa 10 ms, Daten von der Festplatte zu lesen. Je mehr Interaktionen es gibt, desto mehr Zeit wird verbraucht.

Im Bild oben haben wir beispielsweise 6 Daten in einer Tabelle. Wenn wir id=37 abfragen, müssen wir dreimal mit der Festplatte interagieren ? Diese Zeit ist noch schwieriger einzuschätzen.

Was ist also unsere Lösung?

Die erste besteht darin, jeden Knoten mehr Daten speichern zu lassen.

Zweitens: Je mehr Schlüsselwörter sich auf einem Knoten befinden, desto mehr Zeiger haben wir, was bedeutet, dass es mehr Gabeln geben kann.

Denn je mehr Zweige vorhanden sind, desto geringer wird die Tiefe des Baums (der Wurzelknoten ist 0). Werden sich unsere Bäume auf diese Weise von ihrem ursprünglichen hohen und dünnen Aussehen zu einem kleinen und dicken Aussehen verändern?

Zu diesem Zeitpunkt ist unser Baum nicht mehr zweigabelig, sondern mehrgabelig bzw. mehrzweigig.

Mehrfach ausgeglichener Suchbaum (B-Baum)

Wie der AVL-Baum speichert der B-Baum Schlüsselwerte, Datenadressen und Knotenreferenzen in Verzweigungsknoten und Blattknoten.

Es hat eine Besonderheit: Die Anzahl der Forks (Anzahl der Pfade) ist immer um 1 größer als die Anzahl der Schlüsselwörter. In dem von uns gezeichneten Baum speichert beispielsweise jeder Knoten zwei Schlüsselwörter, sodass es drei Zeiger gibt, die auf drei untergeordnete Knoten zeigen.

Was sind die Suchregeln für B Tree?

Zum Beispiel wollen wir in dieser Tabelle 15 finden. Da 15 weniger als 17 ist, gehen Sie nach links. Da 15 größer als 12 ist, gehen Sie nach rechts. 15 wurde in Festplattenblock 7 gefunden und es wurden nur 3 IOs verwendet.

Ist das effizienter als der AVL-Baum? Wie erkennt B Tree also, dass ein Knoten mehrere Schlüsselwörter speichert und dennoch das Gleichgewicht beibehält? Was ist der Unterschied zu AVL-Bäumen?

Wenn beispielsweise der maximale Grad (Anzahl der Wege) 3 beträgt, fügen wir die Daten 1, 2 und 3 ein. Beim Einfügen von 3 sollten sie sich im ersten Festplattenblock befinden, wenn ein Knoten jedoch drei Schlüsselwörter hat, Dies bedeutet, dass es 4 Zeiger gibt und die untergeordneten Knoten zu 4-Wege-Knoten werden, sodass zu diesem Zeitpunkt eine Aufteilung durchgeführt werden muss (eigentlich B + Baum). Rufen Sie die mittleren Daten 2 auf und verwandeln Sie 1 und 3 in untergeordnete Knoten von 2.

Wenn Sie einen Knoten löschen, erfolgt ein umgekehrter Zusammenführungsvorgang.

Beachten Sie, dass es sich dabei um eine Aufteilung und Zusammenführung handelt, die sich von der Links- und Rechtsdrehung des AVL-Baums unterscheidet.

Wir fügen weiterhin 4 und 5 ein, und der B-Baum wird geteilt und wieder zusammengeführt.

Daran können wir auch erkennen, dass es beim Aktualisieren des Index viele strukturelle Anpassungen am Index geben wird, was erklärt, warum wir keine Indizes für häufig aktualisierte Spalten erstellen bzw. die nicht aktualisieren Primärschlüssel.

Das Teilen und Zusammenführen von Knoten ist eigentlich das Teilen und Zusammenführen von InnoDB-Seiten.

B+Tree (erweiterte Version von B Tree)

B Tree ist bereits sehr effizient. Warum muss MySQL B Tree noch verbessern und endlich B+Tree verwenden?

Im Allgemeinen löst diese verbesserte Version von B-Tree umfassendere Probleme als B-Tree.

Werfen wir einen Blick auf die Speicherstruktur des B+-Baums in InnoDB:

Der B+-Baum in MySQL weist mehrere Merkmale auf:

1. Die Anzahl seiner Schlüsselwörter entspricht der Anzahl der Pfade ;

2. B+Tree speichert keine Daten im Wurzelknoten oder in den Zweigknoten, sondern nur in den Blattknoten. Die Suche nach Schlüsselwörtern führt nicht direkt zurück, sondern zu den Blattknoten der letzten Ebene. Wenn wir beispielsweise nach id=28 suchen, befinden sich alle Daten auf den Blattknoten, obwohl sie direkt auf der ersten Ebene gefunden wird. Daher werde ich weiter nach unten suchen, bis zu den Blattknoten.

3. Jeder Blattknoten von B + Baum fügt einen Zeiger auf den benachbarten Blattknoten hinzu, und seine letzten Daten zeigen auf die ersten Daten des nächsten Blattknotens und bilden so eine geordnete verknüpfte Listenstruktur.

4. Es ruft Daten basierend auf dem Intervall links-geschlossen-rechts-offen ab [ ).

Datensuchprozess von B+Tree:

1. Wenn wir beispielsweise nach 28 suchen möchten, haben wir den Schlüsselwert am Wurzelknoten gefunden, aber da es sich nicht um einen untergeordneten Seitenknoten handelt, suchen wir weiter nach unten. 28 ist der kritische Wert auf der linken Seite -geschlossenes und rechts-offenes Intervall von [28,66), also gehen wir zum mittleren untergeordneten Knoten und suchen dann weiter, was der kritische Wert des links-geschlossenen, rechts-offenen Intervalls von [28,34) ist ), also gehen wir zum linken untergeordneten Knoten und finden schließlich die erforderlichen Daten auf dem Blattknoten.

2. Zweitens, wenn es sich um eine Bereichsabfrage handelt, wenn Sie beispielsweise Daten von 22 bis 60 abfragen möchten, müssen Sie nach dem Finden von 22 nur nacheinander die Knoten und Zeiger durchlaufen, um auf alle Datenknoten gleichzeitig zuzugreifen Dadurch wird die Effizienz der Intervallabfrage erheblich verbessert (es ist nicht erforderlich, zum wiederholten Durchlaufen der Suche zum oberen übergeordneten Knoten zurückzukehren).

Funktionen von B+Tree in InnoDB:

1. Es ist eine Variante von B Tree. Es kann alle Probleme lösen, die B Tree lösen kann. Was sind die beiden Hauptprobleme, die B Tree löst? (Jeder Knoten speichert mehr Schlüsselwörter; mehr Pfade)

2. Stärkere Datenbank- und Tabellenscanfunktionen (wenn wir einen vollständigen Tabellenscan für die Tabelle durchführen möchten, müssen wir nur die Blattknoten durchlaufen, nicht den gesamten B +Tree, um alle Daten abzurufen);

3. B+Tree verfügt über stärkere Lese- und Schreibfunktionen auf der Festplatte als B Tree (der Stammknoten und die Zweigknoten speichern den Datenbereich nicht, sodass ein Knoten mehr Schlüsselwörter und mehr Schlüsselwörter speichern kann werden auf einmal auf die Festplatte geladen);

4. Die Sortierfähigkeit ist stärker (da es einen Zeiger auf den nächsten Datenbereich auf dem Blattknoten gibt und die Daten eine verknüpfte Liste bilden); ist stabiler (B + Tree erhält immer Daten von Blattknoten, sodass die Anzahl der E / A stabil ist).

5. Postscript

Nachdem ich das gesehen habe, glaube ich, dass jeder wissen sollte, warum MySQL den B+-Baum als Datenstrukturmodell des Index verwendet.

Weitere Kenntnisse zum Thema Programmierung finden Sie unter:

Einführung in die Programmierung

! !

Das obige ist der detaillierte Inhalt vonWas ist ein Index in MySQL? Kurze Analyse des Indexspeichermodells. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!