View
107
Download
3
Category
Preview:
Citation preview
B-Bäume
Struktur von B-Bäumen
BeispielBaum der Klasse (2,3)
. 4 . 9 .
. 1 . 2 . 3 .. 10 . 11 .
. 17 . 18 .
. 5 . 6 . 7 . 8 . . 20 . 21 . 22 . 23 .. 13 . 14 . 15 .
. 12 .
. 16 . 19 .
• in jedem Knoten stehen die Schlüssel in aufsteigender Ordnung mit k1<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 Seite2. Aufteilung der Schlüssel
. K1 . K2 . … . Kk . . Kk+2 . … . K2k+1 .Kk+1
• Mittlerer Schlüssel (Median) wird zum Vaterknoten gereicht (muss ggf. neu angelegt werden)
. K1 . K2 . … . Kk . . Kk+2 . … . K2k+1 .
. Kk+1 .
SPLIT
Beispiel
. 77 .
• Ausgangspunkt: B-Baum der Klasse PI (2,h)
77 12 48 69
. 12 . 77 . . 12 . 48 . 77 .
. 12 . 48 . 69 . 77 .
33
. 12 . 48 . 69 . 77.
. 12 . 33 . 48 . 69 . 77.
Überlauf!Da 2k+1 Elemente
. 12 . 33 . 48 . 69 . 77 .
. 48 .
. 12 . 33 . . 69 . 77 .
89
. 48 .
. 12 . 33 . . 69 . 77 . 89 .
. 48 .
. 12 . 33 . . 69 . 77 . 89 . 97 .
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 . . 69 . 77 . 83 . . 91 . 97 .
Überlauf!Da 2k+1 Elemente
. 33 . 48 . 89 .
. 2 . 12 . . 69 . 77 . 83 . . 91 . 97 .. 37 . 45 .
. 33 . 48 . 89 .
. 2 . 5 . 12 . . 69 . 77 . 83 . . 91 . 97 .. 37 . 45 .
5
. 33 . 48 . 89 .
. 2 . 5 . 12 . . 57 . 69 . 77 . 83 . . 91 . 97 .. 37 . 45 .
57
. 33 . 48 . 89 .
. 2 . 5 . 12 . . 57 . 69 . 77 . 83 . . 90 . 91 . 97 .. 37 . 45 .
90
. 33 . 48 . 89 .
. 2 . 5 . 12 . . 57 . 69 . 77 . 83 . . 90 . 91 . 95 . 97 .. 37 . 45 .
95
. 33 . 48 . 89 .
. 2 . 5 . 12 . . 57 . 69 . 77 . 83 . . 90 . 91 . 95 . 97 . 99 .. 37 . 45 .
99
Überlauf!Da 2k+1 Elemente
. 33 . 48 . 89 . 95 .
. 2 . 5 . 12 . . 57 . 69 . 77 . 83 . . 90 . 91 .. 37 . 45 . . 97 . 99 .
. 33 . 48 . 89 . 95 .
. 2 . 5 . 12 .
. 50 . 57 . 69 . 77 . 83 .
. 90 . 91 .. 37 . 45 . . 97 . 99 .
50
Überlauf!Da 2k+1 Elemente
. 33 . 48 . 69 . 89 . 95 .
. 2 . 5 . 12 .
. 50 . 57 .
. 90 . 91 .. 37 . 45 . . 97 . 99 .
Überlauf!Da 2k+1 Elemente
. 77 . 83 .
. . .
. 33 . 48 .
. 2 . 5 . 12 .
. 50 . 57 .
. 90 . 91 .. 37 . 45 . . 97 . 99 .
. 77 . 83 .
. 69 .
. 89 . 95 .
B*-Bäume
Struktur von B*-Bäumen
• M enthält eine Kennung des Seitentyps sowie die Zahl der aktuellen Einträge
BeispielB*-Baum der Klasse (3,2,3)
. 2 . 5 . 9 .
. 1 . 2 .
. 10 . 11 . 12 .. 6 . 7 . 8 .
. 12 .
. 15 . 18 . 20 .
. 3 . 4 . 5 . . . .
Indexteil:B-Baum von Schlüsseln
sortierte, sequentielleDatei 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
… . Kk* . K2k* . …
. K1 D1 . … . Kk* Dk* . . Kk+1* Dk*+1 . … . K D . … . K2k* D2k* .
. K1 D1 . … . Kk* Dk* . . Kk+1* Dk*+1 . … . K2k* D2k* .
… . K2k* . …
SPLIT
Beispiel. 12 . 28 . 46 . 67 .
. 1 . 5 . 9 . 12 . . 33 . 37 . 41 . 46 . . 53 . 59 . 67 . .. 15 . 19 . 28 . . . 71 . 83 .99 . .
. 12 . 28 . 46 . 67 .
. 1 . 5 . 9 . 12 . . 33 . 37 . 41 . 45 . 46 . . 53 . 59 . 67 . .. 15 . 19 . 28 . . . 71 . 83 .99 . .
45
Überlauf!Da 2k*+1 Elemente
. 12 . 28 . 41 . 46 . 67 .
. 1 . 5 . 9 . 12 .
. 33 . 37 . 41 . .
. 53 . 59 . 67 . .. 15 . 19 . 28 . . . 71 . 83 .99 . .
. 45 . 46 . . . .
. 12 . 28 .
. 1 . 5 . 9 . 12 .
. 33 . 37 . 41 . .
. 53 . 59 . 67 . .. 15 . 19 . 28 . . . 71 . 83 .99 . .
. 45 . 46 . . . .
. 41 .
. 46 . 67 .
Recommended