Unterschied zwischen MySQL Btree-Index und Hash-Index

In MySQL werden die meisten Indizes (wie PRIMARY KEY, UNIQUE, INDEX und FULLTEXT) in BTREE gespeichert. Bei Verwendung der Speicher-Engine können Sie jedoch zwischen BTREE-Index und HASH-Index wählen. Die beiden unterschiedlichen Indextypen haben unterschiedliche Verwendungsbereiche.

• B-Baum-Indizes können Bereichs- und Präfixsuchen durchführen. Bei einem B-Baum mit N Knoten beträgt die Komplexität zum Abrufen eines Datensatzes O(LogN). Entspricht der binären Suche.
• Hash-Indizes können nur für Gleichheitssuchen verwendet werden, aber unabhängig davon, wie groß die Hash-Tabelle ist, beträgt die Suchkomplexität O(1).
  

Wenn die Werte sehr unterschiedlich sind und hauptsächlich nach gleichen Werten (=, <, >, in) gesucht wird, ist der Hash-Index mit einer Suchkomplexität von O(1) offensichtlich eine effizientere Wahl.
Wenn die Unterschiede zwischen den Werten relativ gering sind und die Bereichssuche im Mittelpunkt steht, ist B-Tree die bessere Wahl, da es die Bereichssuche unterstützt.

1. HASH-Index

Die Speicheradresse wird mithilfe der Hash-Funktion berechnet, sodass beim Abrufen keine Suche vom Stammknoten aus und eine Suche Ebene für Ebene wie bei Btree erforderlich ist.

Aufgrund der speziellen Struktur des Hash-Index ist seine Abrufeffizienz sehr hoch. Der Indexabruf kann einmal lokalisiert werden, im Gegensatz zum B-Tree-Index, der mehrere IO-Zugriffe vom Stammknoten zum Zweigknoten und schließlich zum Seitenknoten benötigt. Daher ist die Abfrageeffizienz des Hash-Index viel höher als die des B-Tree-Index.

Viele Leute haben möglicherweise wieder Fragen. Da die Effizienz des Hash-Index viel höher ist als die des B-Tree-Index, warum verwenden die Leute dann nicht den Hash-Index anstelle des B-Tree-Index? Alles hat zwei Seiten, und das gilt auch für Hash-Indizes. Obwohl Hash-Indizes hocheffizient sind, weisen sie aufgrund ihrer Besonderheit auch viele Einschränkungen und Nachteile auf. Die wichtigsten sind die folgenden.

(1) Hash-Indizes können nur die Abfragen "=", "IN" und "<=>" erfüllen und können nicht für Bereichsabfragen verwendet werden (Bereichsabfragen sind langsam).

Da der Hash-Index die Hash-Werte nach der Hash-Operation vergleicht, kann er nur für die Filterung gleicher Werte und nicht für die bereichsbasierte Filterung verwendet werden, da nicht garantiert werden kann, dass das Größenverhältnis der Hash-Werte nach der Verarbeitung durch den entsprechenden Hash-Algorithmus genau dasselbe ist wie vor der Hash-Operation.

(2) Hash-Indizes können nicht verwendet werden, um Datensortiervorgänge zu vermeiden.

Da der Hash-Index den Hash-Wert nach der Hash-Berechnung speichert und das Größenverhältnis des Hash-Werts nicht unbedingt genau mit dem Schlüsselwert vor der Hash-Operation übereinstimmt, kann die Datenbank die Indexdaten nicht verwenden, um Sortieroperationen zu vermeiden.

(3) Hash-Indizes können nicht mit partiellen Indexschlüsseln abgefragt werden.

Bei einem zusammengesetzten Index berechnet der Hash-Index den Hash-Wert, indem er die zusammengesetzten Indexschlüssel zusammenführt, anstatt den Hash-Wert separat zu berechnen. Daher kann der Hash-Index bei Abfragen über den ersten oder mehrere Indexschlüssel des zusammengesetzten Index nicht verwendet werden.

(4) Hash-Indizes können Tabellenscans zu keiner Zeit vermeiden.

Wie wir wissen, ist ein Hash-Index eine Tabelle, die den Hash-Wert des Hash-Operationsergebnisses und die entsprechenden Zeilenzeigerinformationen speichert, nachdem der Indexschlüssel gehasht wurde. Da verschiedene Indexschlüssel denselben Hash-Wert haben, kann die Abfrage nicht direkt vom Hash-Index aus abgeschlossen werden, selbst wenn die Anzahl der Datensätze ermittelt wird, die einen bestimmten Hash-Schlüsselwert erfüllen. Es ist weiterhin erforderlich, einen entsprechenden Vergleich durchzuführen, indem auf die tatsächlichen Daten in der Tabelle zugegriffen wird, um das entsprechende Ergebnis zu erhalten.

(5) Die Leistung eines Hash-Index ist nicht unbedingt höher als die eines B-Tree-Index, wenn eine große Anzahl gleicher Hash-Werte vorliegt.

