Nadja Scharf

Theoretische Betrachtung von B+-Bäumen mit vereinfachter Löschoperation

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 08.03.2013
Homepage des Autors:

Kurzbeschreibung

In der von mir vorgestellten Arbeit werden B- -Bäume theoretisch untersucht. B- -Bäume sind B+ -Bäume mit dahingehend vereinfachter Löschoperation, dass unterbesetzte Knoten zugelassen sind. Dadurch können die Bäume aber entarten, das heißt sie sind nicht mehr balanciert und ihre Höhe ist nicht mehr logarithmisch in der Anzahl der gespeicherten Elemente.

Um trotzdem die von B+ -Bäumen gewohnten Schranken in Bezug auf Platzverbrauch und Höhe zu garantieren, müssen die Bäume regelmäßig neu gebaut werden. Im wesentlichen basiert diese Arbeit auf den Ergebnissen von Sen und Tarjan in "Deletion Without Rebalancing in Multiway Search Trees".