Übungsblatt B*-Baum

Fachbereich 12 – Institut für Informatik und Mathematik
Professur für Datenbanken und Informationssysteme
Grundlagen der Datenbanksysteme 2
WS 2014/2015
Übungsblatt B*-Baum
Müsterlösung (keine Garantie auf Richtigkeit!)
Aufgabe 1:
Gegeben sei ein leerer B*-Baum mit
3,
∗
2 und den folgenden Daten:
Daten
ID
Wert
1
A
3
B
6
C
4
D
7
C
5
F
2
A
Fügen Sie die Daten aus der Tabelle in den leeren B*-Baum entsprechend der
Reihenfolge der Tabelle (von oben nach unten) ein. Zeichnen Sie mindestens jeden
Zwischenschritt, bei dem ein neuer Block für den Baum benötigt wird und den fertigen
Baum.
Musterlösung:
Schritt 1 (Datensätze mit den ID’s 1, 3 und 6 einfügen)
Schritt 2 (Datensätze mit den ID’s 4 und 7 einfügen)
Schritt 3 (Datensätze mit den ID’s 5 und 2 einfügen)
Aufgabe 2:
Gegeben sei folgende Ausgangsbaum B*-Baum mit
∗
2.
Ausgangsbaum:
25, ..
Führen Sie folgende Operationen jeweils auf dem Ausgangsbaum aus und zeichnen Sie
resultierenden Baum erneut auf.
a) Löschen der 10
12
20
12,… 15,…
20,… 25,…
b) Löschen der 7
X
25, ..
Hier kann kein DS von einem Geschwister genommen werden, daher „Zusammenlegen“ der
beiden Blöcke zu einem mit den Datensätzen 1, 3 und 8. Damit hat der innere Knoten jedoch nur
noch einen Verweis (kleiner als 2!). Dieser kann sich aber einen Verweis von seinem
Geschwister rechts nehmen!
15
10
1.. 3.. 8..
–
10.. 12..
–
27
–
15.. 20.. 25..
–
27.. 30.. –
c) Einfügen von 18
18 kommt in den Block mit 15, 20 und 25. Dieser wäre dann Übervoll!
In diesem Fall wird laut Einfügeverfahren der Vorlesungsfolien immer ein neuer Block erzeugt
und die Werte gleichmäßig verteilt.
(Bem.: Natürlich sind auch hier andere Verfahren vorstellbar! Wie bei Löschen könnte geschaut
werden, ob die Geschwister noch Platz haben.)
Aufgabe 3:
a) Bestimmen Sie die Werte k und k* für einen B*-Baum bei gegebener Seitengröße
p=4096 Bytes, Schlüsselgröße s=8 Bytes, Satzgröße r=500 Bytes und
Verweisgröße v=8 Bytes. Sonstiger Verwaltungsoverhead inkl. Header kann
vernachlässigt werden.
Max. Anzahl von DS pro Blatt sind:
8
Damit lässt sich k* berechnen als: 2k*-1 ≤ 8 => 2k* ≤ 9 => k* ≤
4
Man sollte immer den größten möglichen Werte für k* (und k) wählen, daher k*=4
Der erste Index-Verweis benötigt keinen Schlüssel, also nur den Pointer von 8 Byte. Alle
anderen Index-Verweise bestehen aus Schlüssel plus Pointer, also 8 Byte + 8 Byte=16 Byte.
Max. Anzahl von DS (Index-Verweise) pro Block sind:
1 256
Damit lässt sich k berechne als: 2k-1 ≤ 256 => 2k ≤ 257 => k ≤
Also k = 128
128
b) Wie viele Ebenen benötigt man mindestens mit diesen Parametern um 5000,
500000 und 50000000 Datensätze zu speichern?
Da nach „mindestens“ gefragt ist, geht man vom optimalen Fall aus, dass die Blätter mit 2k*-1
und die Knoten mit 2k-1 gefüllt sind (evt. bis auf einen je Ebene).
Bei 5000:
2k*-1 => 7 DS pro Blatt =>
715 Blätter werden mind. benötigt.
2k-1 => 255 Index-Verweise pro Blatt =>
= 3 Knoten in der Ebene über den Blättern
Da 3 ≤ 255 ist, wird für die Ebene da drüber nur ein Knoten benötigt => die Wurzel
Antwort: Der Baum hat für 5000 Datensätze mindestens 3 Ebenen.
Bei 500000:
2k*-1 => 7 DS pro Blatt =>
= 71429 Blätter werden mind. benötigt.
2k-1 => 255 Index-Verweise pro Blatt =>
= 281 Knoten in der Ebene über den Blättern
In der Ebene über diesen
=2
Da 2 ≤ 255 ist, wird für die Ebene da drüber nur ein Knoten benötigt => die Wurzel
Antwort: Der Baum hat für 500000 Datensätze mindestens 4 Ebenen.
Bei 50000000:
2k*-1 => 7 DS pro Blatt =>
2k-1 => 255 Verweise pro Blatt =>
= 7142858 Blätter werden mind. benötigt.
= 28012 Knoten in der Ebene über den Blättern
In der Ebene über diesen
= 110
Da 110 ≤ 255 ist, wird für die Ebene da drüber nur ein Knoten benötigt => die Wurzel
Antwort: Der Baum hat für 50000000 Datensätze ebenfalls mindestens 4 Ebenen.

Download Report