Transcript
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.
