B-Tree vs Hash Tabelle

101

In MySQL ist ein Indextyp ein B-Baum, und der Zugriff auf ein Element in einem B-Baum erfolgt in logarithmisch amortisierter Zeit O(log(n)).

Der Zugriff auf ein Element in einer Hash-Tabelle erfolgt dagegen in O(1).

Warum wird keine Hash-Tabelle anstelle eines B-Baums verwendet, um auf Daten in einer Datenbank zuzugreifen?

JohnJohnGa
quelle
9
Hash-Tabellen unterstützen keine Bereichsabfragen und können während des Betriebs nicht reibungslos wachsen oder schrumpfen.
Hmakholm verließ Monica
3
@HenningMakholm Warum nicht Hash für Spalten, die keine Bereichsabfragen benötigen?
Pacerier

Antworten:

113

Sie können nur über ihren Primärschlüssel in einer Hashtabelle auf Elemente zugreifen. Dies ist schneller als mit einem Baumalgorithmus ( O(1)anstelle vonlog(n) ), aber Sie können keine Bereiche auswählen ( alles dazwischen xundy ). Baumalgorithmen unterstützen dies, Log(n)während Hash-Indizes zu einem vollständigen Tabellenscan führen können O(n). Auch der konstante Overhead von Hash-Indizes ist normalerweise größer ( was in der Theta-Notation kein Faktor ist, aber immer noch existiert ). Außerdem sind Baumalgorithmen normalerweise einfacher zu warten, wachsen mit Daten, Skalierung usw.

Hash-Indizes arbeiten mit vordefinierten Hash-Größen, sodass Sie am Ende einige "Buckets" haben, in denen die Objekte gespeichert sind. Diese Objekte werden erneut durchlaufen, um wirklich das richtige in dieser Partition zu finden.

Wenn Sie also kleine Größen haben, haben Sie viel Aufwand für kleine Elemente, große Größen führen zu weiterem Scannen.

Heutige Algorithmen für Hash-Tabellen skalieren normalerweise, aber die Skalierung kann ineffizient sein.

Es gibt tatsächlich skalierbare Hashing-Algorithmen. Fragen Sie mich nicht, wie das funktioniert - es ist mir auch ein Rätsel. AFAIK entwickelten sie aus einer skalierbaren Replikation, bei der ein erneutes Hashing nicht einfach ist.

Seine genannt RUSH - R eplication U nder S calable H Veraschungs, und diese Algorithmen sind somit RUSH Algorithmen bezeichnet.

Es kann jedoch vorkommen, dass Ihr Index im Vergleich zu Ihren Hash-Größen eine tolerierbare Größe überschreitet und Ihr gesamter Index neu erstellt werden muss. Normalerweise ist dies kein Problem, aber bei riesigen Datenbanken kann dies Tage dauern.

Der Kompromiss für Baumalgorithmen ist gering und sie eignen sich für fast jeden Anwendungsfall und sind daher Standard.

Wenn Sie jedoch einen sehr genauen Anwendungsfall haben und genau wissen, was und nur was benötigt wird, können Sie Hashing-Indizes nutzen.

Der Surrican
quelle
Können Sie mehr über die Indexwiederherstellung erklären? Bedeutet dies, dass die Tabelle für x Tage während der Neuerstellung des Index für die Verwendung in diesem Zeitraum überhaupt nicht verfügbar ist?
Pacerier
Dies hängt vom verwendeten Datenbanksystem ab. Die Frage umfasste nur die theoretischen Aspekte. Ich weiß nicht wirklich über die Implementierungsdetails gängiger Datenbanksysteme Bescheid. Aber normalerweise sollte dies nicht der Fall sein, da der zweite Index erstellt werden kann, während der erste noch verwendet wird
The Surrican
"Sie können nur über ihren Primärschlüssel auf Elemente zugreifen" - Sie meinen den Wert der Spalte mit dem Indexrecht, unabhängig davon, ob es sich um einen Primärschlüssel oder einen anderen Indextyp handelt?
Mark Fisher
84

