Fast and space-efficient indexing for main-memory database systems on modern hardware
Robert Binna · Digital Library of the University of Innsbruck (University of Innsbruck) · 2020
Der rasante Fortschritt im Bereich der Hardwareentwicklung und das exponentielle Wachstum des Arbeitsspeichers im Laufe der vergangenen Jahrzehnte hat dazu geführt das Design von Indexstrukturen grundlegend zu überdenken. Während bei traditionellen plattenorientierten Datenbanksystemen B-Bäume vorherrschen, stellen Trie-basierte Indexstrukturen bei modernen Multiprozessorarchitekturen, die über enorme Hauptspeicherkapazitäten verfügen, eine geeignete Alternative dar. Der Hauptvorteil von Trie Strukturen ist ihre konstante Zugriffszeit innerhalb eines Knotens. Neben ihren Vorteilen haben existierende Tries den Nachteil, dass sie pro Knoten nur Teilschlüssel einer fixen vordefinierten Länge berücksichtigen. Dies führt dazu, dass bei ungleich verteilten Schlüsselsätzen, Knoten spärlich gefüllt sind und dadurch Baumhöhen und Zugriffszeiten ansteigen. In dieser Arbeit stellen wir den Height Optimized Trie (HOT) vor, der die betrachteten Bits pro Knoten dynamisch wählt um einen möglichst hohen Verzweigungsgrad und damit geringe Baumhöhen und Zugriffszeiten zu erzielen. Zu diesem Zwecke stellen wir Einfüge- und Löschalgorithmem vor, die die Höhe der Trie-Struktur, unter Einhaltung eines maximalen Verzweigungsgrades pro Knoten, schrittweise minimieren. Der resultierende HOT besitzt drei Eigenschaften: (I) die Höhe jedes HOT ist minimal, (II) für den selben Datensatz besitzt jeder HOT die selbe eindeutige Struktur und (III) jeder Teilbaum eines HOT ist selbst ein HOT. Wir beweisen jede dieser drei Eigenschaften im Zuge dieser Arbeit. Aufbauend auf diesem theoretischen Fundament führen wir sieben unterschiedliche Knoten-Layouts für HOT Strukturen ein. Während hierarchische Knoten-Layouts durch ausgefeilte Kodierungstechniken eine hohe Speichereffizienz erzielen, nützen linearisierte Knoten-Layouts die SIMD-Anweisungen moderner Prozessoren um geringe Zugriffszeiten zu realisieren. Anhand der Ergebnisse einer ausführlichen Evaluierung, unter Berücksichtigung verschiedener Datensätze und Anwendungszenarien, zeigen wir, dass das Adaptive Linearised Node Layout die höchste Zugriffsleistung erreicht und andere moderne Indexstrukturen für Zeichenketten in Bezug auf Suchleistung und Speicherbedarf übertrifft, während es für ganzzahlige Schlüssel konkurrenzfähig ist. Die Ergebnisse zeigen weiters, dass das Leaf Optimized Node Layout den geringsten Speicherverbrauch aller evaluierten Indexe, mit weniger als zwei Byte pro Schlüssel, erzielt. Zusammenfassend zeigen unsere Ergebnisse, dass sich HOT als Allzweck-Indexstruktur sehr gut eignet und durch entsprechende Knoten-Layouts für unterschiedlichste Anwendungszenarien angepasst werden kann.