wake-up-neo.com

B-Tree vs Hash-Tabelle

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?

86
JohnJohnGa

Sie können auf Elemente nur über ihren Primärschlüssel in einer Hash-Tabelle zugreifen. Dies ist schneller als mit einem Baumalgorithmus (O(1) anstelle von log(n)), aber Sie können keine Bereiche auswählen ( alles zwischen x und y). Tree-Algorithmen unterstützen dies in Log(n), wohingegen Hash-Indizes zu einem vollständigen Tabellenscan O(n) führen können. 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 die 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 zum weiteren Scannen.

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

Es gibt in der Tat skalierbare Hashing-Algorithmen. Fragen Sie mich nicht, wie das funktioniert - es ist mir auch ein Rätsel. AFAIK Sie sind aus einer skalierbaren Replikation entstanden, bei der das erneute Hashing nicht einfach ist.

Es heißt Rush - R eplication U nder - S calable H ashing, und diese Algorithmen werden daher Rush-Algorithmen genannt.

Es kann jedoch vorkommen, dass Ihr Index eine zulässige Größe im Vergleich zu Ihren Hash-Größen überschreitet und der gesamte 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 präzisen Anwendungsfall haben und genau wissen, was und nur was benötigt wird, können Sie Hashing-Indizes nutzen.

90
The Surrican

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

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

59
lmiguelvargasf

Die zeitliche Komplexität von Hashtabellen ist nur für Hashtabellen mit ausreichender Größe 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 ab und zu erneut aufbereitet werden, um eine optimale Leistung aus einer Hash-Tabelle zu erzielen. Das Aufwärmen ist ebenfalls teuer.

13
Emil Vikström

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