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 .