Tatsächlich scheint es, dass MySQL beide Arten von Indizes verwendet, entweder eine Hash-Tabelle oder einen B-Baum gemäß dem folgenden Link .

Der Unterschied zwischen der Verwendung eines B-Baums und einer Hash-Tabelle besteht darin, dass Sie mit der ersteren Spaltenvergleiche in Ausdrücken verwenden können, die die Operatoren =,>,> =, <, <= oder ZWISCHEN verwenden, während die letztere nur für verwendet wird Gleichheitsvergleiche , die die Operatoren = oder <=> verwenden.

lmiguelvargasf
quelle
9
Das ist ungerecht. Die beste Antwort hat die niedrigste Punktzahl.
Андрей Беньковский
6
Genau das habe ich gesucht. Ich habe mich eher darum gekümmert, wie sich dies auf meine Anfragen auswirkt, als um eine technische Analyse.
Ben Dehghan
Ja! Diese Antwort hat mir am meisten geholfen.
Ron Ross
Vielen Dank, schon lange, aber diese Antwort hilft mir auch sehr.
Reham Fahmy
14

Die zeitliche Komplexität von Hashtabellen ist nur für ausreichend große Hashtabellen konstant (es müssen genügend Buckets vorhanden sein, um die Daten zu speichern). Die Größe einer Datenbanktabelle ist nicht im Voraus bekannt, daher muss die Tabelle von Zeit zu Zeit erneut aufbereitet werden, um eine optimale Leistung einer Hashtabelle zu erzielen. Das Aufwärmen ist auch teuer.

Emil Vikström
quelle
2
Kann ein Reshashing durchgeführt werden, während db online ist? Oder müssen wir den Tisch abschließen, um alles wieder aufzuwärmen?
Pacerier
1
Pacerier, MySQL unterstützen keine Hash-Indizes. Es ist theoretisch möglich, den Index erneut aufzubereiten, während die Datenbank noch online ist (weiterhin den alten Index verwenden, einen neuen Index erstellen, nach Abschluss auf den neuen Index umschalten), aber ich weiß nicht, was MySQL tun würde, wenn sie implementiert würden Hash-Anzeigen.
Emil Vikström
3
MySQL unterstützt Hash-Indizes, oder? : dev.mysql.com/doc/refman/5.5/en/index-btree-hash.html
Pacerier
Sie scheinen richtig zu sein. Das waren Neuigkeiten für mich! Ich muss versuchen, mit der Entwicklung Schritt zu halten :-) Dann sind Sie bei der Beantwortung Ihrer Frage weitaus besser dran als ich, aber wie gesagt: Es ist theoretisch möglich.
Emil Vikström
Übrigens, warum sagen Sie, dass "ein Btree leicht auf die Festplatte ausgelagert werden kann, eine Hashtabelle jedoch nicht"? Könnte eine Hashtabelle nicht auf der Festplatte gespeichert werden, da eine einfache Schlüsselsuche ausreichen würde?
Pacerier
6

Ich denke, Hashmaps skalieren nicht so gut und können teuer sein, wenn die gesamte Karte erneut aufbereitet werden muss.

Jonathan Weatherhead
quelle
0

Pick DB / OS basierte auf Hashing und funktionierte gut. Mit mehr Speicher heutzutage zur Unterstützung effizienter Hash-Tabellen mit geringer Dichte und redundantem Hashing zur Unterstützung bescheidener Bereichsabfragen würde ich sagen, dass Hashing möglicherweise noch seinen Platz hat (einige hätten lieber andere Formen der Ähnlichkeitsübereinstimmung außerhalb des Bereichs, wie Platzhalter und reguläre Ausdrücke ). Wir empfehlen außerdem das Kopieren, um Kollisionsketten zusammenhängend zu halten, wenn Speicherhierarchien große Geschwindigkeitsunterschiede aufweisen.

RONALD LOUI
quelle