Datenbankindizierung auf den Punkt gebracht mit B+Tree und Hash im Vergleich

Es wird oft gesagt, dass die Indizierung eine Methode ist, um Abfragen effizient zu verarbeiten, falls Ihre Datenbank groß genug ist. Dieser Beitrag dient dazu, zusammenzufassen, was Datenbankindex ist, und Hash und B+Tree erneut zu besuchen.

Index ist eine Datenstruktur, die Datensätze organisiert, um bestimmte Arten von Abrufvorgängen zu optimieren. Wir können einen Index für ein Feld der Tabelle erstellen und dann alle Datensätze abrufen, die die Suchbedingungen für search-key erfüllen Feld. Ohne Index würde unsere Abfrage am Ende den gesamten Inhalt der Tabelle linear scannen, um nur einen oder wenige Datensätze abzurufen.

In diesem Beitrag möchte ich die Leistung und Anwendungsfälle von zwei gängigen Indizierungstechniken zusammenfassen:Hash-Index und B+Baum

Hash-Index

Diese Technik wird häufig zum Erstellen von Indizes im Hauptspeicher verwendet weil es von Natur aus schnell auffindbar ist. Es hat eine durchschnittliche Operationskomplexität von O(1) und eine Speicherkomplexität von O(n).
In vielen Büchern wird der Begriff bucket verwendet um eine Speichereinheit zu bezeichnen, die einen oder mehrere Datensätze speichert
Beim Hashing gibt es zwei Dinge zu besprechen:

• Hash-Funktion:ordnet Suchschlüssel (als Eingabe) einer Ganzzahl zu, die diesen Schlüssel im Bucket darstellt.
• Hashing-Schema:Umgang mit Schlüsselkollisionen nach dem Hashing.

Manche Leute fragen:Warum Kollision? Gibt es jemals eine perfekte Hash-Funktion? Nehmen wir an, Ihre Schlüssel sind ein unendlicher Satz, es ist unmöglich, sie einem Satz von 32-Bit-Ganzzahlen zuzuordnen, ohne dass es zu keiner Kollision kommt. Es sollte einen Kompromiss zwischen Berechnung und Kollisionsrate geben.

Es gibt einige erwähnenswerte Hashing-Schemata:lineares Sondieren, verkettetes Hashing und erweiterbares Hashing. Such-/Einfüge-/Löschalgorithmen variieren je nach Hashing-Schema, zum Beispiel behandelt verkettetes Hashing Schlüsselkollisionen, indem Elemente denselben Hashwert in demselben Bucket platzieren.

Vorteile

• Der Hash-Index eignet sich für Gleichheits- oder Primärschlüsselsuche. Abfragen können vom Hash-Index profitieren, um amortisierte O(1)-Suchkosten zu erhalten. Zum Beispiel:SELECT name, id FROM student WHERE id = '1315';

Nachteile

Die Hash-Tabelle hat einige Einschränkungen:

• Bereichsabfragen sind nicht effizient. Die Hash-Tabelle basiert auf einer gleichmäßigen Verteilung. Mit anderen Worten, Sie haben keine Kontrolle darüber, wo ein Indexeintrag platziert wird.
• Geringe Skalierbarkeit:Die Leistung des Suchvorgangs kann sich verschlechtern, wenn es viele Kollisionen gibt und es erforderlich ist, die Größe der Hash-Tabelle zu ändern und dann vorhandene Indexeinträge erneut zu hashen.

B+Baum

Dies ist eine selbstausgleichende Baumdatenstruktur, die Daten in sortierter Reihenfolge hält und eine schnelle Suche innerhalb jedes Knotens ermöglicht, typischerweise unter Verwendung einer binären Suche.
B+Tree ist eine Standard-Indeximplementierung in fast allen relationalen Datenbanksystemen.

B+Tree ist im Grunde ein M-Wege-Suchbaum, der die folgende Struktur hat:

• perfekte Balance:Blattknoten haben immer die gleiche Höhe.
• jeder innere Knoten außer der Wurzel ist mindestens halb voll (M/2 − 1 <=Anzahl der Tasten <=M − 1).
• jeder innere Knoten mit k Schlüsseln hat k+1 Nicht-Null-Kinder.

Jeder Knoten des Baums hat ein Array von sortierten Schlüssel-Wert-Paaren. Das Schlüssel-Wert-Paar wird aus (Suchschlüsselwert, Zeiger) für Wurzel- und innere Knoten konstruiert. Blattknotenwerte können 2 Möglichkeiten sein:

• der eigentliche Datensatz
• der Zeiger auf den aktuellen Datensatz

Suchen Sie einen Wert v

• Beginnen Sie mit dem Stammknoten
• Während der Knoten kein Blattknoten ist, tun wir:
  • Finde das kleinste Ki, wobei Ki>=v
  • Wenn Ki ==v:aktuellen Knoten auf den Knoten setzen, auf den Pi+1 zeigt
  • Andernfalls setzen Sie den aktuellen Knoten auf den Knoten, auf den Pi zeigt

Doppelte Schlüssel

Im Allgemeinen kann der Suchschlüssel doppelt vorhanden sein, um dies zu lösen, bieten die meisten Datenbankimplementierungen einen zusammengesetzten Suchschlüssel. Beispielsweise möchten wir einen Index für student_name erstellen dann sollte unser zusammengesetzter Suchschlüssel (student_name, Ap) lauten, wobei Ap der Primärschlüssel der Tabelle ist.

Vorteile

Es gibt zwei Hauptfunktionen, die B+tree bietet:

• Minimieren von E/A-Vorgängen
  • Reduzierte Höhe:B+Tree hat einen ziemlich großen Verzweigungsfaktor (oft verwendeter Wert zwischen 50 und 2000), wodurch der Baum dick und kurz wird. Die folgende Abbildung zeigt einen B+Baum mit einer Höhe von 2. Da wir sehen können, dass die Knoten verteilt sind, sind weniger Knoten erforderlich, um zu einem Blatt zu gelangen. Die Kosten für die Suche nach einem einzelnen Wert sind die Höhe des Baums + 1 für den wahlfreien Zugriff auf die Tabelle.
• Skalierbarkeit:
  • Sie haben eine vorhersagbare Leistung für alle Fälle, insbesondere O(log(n)). Für Datenbanken ist dies normalerweise wichtiger als eine bessere Best- oder Average-Case-Leistung.
  • Der Baum bleibt durch seine Implementierung immer im Gleichgewicht. Ein B+Baum mit n Schlüsseln hat immer eine Tiefe von O(log(n)). Daher wird die Leistung nicht beeinträchtigt, wenn die Datenbank größer wird. Ein vierstufiger Baum mit einem Verzweigungsfaktor von 500 kann bis zu 256 TB speichern, vorausgesetzt, dass eine Seite eine Größe von 4 KB hat.

• B+Tree eignet sich am besten für Bereichsabfragen, zum Beispiel "SELECT * FROM student WHERE age > 20 AND age < 22"

Fazit

Obwohl der Hash-Index in Bezug auf Abfragen mit exakter Übereinstimmung besser abschneidet, ist B+Tree dank seiner konsistenten Gesamtleistung und hohen Skalierbarkeit wohl die am weitesten verbreitete Indexstruktur in RDBMS.

Vor kurzem hat der protokollstrukturierte Zusammenführungsbaum (LSM-Baum) als Anwärter auf den B+-Baum erhebliches Interesse geweckt, da seine Datenstruktur eine bessere Effizienz der Speicherplatznutzung ermöglichen könnte. Ich werde es weiter untersuchen und in naher Zukunft einen Beitrag darüber schreiben.