Bei Indexschlüsseln mit geringer Selektivität werden bei der Erstellung eines Hash-Index zahlreiche Datensatzzeigerinformationen im selben Hash-Wert gespeichert und diesem zugeordnet. Dadurch wird das Auffinden eines bestimmten Datensatzes sehr mühsam und es werden mehrere Zugriffe auf die Tabellendaten vergeudet, was zu einer schlechten Gesamtleistung führt.

2. B+ Baum

• Der Suchvorgang des B+-Baums
  

Wie in der Abbildung gezeigt, wird, wenn Sie das Datenelement 29 finden möchten, zuerst Datenträgerblock 1 von der Festplatte in den Speicher geladen. Zu diesem Zeitpunkt erfolgt ein IO. Eine binäre Suche im Speicher wird verwendet, um zu bestimmen, dass 29 zwischen 17 und 35 liegt. Der P2-Zeiger von Datenträgerblock 1 ist gesperrt. Die Speicherzeit ist sehr kurz (im Vergleich zum Datenträger-IO) und kann ignoriert werden. Datenträgerblock 3 wird über die Datenträgeradresse des P2-Zeigers von Datenträgerblock 1 von der Festplatte in den Speicher geladen. Der zweite IO erfolgt. 29 liegt zwischen 26 und 30. Der P2-Zeiger von Datenträgerblock 3 ist gesperrt. Datenträgerblock 8 wird über den Zeiger in den Speicher geladen. Der dritte IO erfolgt. Gleichzeitig wird eine binäre Suche im Speicher durchgeführt, um 29 zu finden, und die Abfrage endet. Insgesamt werden drei IOs durchgeführt. Tatsächlich kann ein 3-Schicht-B+-Baum Millionen von Daten darstellen. Wenn für die Suche nach Millionen von Daten nur drei IOs erforderlich sind, ist die Leistungssteigerung enorm. Wenn kein Index vorhanden ist, ist für jedes Datenelement ein IO erforderlich, sodass insgesamt Millionen von IOs erforderlich sind, was offensichtlich sehr kostspielig ist.

• B+-Baumeigenschaften
  

1. Das Indexfeld sollte möglichst klein sein:

Durch die obige Analyse wissen wir, dass die Anzahl der IO-Vorgänge von der Höhe h von b+Zahl abhängt. Angenommen, die Daten in der aktuellen Datentabelle sind N und die Anzahl der Datenelemente in jedem Datenträgerblock ist m, dann ist h=㏒(m+1)N. Wenn das Datenvolumen N konstant ist, gilt: Je größer m, desto kleiner h; und m = Datenträgerblockgröße/Datenelementgröße. Die Datenträgerblockgröße ist die Größe einer Datenseite, die fest ist. Wenn der von den Datenelementen belegte Speicherplatz kleiner und die Anzahl der Datenelemente größer ist, ist die Höhe des Baums geringer. Aus diesem Grund sollte jedes Datenelement, d. h. das Indexfeld, so klein wie möglich sein. Beispielsweise belegt int 4 Bytes, also die Hälfte der 8 Bytes von bigint. Aus diesem Grund erfordert der B+-Baum, dass die tatsächlichen Daten in den Blattknoten und nicht in den inneren Knoten platziert werden. Sobald sie in den inneren Knoten platziert sind, sinken die Datenelemente der Festplattenblöcke erheblich, wodurch die Höhe des Baums zunimmt. Wenn das Datenelement gleich 1 ist, degeneriert es zu einer linearen Liste.

2. Das am weitesten links stehende Übereinstimmungsmerkmal des Index (d. h. Übereinstimmung von links nach rechts):

Wenn die Datenelemente des B+-Baums zusammengesetzte Datenstrukturen sind, wie etwa (Name, Alter, Geschlecht), erstellt der B+-Baum den Suchbaum der Reihe nach von links nach rechts. Wenn beispielsweise Daten wie (Zhang San, 20, W) 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 nacheinander verglichen, um schließlich die abgerufenen Daten zu erhalten. Wenn jedoch Daten ohne Namen wie etwa (20, W) kommen, weiß der B+-Baum nicht, welcher Knoten als nächstes überprüft werden soll, da der Name der erste Vergleichsfaktor beim Erstellen des Suchbaums ist und es notwendig ist, zuerst basierend auf dem Namen zu suchen, um zu wissen, wo als nächstes abgefragt werden soll. Wenn beispielsweise Daten wie (Zhang San, F) abgerufen werden, kann der b+-Baum den Namen verwenden, um die Suchrichtung anzugeben, aber das nächste Feld „Alter“ fehlt. Daher kann er nur die Daten mit dem Namen „Zhang San“ finden und dann die Daten mit dem Geschlecht „F“ abgleichen. Dies ist eine sehr wichtige Eigenschaft, nämlich das am weitesten links stehende Übereinstimmungsmerkmal des Index.

Oben finden Sie detaillierte Informationen zum Unterschied zwischen MySQL-B-Tree-Index und Hash-Index. Weitere Informationen zu MySQL-B-Tree-Index und Hash-Index finden Sie in den anderen verwandten Artikeln auf 123WORDPRESS.COM!