Prof. Dr. R. Laue                                                                                                                                  WS0405
                                Datenbanken
                                Übungsblatt 3
                                Abgabe: 11.11.04  am Ende der Vorlesung

URL:         /axel/database_ws0405_blatt3.html
Dieses  Übungsblatt ist in Dreiergruppen zu bearbeiten.
Tag der Übungsgruppe bitte notieren.
Neuer Übungstermin Di 12.00 - 13.30 S76


 

Aufgabe 5 B* Baum

In der Vorlesung wurde der B-Baum als Speziallfall eines (a,b) Baums mit b=2a-1 eingeführt.

Im Fall eines B* Baums sind die eigentlichen Einträge nur in der untersten Ebene, in den inneren Knoten sind nur Vergleichswerte. Wir betrachten  nun einen Baum mit maximal 2a-1 Vergleichswerten im Knoten. Bei der Höhe des B* Baums zählen wir nur die Ebenen der inneren Knoten.

a)  Was ist die Minimalanzahl an Einträgen für einen Baum der Höhe n. (2 Punkte)
b)  Was ist die Maximalanzahl an Einträgen für die Höhe n. (2 Punkte)
c)  Führen  Sie ein Beispiel eines B* Baums mit 2 Ebenen vor, der beim Löschen um eine Ebene schrumpft. (2 Punkte)