B-Bäume
Struktur von B-Bäumen
Beispiel
Baum der Klasse (2,3)
. 12 .
.4.9.
.1.2.3.
.5.6.7.8.
. 16 . 19 .
. 10 . 11 .
. 17 . 18 .
. 13 . 14 . 15 .
. 20 . 21 . 22 . 23 .
• in jedem Knoten stehen die Schlüssel in aufsteigender Ordnung mit k 1<K2<…<Kb.
• jeder Schlüssel hat eine Doppelrolle als Identifikatro eines Datensatzes und als Wegweiser im Baum.
• Die Klassen (k,h) sind nicht alle disjunkt. Beispeislweise ist ein maximaler
Baum aus (2,3) ebenso in (3.3) und (4,3):
Einfügen in B-Bäume
. K1 . K2 . … . K2k .
K2k+1
1. Anforderung einer neuen Seite
2. Aufteilung der Schlüssel
. K1 . K2 . … . Kk .
Kk+1
. Kk+2 . … . K2k+1 .
• Mittlerer Schlüssel (Median) wird zum Vaterknoten gereicht
(muss ggf. neu angelegt werden)
SPLIT
. Kk+1 .
. K1 . K2 . … . Kk .
. Kk+2 . … . K2k+1 .
Beispiel
• Ausgangspunkt: B-Baum der Klasse PI (2,h)
77 12 48 69
. 77 .
. 12 . 77 .
. 12 . 48 . 77 .
. 12 . 48 . 69 . 77 .
. 12 . 48 . 69 . 77.
33
. 12 . 33 . 48 . 69 . 77 .
. 12 . 33 . 48 . 69 . 77.
. 48 .
Überlauf!
Da 2k+1 Elemente
. 12 . 33 .
. 69 . 77 .
89
. 48 .
. 12 . 33 .
. 69 . 77 . 89 .
97
. 48 .
. 12 . 33 .
. 69 . 77 . 89 . 97 .
91
91 37 45 83
. 48 .
. 12 . 33 .
. 69 . 77 . 89 . 91 . 97 .
Überlauf!
Da 2k+1 Elemente
. 48 . 89 .
. 12 . 33 .
. 69 . 77 .
. 91 . 97 .
37
. 48 . 89 .
. 12 . 33 . 37 .
. 69 . 77 .
. 91 . 97 .
45
. 48 . 89 .
. 12 . 33 . 37 . 45 .
. 69 . 77 .
. 91 . 97 .
83
. 48 . 89 .
. 12 . 33 . 37 . 45 .
. 69 . 77 . 83 .
. 91 . 97 .
2
. 48 . 89 .
. 2 . 12 . 33 . 37 . 45 .
Überlauf!
Da 2k+1 Elemente
. 69 . 77 . 83 .
. 91 . 97 .
. 33 . 48 . 89 .
. 2 . 12 .
. 37 . 45 .
. 69 . 77 . 83 .
. 91 . 97 .
5
. 33 . 48 . 89 .
. 2 . 5 . 12 .
. 37 . 45 .
. 69 . 77 . 83 .
. 91 . 97 .
57
. 33 . 48 . 89 .
. 2 . 5 . 12 .
. 37 . 45 .
. 57 . 69 . 77 . 83 .
. 91 . 97 .
90
. 33 . 48 . 89 .
. 2 . 5 . 12 .
. 37 . 45 .
. 57 . 69 . 77 . 83 .
. 90 . 91 . 97 .
95
. 33 . 48 . 89 .
. 2 . 5 . 12 .
. 37 . 45 .
. 57 . 69 . 77 . 83 .
. 90 . 91 . 95 . 97 .
99
. 33 . 48 . 89 .
. 2 . 5 . 12 .
. 37 . 45 .
. 57 . 69 . 77 . 83 .
. 90 . 91 . 95 . 97 . 99 .
Überlauf!
Da 2k+1 Elemente
. 33 . 48 . 89 . 95 .
. 2 . 5 . 12 .
. 37 . 45 .
. 57 . 69 . 77 . 83 .
. 90 . 91 .
. 97 . 99 .
50
. 33 . 48 . 89 . 95 .
. 50 . 57 . 69 . 77 . 83 .
. 2 . 5 . 12 .
. 37 . 45 .
Überlauf!
. 90 . 91 .
Da 2k+1 Elemente
. 97 . 99 .
...
. 33 . 48 . 69 . 89 . 95 .
. 50 . 57 .
. 2 . 5 . 12 .
. 37 . 45 .
Überlauf!
Da 2k+1 Elemente
. 77 . 83 .
. 90 . 91 .
. 97 . 99 .
. 69 .
. 33 . 48 .
. 89 . 95 .
. 50 . 57 .
. 2 . 5 . 12 .
. 37 . 45 .
. 77 . 83 .
. 90 . 91 .
. 97 . 99 .
B*-Bäume
Struktur von B*-Bäumen
• M enthält eine Kennung des Seitentyps sowie die Zahl der aktuellen Einträge
Beispiel
B*-Baum der Klasse (3,2,3)
. 12 .
. 15 . 18 . 20 .
.2.5.9.
.1.2.
.3.4.5.
...
.6.7.8.
. 10 . 11 . 12 .
Indexteil:
B-Baum von Schlüsseln
sortierte, sequentielle
Datei der Blätter
Einfügen in B*-Bäume
• sehr ähnlich dem Einfügen in einen B-Baum
• innere Knoten: analog zu zum B-Baum
• Blattknoten: höchsten Schlüssel einer Seite müssen in
Vaterknoten kopiert werden
… . K2k* . …
. K1 D1 . … . Kk* Dk* . . Kk+1* Dk*+1 . … . K2k* D2k* .
SPLIT
… . Kk* . K2k* . …
. K1 D1 . … . Kk* Dk* .
. Kk+1* Dk*+1 . … . K D . … . K2k* D2k* .
Beispiel
. 12 . 28 . 46 . 67 .
. 1 . 5 . 9 . 12 .
. 15 . 19 . 28 . .
. 33 . 37 . 41 . 46 .
. 53 . 59 . 67 . .
. 71 . 83 .99 . .
45
. 12 . 28 . 46 . 67 .
. 1 . 5 . 9 . 12 .
. 15 . 19 . 28 . .
. 33 . 37 . 41 . 45 . 46 .
Überlauf!
Da 2k*+1 Elemente
. 53 . 59 . 67 . .
. 71 . 83 .99 . .
. 12 . 28 . 41 . 46 . 67 .
. 1 . 5 . 9 . 12 .
. 15 . 19 . 28 . .
. 33 . 37 . 41 . .
. 53 . 59 . 67 . .
. 45 . 46 . . . .
. 71 . 83 .99 . .
. 41 .
. 12 . 28 .
. 1 . 5 . 9 . 12 .
. 46 . 67 .
. 15 . 19 . 28 . .
. 33 . 37 . 41 . .
. 53 . 59 . 67 . .
. 45 . 46 . . . .
. 71 . 83 .99 . .

ppt - Angelfire