B*-Bäume 1
Grundlagen der Datenbanksysteme II
B*-BÄUME
Beobachtung:
• Ein Index ist seinerseits wieder nichts anderes als eine Datei
mit unpinned Records.
• Es gibt keinen Grund, warum man nicht einen Index über
einem Index haben sollte, und so weiter, bis der letzte Index
in einen einzigen Block paßt.
• Eine solche Hierarchie von Indizes (Multi-Level-Index) kann
weitaus effektiver sein als ein einziger Index.
• Eine Multi-Level-Index Hierarchie kann als ein Baum
betrachtet werden.
• Beispiel: Jeder Index-Block kann fünf Einträge enthalten.
B*-Bäume 2
Grundlagen der Datenbanksysteme II
First level index
Second level index
Third level index
File
2 21
2
2 8 14
21
2 ... 7 ... 8 ... 11 ... 14 ... 19 ... 21 ... 22 ...
B*-Bäume 3
Grundlagen der Datenbanksysteme II
Anforderungen an einen Multi-Level-Index:
• Baum von Indizes mit einer unspezifizierten Anzahl von
Ebenen.
• Balancierter Baum:
Jeder Pfad von der Wurzel ( erste Index-Ebene ) zu
einem Blatt hat die gleiche Länge.
• Die Sätze der Hauptdatei sind unpinned.
B*-Baum
B*-Bäume 4
Grundlagen der Datenbanksysteme II
Definition:
Ein B*-Baum ist ein Baum, dessen Knoten aus Blöcken
bestehen, mit den folgenden Eigenschaften:
• Jeder Blattknoten (außer der Wurzel) enthält zwischen k* und
2k*-1 sortierte Datensätze.
Jeder Block ist also mindestens zur Hälfte gefüllt.
• Jeder Nichtblattknoten mit Ausnahme der Wurzel enthält
zwischen k und 2k-1 Indexeinträge.
Der erste Eintrag jedes Knotens hat keinen zugeordneten
Schlüssel (dies spart Platz).
• Die Wurzel enthält maximal 2k-1 Indexeinträge oder maximal
2k*-1 Datensätze.
• Alle Blätter liegen auf gleicher Höhe.
B*-Bäume 5
Grundlagen der Datenbanksysteme II
Eine Variante des B*-Baum ist es, die Blöcke der Hauptdatei zu
den Blättern des Baumes zu machen.
Dieser sehr einfache Ansatz ist allerdings nicht der Effizienteste
(insbesondere im Platzverbrauch).
Ein besserer Ansatz wird beim Betrachten von B*-Bäumen
mit pinned Records aufgezeigt.
B*-Bäume 6
Grundlagen der Datenbanksysteme II
Lookup
Gesucht wird ein Satz mit dem Schlüssel v.
Die Suche beginnt an der Wurzel des B*-Baumes.
Angenommen die Suche ist am Knoten B angekommen, dann
ist B entweder
• Ein Blatt (dies kann durch Zählen der durchlaufenen Ebenen
feststellen), oder
• Ein Knoten.
Wenn B ein Blatt ist, muß lediglich der Block nach dem Satz
durchsucht werden.
Ist B hingegen ein Knoten, dann ist B ein Index-Block.
B*-Bäume 7
Grundlagen der Datenbanksysteme II
Ist B ein Index-Block, wird festgestellt, welcher Indexeintrag den
Wert v überdeckt.
Anmerkung: Der erste Satz von B hat keinen Schlüssel, er
überdeckt alle Werte die kleiner sind als der Schlüsselwert des
zweiten Satzes.
25 144
Erster Satz(ohne Schlüssel)
Alle Wertekleiner als 25
Erster Satz(ohne Schlüssel)
Alle Werte xmit x ≥ 144
Alle Werte xmit 25 ≤ x < 144
Der Satz, der v überdeckt, enthält einen Zeiger zu einem
weiteren Block B’ dieser Block folgt dem Block B auf dem Pfad
zu dem gesuchten Satz.
Diese Schritte werde wiederholt bis ein Blatt erreicht wird.
B*-Bäume 8
Grundlagen der Datenbanksysteme II
Modifikation
• Wenn der Schlüsselwert geändert wird,
Löschen und Einfügen.
• Wenn der Schlüsselwert unverändert bleibt,
Lookup und Rewrite.
B*-Bäume 9
Grundlagen der Datenbanksysteme II
Einfügen
Es wird ein Satz mit dem Schlüssel v eingefügt.
• Lookup (v)
Block B.
• Wenn in B weniger als 2k*-1 Sätze sind, wird der neue
Satz an der richtigen Stelle der Sortierreihenfolge
eingefügt (unpinned Records).
• Der neue Satz kann niemals der erste in Block B sein,
außer wenn B der äußerst linke Block ist.
B*-Bäume 10
Grundlagen der Datenbanksysteme II
Hauptdatei
Daraus folgt, daß es unter keinen Umständen nötig wird, den
Schlüsselwert eines Vorfahren von B zu ändern, denn der erste
Satz jedes Indexblocks hat keinen Indexwert.
B*-Bäume 11
Grundlagen der Datenbanksysteme II
• Wenn aber in bereits 2k*-1 Sätze in Block B vorhanden sind
(der Block ist also voll), dann
• erzeuge einen neuen Block B’,
• teile die Sätze von B und den eingefügten Satz auf die
zwei Blöcke auf. Jeder Block ist danach mit k* Sätzen
gefüllt.
2k*-1 Sätze +1 Satz = 2k*
k* Sätze k* Sätze
B
B B’
B*-Bäume 12
Grundlagen der Datenbanksysteme II
Jetzt muß noch der Index auf den neuen Stand gebracht
werden:
P sei der Vaterknoten von B. Dann wird in den Block P ein Satz
für den neuen Block B’ eingefügt, dies geschieht mit dem eben
beschriebenen Verfahren nur mit dem Wert k statt k*.
P
B
P
B B’
B*-Bäume 13
Grundlagen der Datenbanksysteme II
Falls P schon mit 2k-1 Sätzen gefüllt war:
P
B B’
P’
Q
k Sätze
B*-Bäume 14
Grundlagen der Datenbanksysteme II
Diese Prozeß kann bis in die Wurzel propagiert werden, wobei
aber nur Vorfahren von B betroffen sind.
Falls der Prozeß die Wurzel erreicht, dann
• teile die Wurzel,
• Erzeuge eine neue Wurzel mit zwei Kindern.
v
Die neueWurzel
Die alte Wurzel
Anmerkung:
Dies ist die einzige Situation in der ein Index-Block weniger als
k Sätze haben kann.
B*-Bäume 15
Grundlagen der Datenbanksysteme II
Löschen
Der Satz mit dem Schlüssel v soll gelöscht werden.
• Lookup v
Block B.
• Lösche den Satz in B.
B*-Bäume 16
Grundlagen der Datenbanksysteme II
1. Falls nach dem Löschen in B k* oder mehr Sätze übrig sind,
ist der Vorgang beendet, es sei denn:
• Der gelöschte Satz war der erste Satz in B, dann muß
im Vater P von B der Schlüsselwert für B geändert
werden.
P
B
25
25 36 42
P
B
36
36 42
B*-Bäume 17
Grundlagen der Datenbanksysteme II
• Falls B das erste Kind von P ist, hat P keinen Schlüssel
für B. Dann muß ein Vorfahre A von B gefunden werden
für den gilt, daß er nicht das erste Kind seines
Vaterknotens A’ ist.
Dann wird der neue (kleinste) Schlüssel von B in den
Satz von A’ eingetragen, der auf A verweist.
P = A
B
25 36 42
A’25
36
B*-Bäume 18
Grundlagen der Datenbanksysteme II
2. Falls nach dem Löschen in B nur noch k*-1 Sätze übrig
sind, dann:
• Betrachte einen Block B’ der den selben Vaterknoten
P hat und der unmittelbar links oder rechts von B liegt.
P
B B’B’
B*-Bäume 19
Grundlagen der Datenbanksysteme II
• Falls B’ mehr als k* Sätze hat, verteile die Sätze von B
und B’ gleichmäßig auf beide Blöcke.
Modifiziere den Schlüsselwert von B und/oder B’ und,
falls nötig, propagiere die Änderungen zu den Vorfahren
von B.
B B’
k*-1 > k*
B B’
k*1 k*2
k*1 ≥ k* k*2 ≥ k*
B*-Bäume 20
Grundlagen der Datenbanksysteme II
• Falls B’ nur k* Sätze hat, dann vereinige B mit B’ zu
einem Block mit k*-1 + k* = 2k*-1 Sätzen.
Lösche den Eintrag des rechten der beiden Blöcke
(rekursiver Aufruf der Löschprozedur).
B B’
k*-1 ≤ k*
P
B
≤ 2k*-1
P
B*-Bäume 21
Grundlagen der Datenbanksysteme II
• Falls nach Anwendung dieses Verfahrens die Wurzel nur
noch einen Zeiger enthält, kann die Wurzel wegfallen
und das einzige Kind der Wurzel wird zur neuen Wurzel.
≤ 2k-1
Wurzel
B’≤ 2k-1
B’
Neue Wurzel
Anmerkung:
Dies ist der einzige Fall in dem die Anzahl der Ebenen des
Baumes kleiner wird.
B*-Bäume 22
Grundlagen der Datenbanksysteme II
Beispiel:
Auf dem folgenden, bereits vorhandenen B*-Baum sollen zwei
Operationen durchgeführt werden:
1. Einfügen eines Satzes mit Schlüsselwert 32
2. Löschen des Satzes mit dem Schlüsselwert 64
B1 25 144
B4 196 – B3 64 100 B2 9 –
1 4 – 9 16 – 25 36 49 64 81 – 100 121 – 144 169 – 196 225 256
B5 B6 B7 B8 B9 B10 B11
First record, key value omitted Second record Third record
B*-Bäume 23
Grundlagen der Datenbanksysteme II
1. Einfügen von 32
• Zuerst wird ein Pfad von der Wurzel zu dem Block, in
den der Wert 32 gehört, gesucht.
• B1 : Der Wert 25 überdeckt 32. Wir gehen also weiter zu
Block B3.
25 144
B3 B4B2
B1
• B3 : 32 ist kleiner als der Schlüsselwert 64 der zweiten
Satzes von B3, daher wird em Zeiger des ersten Satzes
zu Block B7 gefolgt.
64 100
B8 B9B7
B3
B*-Bäume 24
Grundlagen der Datenbanksysteme II
• B7 : Der Block B7 ist ein Blatt und daher ein Block der
Hauptdatei. Der Wert 32 gehört hier zwischen die Werte
25 und 36.
25 49
B7
36
32
• Der Block B7 ist allerdings bereits voll, daher wird ein
neuer Block B12 angelegt. Die Werte 25 und 32 kommen
dann in Block B7 und die Werte 36 und 49 in Block B12.
25
B7
32 36 49
B12
B*-Bäume 25
Grundlagen der Datenbanksysteme II
• Nun muß ein Satz mit dem ersten Schlüssel von Block
B12 in B3 (der Vorfahre von B7) eingefügt werden.
Der Block B3 ist aber auch schon voll, daher wird ein
weiterer Block (B13) angelegt. Die Sätze mit den Zeigern
auf B7 und B12 kommen in Block B3 und die Sätze mit
Zeigern auf B8 und B9 kommen in Block B13.
36
B12B7
B3
100
B9B8
B13
• Jetzt muß ein Satz mit dem Schlüsselwert 64 und einem
Zeiger auf B13 in B1 eingefügt werden. Leider bekommt
B1 dadurch 4 Sätze. Deshalb wird ein neuer Block B14
angelegt. Die Sätze mit Zeigern auf B2 und B3 kommen
in Block B1 und die Sätze mit Zeigern auf B13 und B4
kommen in Block B14.
25
B3B2
B1
144
B4B13
B14
B*-Bäume 26
Grundlagen der Datenbanksysteme II
• Da B1 die Wurzel war und gesplittet wurde, wird jetzt ein
neuer Block B15 erzeugt, der zur Wurzel wird und Zeiger
auf B1 und B14 hat.
Der endgültige Baum sieht dann wie folgt aus:
1 4 – 9 16 – 25 32 – 36 49 – 64 81 – 100 121 – 144 169 – 196 225 256
B5 B6 B7 B12 B8 B9 B10 B11
B15 64 –
B13 100 – B3 36 – B2 9 –
B14 144 – B1 25 –
B4 196 –
B*-Bäume 27
Grundlagen der Datenbanksysteme II
2. Löschen von 64.
• Durch suchen (lookup) findet man heraus, daß der Pfad
zu dem Block der den Wert 64 enthält wie folgt ist:
B15, B14, B13, B8
• Der Wert 64 wird aus dem Block B8 gelöscht.
64
B8
81 81
B8
• Da es der erste Satz in dem Block war, muß auch der
neue Schlüsselwert (81) in der Hierarchie nach oben
propagiert werden.
• Da B8 das links-außen liegende Kind von B13 ist, wird B13
nicht geändert, das gleiche gilt für B14 da für B14 der
Block B13 das links-außen liegende Kind ist.
B*-Bäume 28
Grundlagen der Datenbanksysteme II
• B14 ist allerdings nicht links-außen in B15 verankert,
daher muß ein Schlüsselwert von B15 geändert werden.
64
B14B1
B15
81
B14B1
B15
• Durch das löschen von 64 in Block B8 hat dieser nur
noch einen einzigen Satz. Dies widerspricht der
Vorschrift, daß jeder Block mindestens k, also in diesem
Fall 2, Sätze haben muß.
Da B8 keinen linken Geschwister hat, wird sein rechter
Geschwister B9 überprüft. B9 hat zwei Sätze, B8 und B9
können also zusammengefaßt werden.
81
B8
100
B9
121 81
B8
100 121
B*-Bäume 29
Grundlagen der Datenbanksysteme II
• B13 hat jetzt nur noch das eine Kind B8. B13 wird deshalb
mit B4 zusammengefaßt:
B8
B13
196
B11B10
B4
144
B10 B8
B13
196
B11
• Jetzt hat auch B14 nur noch ein Kind und wird mit B1
zusammengefaßt:
25
B2
B1
B3 B13
B14
25
B3B2
B14
81
B13
B*-Bäume 30
Grundlagen der Datenbanksysteme II
• Block B15 hat jetzt nur noch ein Kind und, da er die
Wurzel ist, wird er gelöscht. B14 wird zur neuen Wurzel:
B14 25 81
B13 144 196 B3 36 – B2 9 –
1 4 – 9 16 – 25 32 – 36 49 – 81 100 121 144 169 – 196 225 256
B5 B6 B7 B12 B8 B10 B11
B*-Bäume 31
Grundlagen der Datenbanksysteme II
Leerer B*-Baum:
k = k* = 2
Einfügen der Werte
2, 5, 8, 9, 3, 11, 50
⇓
Aufbauen des B*-Baumes.
Ändern des Schlüsselwertes 50 nach 7.
50 7
B*-Bäume 32
Grundlagen der Datenbanksysteme II
LAUFZEITANALYSE FÜR OPERATIONEN
AUF B*-BÄUMEN
Annahme:
gegeben ist eine Datei mit n Sätzen, die in einem B*-Baum mit
den Parametern k und k * organisiert ist.
• Der Baum wird nicht mehr als
nk * Blätter haben.
• Der Baum wird nicht mehr als
nk k⋅ * Eltern von Blättern haben.
• Des weiteren kann er nicht mehr als
nk k2 ⋅ *
Eltern von Eltern von Blättern haben.
• und so weiter ...
B*-Bäume 33
Grundlagen der Datenbanksysteme II
Wenn ein Pfad von der Wurzel zu den Blätter i Knoten hat,
dann gilt:
n k ki≥ ⋅−1 *
Es folgt hieraus:
i n kk≤ +1 log ( *)
Für eine Datei mit n Sätzen in einem B*-Baum mit den
Parametern k und k* folgt daher:
Für einen lookup benötigt man
i n kk≤ +1 log ( *) Zugriffe,
für alle anderen Operationen
2 + log ( *)k n k Zugriffe.
B*-Bäume 34
Grundlagen der Datenbanksysteme II
Beispiel:
nkk
==
=
1000 0005
50
. .*
⇓
( )2 200 000 650+ ≤log .
Für eine hashed Datei wären es ≅ 3 Zugriffe gewesen.
Der B*-Baum ist also besser als eine Ein-Level Index
Struktur.
Der Vorteil gegenüber Hashing ist, daß die
Datei immer sortiert vorliegt.
B*-Bäume 35
Grundlagen der Datenbanksysteme II
DATEIEN MIT EINEM
DENSE INDEX
Wenn die Hauptdatei nicht sortiert vorliegen muß, dann
• kann man teilgefüllte Blöcke in der Hauptdatei
vermeiden.
• kann man eine einfache Einfüge-Strategie anwenden:
immer am Ende einfügen.
Für die dann beim Löschen auftretenden „Löcher“ in der
Hauptdatei kann man zwei Strategien wählen:
• Man ignoriert die Tatsache und lebt mit den Löchern,
oder
B*-Bäume 36
Grundlagen der Datenbanksysteme II
• Man hält eine separate Datei mit Zeigern auf die Blöcke
mit leeren Subblöcken, oder sogar direkt auf die leeren
Subblöcke:
Dadurch werden aber keine Blockzugriffe eingespart, es
wird nur der freie Platz besser verwaltet.
B*-Bäume 37
Grundlagen der Datenbanksysteme II
Wenn die Hauptdatei unsortiert vorliegt,
• wie findet man einen Satz?
Dense Index
Ein Dense Index ist eine Datei mit einem Satz der Form
(v,p) für jeden Schlüsselwert v in der Hauptdatei.
Ein Dense Index kann bei den bisher besprochenen
Verfahren anstelle der Hauptdatei verwendet werden.
Der Dense Index kann also als
• Hash-Datei
• Index
• B*-Baum
organisiert sein.
B*-Bäume 38
Grundlagen der Datenbanksysteme II
Suchen (Lookup)
V1 V2 V3 V4 V5V0
V1 V3 V2 V5V4V0
• Bestimmen des Blockes der Hauptdatei.
• Lesen des Blocks.
• evtl. Ändern/Zurückschreiben des Blocks.
Modifikation
B*-Bäume 39
Grundlagen der Datenbanksysteme II
Löschen
• Löschen des Blockeintrages.
• Zurückschreiben des Blocks.
• Löschen des Indexeintrags.
B*-Bäume 40
Grundlagen der Datenbanksysteme II
Einfügen
• Einfügen eines Satzes am Ende der Hauptdatei (evtl. In
einem neuen Block).
• Einfügen eines entsprechenden Eintrags im Index.
Anmerkung: Durch die zusätzlichen Zugriffe auf die
Hauptdatei werden immer 2 Zugriffe mehr benötigt als
wenn die Organisation des Dense Index direkt auf die
Hauptdatei angewendet würde.
B*-Bäume 41
Grundlagen der Datenbanksysteme II
Wozu Dense Index?
Wenn jede Operation über den Dense Index grundsätzlich 2
Zugriffe mehr benötigt als ohne Dense Index, muß der Einsatz
eines Dense Index begründet werden.
DenseIndex
Haupt-datei
B*-Bäume 42
Grundlagen der Datenbanksysteme II
Gründe für einen Dense Index:
1. Die Sätze in der Hauptdatei sind evtl. pinned, Die Sätze
im Dense Index hingegen nicht.
Es kann eine einfachere oder effizientere
Organisationsform für den Dense Index gewählt
werden.
B*-Bäume 43
Grundlagen der Datenbanksysteme II
Hauptdatei
pinned Recordsunsortiert
Dense Index
unpinned Recordssortiert
B*-Bäume 44
Grundlagen der Datenbanksysteme II
B*-Baum
B*-Bäume 45
Grundlagen der Datenbanksysteme II
Hash
B*-Bäume 46
Grundlagen der Datenbanksysteme II
SparseIndex
B*-Bäume 47
Grundlagen der Datenbanksysteme II
2. Falls die Sätze der Hauptdatei sehr groß sind, wird die
Anzahl der Blocks, die für einen Dense Index benötigt
werden, viel kleiner sein, als wenn ein Sparse Index oder ein
B*-Baum auf der Hauptdatei anwendet würde.
Gleiches gilt für einen Zugriff per Hashing, auch hier kann die
durchschnittliche Anzahl der Blocks pro Bucket geringer
ausfallen, wenn über den Dense Index statt über der
Hauptdatei gehashed wird.
n Blocks B*-Baum oderSparse Indexüber derHauptdatei
m Blocks
n ≤ m
B*-Bäume 48
Grundlagen der Datenbanksysteme II
B*-Baum vs. Dense Index mit B*-Baum
Hauptdatei Dense Index
Hauptdatei
+2: Block lesen;Block schreiben.
Beispiel:
Hauptdatei mit
n = 1.000.000 Sätzen
B*-Baum mit
k* = 5
k = 50
B*-Bäume 49
Grundlagen der Datenbanksysteme II
B*-Baum über der Hauptdatei:
( )22 200 000 650
+ =+ ≤
log ( / *)log .
k n k
B*-Baum über Dense Index:
• Größe der Dense Index Record = Größe der Knoten des B*-
Baumes. k* = 50
2
2 1000 00050
550
+ =
+ ⎛⎝⎜
⎞⎠⎟
≤
log ( / *)
log . .k n k
Es müssen hierzu noch die 2 Zusätzlichen Zugriffe auf die
Hauptdatei hinzugezählt werden:
2+5 = 7
Es werden mehr Zugriffe benötigt als für einen B*-Baum über
der Hauptdatei.
Aber ...
B*-Bäume 50
Grundlagen der Datenbanksysteme II
Kompensations Faktoren
Es gibt zwei Faktoren die den Nachteil der zusätzlichen Zugriffe
kompensieren:
1. Platzersparnis
Die Blöcke der Hauptdatei können jetzt immer dicht gepackt
werden. In einer B*-Baum Organisation wären sie dagegen
zwischen halb und ganz gefüllt. Platzersparnis 25% bei der
Hauptdatei.
Der Platz der für die Blätter des B*-Baumes beim Dense
Index benötigt wird ist ca. 10% des Platzes der Hauptdatei.
Die reale Ersparnis beträgt also ca. 25% - 10% = 15%
B*-Bäume 51
Grundlagen der Datenbanksysteme II
2. Falls die Sätze der Hauptdatei pinned down sind, kann die
Organisationsform B*-Baum nicht benutzt werden.
Dies kann durch benutzen eines Dense Index gelöst
werden.
Dense Index
Hauptdatei
unpinned
pinned
B*-Bäume 52
Grundlagen der Datenbanksysteme II
Methoden zum Unpinning von Sätzen
Eine andere Verwendung des Dense Index ist es, die Sätze der
Hauptdatei unpinned zu machen.
r
P
Dense Index
Hauptdatei
1:1
i
( - ) Es muß 2 Zeigern zum Satz r gefolgt werden.
( + ) Sätze der Hauptdatei sind nicht pinned.
( - ) Sätze des Dense Index sind pinned.
( + ) Beim Verschieben eines Satzes in der Hauptdatei muß nur
ein Zeiger verändert werden.
B*-Bäume 53
Grundlagen der Datenbanksysteme II
Alternative Methoden zum Unpinnen von Sätzen
• Kein Dense Index für die Hauptdatei, sondern Zeiger in
jedem Blockheader auf die Sätze in dem Block.
r
Header Block
Alle Zeiger auf den Satz r zeigen nun auf den Block, der r
enthält.
• Sätze können nicht zwischen Blocks ausgetauscht werden.
• Sätze sind innerhalb eines Blocks unpinned und daher frei
beweglich.
B*-Bäume 54
Grundlagen der Datenbanksysteme II
Kosten des Verfahrens:
• Der Platz, der für die Zeiger im Blockheader verbraucht wird.
• Die Zeit, die benötigt wird dem zusätzlichen Zeiger innerhalb
des Blocks zu folgen ist nicht relevant, da kein weiterer
Blockzugriff erforderlich wird.
• System R benutzt dieses Verfahren für Sätze mit variabler
Länge.
• Eine Generalisierung des Verfahrens ist es auf das Bucket
eines Satzes zu zeigen statt auf den Satz direkt. (Hashing)
B*-Bäume 55
Grundlagen der Datenbanksysteme II
Eine weitere Möglichkeit ist es,
• die Schlüsselwerte anstelle von Zeigern als Referenz zu
benutzen.
r v
v Dense Index
IBM nutzt dieses Verfahren bei der IMS-Datenbank.
( + ) Dense Index und Haupdatei sind unpinned.
( - ) Um einer Referenz zu folgen muß nach dem Schlüsselwert
gesucht werden.