B-Bäume sind wegen ihrer Cache-Effizienz eine der beliebtesten Datenstrukturen für Datenbanken und Dateisysteme. Während Hashtabellen dynamische Mengen oder dynamische assoziative Arrays in Hinsicht auf die Laufzeit für gewöhnlich besser repräsentieren, haben B-Bäume den Vorteil, dass sie auch im externen Speicher performant sind. Zudem können B-Bäume mit Zusatzdaten bereichert werden, z.B. mit Aggregationswerte wie das Speichern der Minima aller Werte im Teilbaum eines Knotens. Solche Aggregationswerte können genutzt werden, um weitere nützliche Anfragen wie Prefix-Sum zu unterstützen.
Eine naive Zeiger-basierte Implementierung von B-Bäumen braucht jedoch viel Platz, und kann die Cache-Effizienz von modernen Rechnerarchitekturen schlecht ausnutzen. Ein interessanter Ansatz ist es, die Anzahl der internen Knoten als auch die Höhe des B-Baums niedrig zu halten, sodass eine Traversierung von der Baumwurzel zu einem Blatt in wenigen Schritten erfolgen kann. Hierfür wurde in [1] der Vorschlag gemacht, (a) die Speicherkapazität der Blätter eines B-Baums zu vergrößern, und (b) das Erzeugen eines neuen Blattes möglichst weit hinauszuzögern. Das Letztere kann erzielt werden, wenn wir die Speicherkapazitäten der Blätter ausschöpfen, was durch eine Verteilung der gespeicherten Daten unterhalb der Nachbarblätter möglich ist. Ein Nebeneffekt hierbei ist, dass der modifizierte B-Baum wegen der geringeren Anzahl an internen Knoten deutlich speicher-sparsamer ist als eine Naiv-Implementierung.
Ziel dieser Arbeit ist es, auf praktische Fragestellungen der Arbeit [1] einzugehen. Hierzu zählt die algorithmische Optimierung hinsichtlich der Laufzeit und des Speicherplatzes. Die entworfene Implementierung soll als Prefix-Sum-Datenstruktur verwendbar sein können, beispielsweise für dynamische Datenstrukturen wie der dynamische FM-Index [2].
Masterarbeit.
[1]: Tomohiro I, Dominik Köppl: Load-Balancing Succinct B Trees, arXiv abs/2104.08751 (2021)
[2]: Nicola Prezza: A Framework of Dynamic Data Structures for String Processing, SEA 2017: 11:1-11:15. https://github.com/xxsds/DYNAMIC
Bei Interesse wenden Sie sich bitte Johannes Fischer.