Kombination des LSM-Baumes mit Patricia Tries zur Beschleunigung von Indexen mit Zeichenketten-Strings

- Bachelorarbeit -


Beschreibung:

B+-Bäume sind jedoch langsam, wenn viele Einfügungen zu erwarten sind. Daher werden oft die sogenannten LSM-Bäume (bzw. deren Varianten) verwendet, die zunächst viele einzufügende Daten im Hauptspeicher aufsammeln, bevor sie blockweise die Daten in Läufen auf Externspeicher wie Festplatte/SSD auslagern, die wiederum zu größeren Läufen gemischt werden.

Für Zeichenketten ist bekannt, dass sie sehr platzsparend in Patricia Tries gespeichert werden können, sowie das Patricia Tries sehr schnell gemischt werden können (Paper).

In dieser Bachelorarbeit soll daher als interne Hauptspeicherdatenstruktur sowie für die Läufe Patricia Tries verwendet werden, um eine (speicher- und laufzeit-) vorteilhafte LSM-Bäum-Variante für Zeichenkettenschlüssel zu erhalten.

Anforderungen/Kenntnisse:
Java, Datenbank-Grundkenntnisse

Bearbeitung:
Kristin Schultz

Betreuung:

Privatdozent Dr. rer.nat. habil. Sven Groppe
Institut für Informationssysteme
Ratzeburger Allee 160 ( Gebäude 64 - 2. OG)
23562 Lübeck
Telefon: 0451 / 500 5706