A
IFB
S
S20
01
2
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (2/33)(2/33)
Definition (B-Baum)
Ein B-Baum vom Typ (k, h), k 1, h 0, ist ein sortierter
Schlüsselbaum
T = (W,U, <, Inhalt, )
mit folgenden Eigenschaften (w W):
(i) w) = {(s) | s Inhalt(w)},
und verschiedene Knoten haben keinen Schlüssel
gemeinsam:
w' W, w' w: Inhalt(w) Inhalt(w' ) = Ø
(ii) Alle Blätter haben dieselbe Höhe h:
w Blatt H(w) = h
A
IFB
S
S20
01
3
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume7.2.3 B-Bäume (3/33)(3/33)
(iii) Die Wurzel enthält mindestens einen Schlüssel:I(w0) 1
(iv) Außer der Wurzel enthält jeder Knoten mindestens k Schlüssel:
w w0 Iwk
(v) Ein Knoten w enthält höchstens 2k Schlüssel: I(w) 2k.
(vi) Für die Anzahl der Söhne eines Knotens w gilt: (w) = 0 oder (w) = I(w) +1
A
IFB
S
S20
01
4
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (4/33)(4/33)
Aus (iii) und (vi) folgt:
Die Wurzel w0 hat niemals genau einen Sohn:
(w0)
(d.h. : Entweder (w0) = 0 oder (w0)
A
IFB
S
S20
01
5
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (5/33)(5/33)
Eigenschaften von B-Bäumen
• Aus den Definitionen folgt für B-Bäume (w W):
w w0 : (w) = 0 oder k+1 (w) 2k+1
w w0 : (w) = 0 oder 2 (w0) 2k+1
• Format von B-Baum-Knoten:
(Schlüssel in den Knoten seien sequentiell aufsteigend angeordnet)
A
IFB
S
S20
01
6
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (6/33)(6/33)
w:
p w,0 S w,1 w,1 p w,1 S w,2 w,2 p w,2 ... S w,I w,I p w,I ...
-sw,i Schlüssel, I = I(w) = #Inhalt(w)
w,i = (sw,i) (Satz-Information)
-pw,i = Zeiger auf einen Sohn des Knotens.
A
IFB
S
S20
01
11
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (11/33)(11/33)
class B_BAUM [SCHLÜSSELTYP <- COMPARABLE, SATZTYP]
feature
k : INTEGER wurzel : B_BAUM_KNOTENmake (k0 : INTEGER; key : SCHLÜSSELTYP; info SATZTYP)
is require
k0 1 and key Ø and info Ødo
k := k0!!wurzel.make (k, key, info)
ensurekey wurzel.s and info wurzel.p
end…
invariant wurzel_hat_keinen_vater: wurzel.ist_wurzel
end – – class B_BAUM
A
IFB
S
S20
01
12
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (12/33)(12/33)
Höhe eines B-Baums vom Typ (k,h) in Abhängigkeit von der Anzahl Schlüssel in S (#S):
• Obere Schranke für die Höhe h:
Alle Knoten haben eine Mindestbelegung mit 1 Schlüssel (Wurzel) bzw. k Schlüsseln:
1
k k
k k k kk1....
k1....
Höhe #Knoten #Söhne(proKnoten)
h=0 1 2
h=1 2 k1
h=2 2(k1) k1
h=3 ... ...
A
IFB
S
S20
01
13
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (13/33)(13/33)
1 + 2k + 2k(k + 1) + 2k(k + 1)2 + ... + 2k(k + 1)h -1 #S
1 + 2k (1 + (k + 1) + (k + 1)2 + ... + (k + 1)h -1) #S
1 + 2k #S
1 + 2((k + 1)h - 1) #S
(k + 1)h
h logk+1
h ist ganze Zahl, also h logk+1 für #S .
1)1(1)1(
khk
#S12
2
1#S
#S12
A
IFB
S
S20
01
14
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (14/33)(14/33)
• Untere Schranke für die Höhe h:
Alle Knoten haben eine Höchstbelegung
mit 2k Schlüsseln:
2k
2k 2k
2k 2k 2k 2k2k1....
2k1
....
Höhe #Knoten #Söhne
h=0 1 2k1
h=1 2k1 2k1
h=2 (2k1)2 2k1
h=3 ... ...
2k1....
A
IFB
S
S20
01
15
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (15/33)(15/33)
2k + 2k(2k + 1) + 2k(2k + 1)2 + ... + 2k(2k + 1)h #S
2k(1 + (2k + 1) + (2k + 1)2 + ... + (2k + 1)h ) #S
k #S
(2k + 1)h+1 #S + 1
h log2k+1(#S + 1) - 1
h ist eine ganze Zahl, also h log2k+1(#S + 1) - 1.
1)12(11)12(
khk
A
IFB
S
S20
01
16
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (16/33)(16/33)
Beispiele zur Höhe von B-Bäumen:
(1) #S = 17, k = 2 h 2
log2k+1(#S + 1) - 1 h logk+1
2
1#S
log5(18) = 1.80 (Abschätzung: 51 = 5, 52 = 25)
log3(9) = 2 1 h 2
log5(25) = 2
log3(12.5) = 2.30 1 h 2
(2) #S = 24, k = 2, 1 h 2
log2k+1(#S + 1) - 1 h logk+1
2
1#S
A
IFB
S
S20
01
17
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (17/33)(17/33)
(3) Block: 2KB
Schlüssel + Zeiger + Zeiger p ca. 15-16 B
2k 128, k 64
h = 0: 1 - 128 Schlüssel
h = 1: 129 - 16.640 Schlüssel
h = 2: 8449 - 2.146.688 Schlüssel (!)
A
IFB
S
S20
01
18
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (18/33)(18/33)
B-Baum Algorithmen
Suche den Schlüssel s im B-Baum T:
SUCHE(s, T, w)
• Vorgehensweise klar
• Suche endet mit einem Knoten w = w(s), für den gilt:
- s Inhalt(w) oder
- w ist Blatt, das s enthalten müßte.
END SUCHE
A
IFB
S
S20
01
19
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (19/33)(19/33)
Beispiel: Suche nach s=10
7 •
4 • 9 • 12 •
1 • 3 • 6 • 8 • 10 • 11 • 13 • 14 •
A
IFB
S
S20
01
20
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (20/33)(20/33)
Einfügen eines Schlüssels s in einen B-Baum T
INSERT (s, T,w ) :
– -- Schlüssel s in Baum T einfügen
– Suche(s,T,w);
– WENN s in w enthalten ist, DANN
– Fehler
– ANDERNFALLS
– INSERT-IN-NODE ((nil, s, nil), w)
– -- s ist in diesem Fall immer ein Blatt
END INSERT
A
IFB
S
S20
01
21
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (21/33)(21/33)
INSERT-IN-NODE ((l, s, r), w) :
– -- Schüssel s mit Zeiger auf linken und
-- rechten Sohn (l, r) in Knoten w
-- einfügen
–FÜGE s in w sortiert ein
–Wenn I(w) > 2k DANN -- Überlauf
– SPLIT (w)
END INSERT-IN-NODE
A
IFB
S
S20
01
22
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (22/33)(22/33)
SPLIT (w) :
– -- Spaltet den übervollen Knoten w in
– -- zwei Knoten auf
Erzeuge Knoten w‘;
in w verbleiben die ersten k Schlüssel,
w‘ wird mit den letzten k Schlüsseln von w gefüllt.
sei s’ der (k+1)-te Schlüssel
WENN Vater v von w nicht existiert
(w ist also die Wurzel),
DANN
– v := neu erzeugte Wurzel
INSERT-IN-Node ((w, s’, w’), v)
END SPLIT
A
IFB
S
S20
01
23
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume7.2.3 B-Bäume (23/33) (23/33)
Vor Split w
Nach Split:
... 8 17 61 ...
17
... 8 61 ...
v
w w´
A
IFB
S
S20
01
24
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (24/33)(24/33)
Einfügen der Schlüssel 0, 7, 22, 1, 20, 11, 3
0S=0
0 7S=7
7
0 22
S=1
S=20
7
0 1 20 22
S=22 split
Neue Wurzel
A
IFB
S
S20
01
25
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (25/33)(25/33)
7 20
0 1 22 11
7
1 20
0 22 3 11
S=11 split
S=3 split
neue Wurzel
A
IFB
S
S20
01
26
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (26/33)(26/33)
Löschen eines Schüssels s aus einem B-Baum T
DELETE (s, T) :
-- Schlüssel s aus dem Baum T löschen
SUCHE (s, T, u);
WENN s nicht in u enthalten ist,
DANN
– Fehler
ANDERNFALLS
– DELETE-FROM-NODE (s, u)
END DELETE
A
IFB
S
S20
01
27
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (27/33)(27/33)
DELETE-FROM-NODE (s, u) :
-- Schlüssel s aus Knoten u löschen
WENN u kein Blatt ist,
DANN
Ersetze s in u durch den kleinsten Schl. s0
aus dem rechten Teilbaum von s.
Sei b das Blatt, aus dem s0 entnommen wurde.
DELETE-FROM-NODE (s0, b)
ANDERNFALLS
Entferne s aus u
UNTERLAUFBEHANDLUNG (u)
END DELETE–FROM-NODE
A
IFB
S
S20
01
28
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (28/33)(28/33) UNTERLAUFBEHANDLUNG (u) :
-- Ausgleich oder Zusammenlegung mit -- einem Bruderknoten, falls u die erlaubte -- Schüsselzahl unterschreitet
WENN u nicht Wurzel von T ist UND I(u) < k (Unterlauf),
DANN
– Sei w der Bruderknoten von u, s‘ der zu u und w gehörende Schlüssel in deren Vaterknoten v und S’ die Schlüsselliste {Schlüssel aus u, s‘, Schlüssel aus w}
– WENN I(u) + I(w) 2k DANN
– Verteile die Schlüssel aus S‘ gleichmäßig auf u und w; ersetze s‘ durch den mittleren Schlüssel aus S’
– ANDERNFALLS
– Fasse S’ in einem Knoten zusammen; entferne s‘ aus v;
– UNTERLAUFBEHANDLUNG (v)END UNTERLAUFBEHANDLUNG
A
IFB
S
S20
01
29
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (29/33)(29/33)
... 1 17 61 ...
... 2 4 18 19 ...
v
u w
s
... 1 61 ...
... 2 4 17 18 19 ...
v
u
Vor Zusammenfassen:
Nach Zusammenfassen:
A
IFB
S
S20
01
30
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (30/33)(30/33)
7
1 20
0 22 3 5 11
T
S=17
7
1 20
0 22 3 5 11 17
Beispiel: Löschen in Blattern (Schlüssel17.22)DELETE (s,T)
A
IFB
S
S20
01
31
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (31/33)(31/33)
7
0 3 5 11 20
S=22,
Zwischenschritt
Ergebnis
7
1
0 3 5 11 20
Beispiel: Löschen in Blattern (Schlüssel17.22)DELETE (s,T)
A
IFB
S
S20
01
32
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (32/33)(32/33) Beispiel:Löschen aus inneren Knoten (Schlüssel 1, 20) DELETE(s,T)
7
3 20
0 22 5 11 17
T
S=1
7
1 20
0 22 3 5 11 17
A
IFB
S
S20
01
33
Phy
sisc
he D
aten
orga
nisa
tion
7.2.3 B-Bäume 7.2.3 B-Bäume (33/33)(33/33)
S=20,
Zwischenschritt
Ergebnis
7
3 22
0 5 11 20
7
3 17
0 22 5 11
Beispiel:Löschen aus inneren Knoten (Schlüssel 1, 20) DELETE(s,T)