Embed Size (px)
Citation preview
1
3.101 Exkurs: Zum Begriff „Zugriffspfade“
2 Der Begriff des Zugriffspfads ist historisch begründet und
geht davon aus, dass jede logische Kollektion in genau einer internen Datei und diese in genau einer physischen Datenstruktur gespeichert ist. Dabei gibt es dann zu jedem logischen Datenelement einen
physischen Datensatz, der das Datenelement physisch repräsentiert.
Zugriffspfade sind Strukturen, die den Datensätzen überlagert werden. Sie bestehen aus Stellvertretern der Datensätze.
Die physischen Datensätze oder deren Anteile, die die logischen Datenelemente speichern, werden als Primärdaten, die Zugriffspfade als Sekundärdaten bezeichnet.
Zur Historie: Der Begriff des „Zugriffspfads“
3 Ein logischer Zugriffspfad ist eine abstrakte Datenstruktur,
die eine Menge von Datensätzen gemäß einer vorzugsweisen Zugriffsabfolge verwaltet, und die Operationen für sequenzielle Zugriffe, direkte Zugriffe und den Aufbau und die Änderung zur Verfügung stellt.
Ein physischer Zugriffspfad ist die spezielle Implementierung eines logischen Zugriffspfads. Bei einem eingebetteten Zugriffspfad sind die Stellvertreter in
die verwalteten Datensätze „eingebettet“. Bei einem getrennten Zugriffspfad sind die Stellvertreter
getrennt von den verwalteten Datensätzen gespeichert.
Zur Historie: Der Begriff des „Zugriffspfads“
4
Beispiel: Schlüsselsequentielle Organisation der physischen Dateiverwaltung
HauptdateiÜberlauf-bereich
Index
Zur Historie: Der Begriff des „Zugriffspfads“
eingebetteter Zugriffspfad
(Primär-/Sekundärdaten)
Primärdatengetrennter Zugriffspfad
(Sekundärdaten)
5
3.102 Wiederholung und Vertiefung: B*-Bäume
6 Wertbasierter Zugriff: Zugriff aufgrund eines Attributwertes
(häufig etwas unpräzise als „Schlüssel“ bezeichnet). Klassische Techniken für wertbasierten Zugriff im
Hauptspeicher (linear sortierte Anordnung oder binär-baumartige Struktur der zu durchsuchenden Elemente) sind nicht ohne weiteres auf persistente Datenhaltung übertragbar: Sortieranordnung: Elemente, die weit auseinanderliegen,
müssen aufgesucht werden zu viele Seitenzugriffe auf Hintergrundspeicher
Baumförmige Anordnung: Suchweg durch Baum unbekannt kontrollierbare Abbildung auf Seiten nicht ohne weiteres
angebbar
Wertbasierter Zugriff
7
Ziel: Anzahl der Seitenzugriffe auch bei unbekanntem Zugriffsverhalten gering halten.
Vorgehensweise: Schrittweise und zugleich starke Begrenzung des Suchbereichs. Führt auf Baumstruktur.
Alle für DB-Zugriff relevanten baumstrukturierten Organisationsformen müssen für Seitenstrukturen konzipiert sein. Daher: Jeder Schritt beinhaltet einen Zugriff auf eine Seite, auf der dann eine große Zahl von Suchschritten im Hauptspeicher vollzogen werden. Sei s Zahl der Suchschritte pro Seite und N die Gesamtzahl
der Sätze. Dann ist die Anzahl der Seitenzugriffe beim Fortschreiten in einem ausgewogenen Baum O(logs(N)).
s = 2 BinärbaumZiel: s > 100 Mehrwegbaum
Baumförmige Anordnungen
8
Vergleich Binärbaum und Mehrwegbaum
Binärbaum (s=2)520
356 740
231 409 622 834
587 701 822 910123 277 386 469
65 143 241 278 361 399 420 501 534 597 679 712 780 831 878 923
9
Vergleich Binärbaum und MehrwegbaumMehrwegbaum (s=6) 277 409 578 740 910
65 123 143 231 241
278 361 356 386 399
420 469 501 520 534
597 622 679 701 712
780 822 831 834 878
923
s=6
10
Ein Knoten des Baums wird auf einer Seite gespeichert. Damit bei direktem Zugriff nur auf wenige Seiten
zugegriffen werden muss, ist ein sehr hoher Verzweigungsgrad der Wurzel und der internen Knoten anzustreben (s im Bereich 100 bis 500).
Damit lässt sich selbst bei hoher Skalierung die Höhe eines Mehrwegbaums auf 3 bis 4 begrenzen. Eine Höhe über 4 kommt praktisch nie vor.
Zugleich müssen bei sortierter sequenzieller Verarbeitung aller Sätze die Elemente eines Knotens die Zugriffsabfolge widerspiegeln.
Eigenschaften von Mehrwegbäumen
11 Allerdings sollte dann zusätzlich gelten:
Der Baum ist balanciert, um ein ausgewogenes Zugriffsverhalten zu garantieren.
Die Datensätze sind möglichst kompakt auf wenigen Seiten gespeichert, d.h. der Füllgrad der Seiten ist möglichst hoch.
Da jedoch Änderungen Balancierung und Füllgrad beeinflussen, wird man zur Wiederherstellung der Balance und eines hohen Füllgrads fordern, dass die Reorganisation auf einen möglichst kleinen Teil des Baums begrenzt bleibt.
Das flexible Verhalten bei Änderungsoperationen verlangt Kompromisse.
Wir studieren diese an den am weitesten verbreiteten B- und B*-Bäumen in ihren verschiedenen Varianten.
Eigenschaften von Mehrwegbäumen
12
Ein B-Baum vom Typ (k,h) ist ein leerer Baum oder ein Baum mit folgenden Eigenschaften:
1. Jeder Weg von der Wurzel zu einem Blatt hat die gleiche Länge h (Länge = Zahl der Knoten). h daher als Höhe bezeichnet.
2. Jeder Knoten j, der nicht Blatt ist, hat nj+1 Kinder. Ist der Knoten Wurzel so gilt 1 nj 2k, andernfalls k nj 2k.
3. Jeder Knoten mit nj+1 Kindern ist mit nj sortiert angeordneten Schlüsseln belegt (sowie mit Datensätzen).
4. Seien S1,…,Sn die Schlüssel eines Knotens j mit nj+1 Söhnen. Seien Z0, Z1, …, Zn die Zeiger auf diese Kinder.
a) Z0 weist auf Teilbaum mit Schlüsseln kleiner S1 b) Zi (i=1, …, nj-1) weist auf Teilbaum, dessen Schlüssel echt zwischen
Si und Si+1 liegen. c) Zn weist auf Teilbaum mit Schlüsseln größer Sn. d) In den Blattknoten sind die Zeiger nicht definiert.
B-Baum
13Interne Struktur der Knoten (1)
Z0 S1 D1 Z1 S2 D2 Z2 … Sn Dn Zn frei
Schlüsselwert Satzdaten Zeiger auf Kindknoten
Di enthält nur den Datensatz zum Schlüssel Si
Eindeutige Schlüsselwerte
Di enthält Anzahl der Datensätze und die Datensätze selbst
Di enthält Anzahl der Datensätze, zu jedem Datensatz die Länge und die Datensätze selbst
Di enthält ein Längenfeld und den Datensatz zum Schlüssel Si
Mehrere Datensätze mit gleichem Schlüssel zugelassen
Sätze fester Länge Sätze variabler Länge
14 Lösungen für die Satzdaten Di:
Datensätze direkt in den Knoten des Baums (eingebettete Datensätze).
Stellvertreter (Verweise auf die Datensätze) in den Knoten des Baums (ausgelagerte Datensätze). Die Datensätze selbst sind getrennt auf anderen Seiten (durch externe Platzierung) gespeichert.
Die Entscheidung fällt auf der internen Ebene. Beispiel: Ausgelagerte Datensätze:
Man definiert eine Datei F1, die Schlüsselwerte und Verweise auf eine Datei F2 enthält.
Wird F1 in einem B-Baum gespeichert, dann erhält man einen B-Baum mit ausgelagerten Datensätzen.
Daher einheitliche Betrachtungsweise: Ein B-Baum enthält somit immer die vollständigen Datensätze der internen Datei, die er physisch repräsentiert.
Interne Struktur der Knoten (2)
15Annahme: k=1
Beispiel für einen B-Baum
50 50 „white“
„brown“ 70 „red“
„blue“
„yellow“
40 „black“
„green“„red“
„yellow“
30 30 70 70
40 80 80 90 90
60 6020 2010 10
Schlüssel Datensatz
Höhe eines B-Baums mit N Datenseiten:log 2k+1(N+1) h 1+logk+1((N+1)/2) (N 1)
Aus der Sicht der nächsten Ebene:
SeparatorAus der Sicht des
Knotens: Wegweiser
16 Eineindeutige Zuordnung von Knoten und Seiten. Ein Knoten wird auf irgendeiner frei wählbaren Seite des
Segmentes gespeichert. Folge: h beschreibt maximale Anzahl der Seitenzugriffe bei
direktem Zugriff. Niedriges h ist anzustreben, somit hohes k („fan-out“)
notwendig. Fan-out k ist jedoch abhängig von Satzlänge! Errechne sich
die maximal mögliche Zahl der Einträge pro Seite zu m. Dann ist k = (m/2).
Zuordnung von B-Baum-Knoten zu Seiten
Beispiel: Seitengröße = 4 KB Zeiger- und Schlüssellänge = 4 B Satzlänge = 120 B: 2k = 32 (z.B. Einbettung) Satzlänge = 8 B: 2k = 256 (z.B. Auslagerung)
17 Jeder Knoten enthält n Schlüssel mit
k n 2k Einfügen eines neuen Datensatzes erfordert 2 Phasen:
1. Suche nach dem Schlüssel des neuen Datensatzes (notfalls bis zum Blatt).
2a. Falls gefunden: Einfügen des neuen Datensatzes in den entsprechenden Knoten des B-Baums (bei nichteindeutigem Schlüssel).
2b. Falls nicht gefunden: Einfügen des neuen Datensatzes in das bei der Suche erreichte Blatt.
Einfügen eines Datensatzes
18Beispiel: Einfügen des Datensatzes [ 32, „gray“, ]
Einfügen eines Datensatzes
50 50 „white“
„brown“ 70 „red“
„blue“
„yellow“
40 „black“
„green“„red“
„yellow“
30 30 70 70
40 80 80 90 90
60 6020 2010 10
3232 „gray“
19Beispiel: Einfügen des Datensatzes [42, „rose“, ]
Einfügen eines Datensatzes
50 50 „white“
„brown“ 70 „red“
„blue“
„yellow“
40 „black“
„green“„red“
„yellow“
30 30 70 70
40 80 80 90 90
60 6020 2010 10
3232 „gray“
Knotenüberlauf!
20 Bei Überlauf eines Knotens wird der Knoten gespalten, d.h.
die Einträge des Knotens werden auf zwei Knoten verteilt. Die alte Seite wird weiterverwendet (z.B. für den ersten
Knoten). Für den zweiten Knoten wird eine zusätzliche Seite von der Seitenverwaltung angefordert.
Der Datensatz, der in der Mitte des übergelaufenen Knotens liegt, wird zum Elternknoten propagiert.
Einfügen eines Datensatzes
S1 < S2< … < Sk < Sk+1 < S k+2 < … < S2k+1
alter Knoten
Propagation zum Elternknoten
neuer Knoten
21
„brown“ 30 30
40 „black“40 3232 „gray“
70 „red“ 70 70
Beispiel: Einfügen des Datensatzes [42, „rose“, ]
Einfügen eines Datensatzes
50 50 „white“
„blue“
„yellow“ „green“„red“
„yellow“80 80 90 90
60 6020 2010 10
32
„brown“
42 „rose“
30 30
42 32 „gray“
„black“ 40 40
22 Spalten von Knoten kann sich im Elternknoten rekursiv
fortsetzen. Schlimmster Fall:
Alle Knoten bis zur Wurzel laufen über und werden gespalten. Wenn sogar die Wurzel überläuft, wird auch sie gespalten. Folge: Der Baum wächst in der Höhe um 1.
Einfügen eines Datensatzes
23
Entfernen eines Datensatzes erfordert 2 Phasen: Suche nach dem zu entfernenden Datensatz anhand seines
Schlüssels. Entferne ihn. Zwei Fälle:
1. Datensatz befindet sich in einem Blatt. 2. Datensatz befindet sich in einem internen Knoten oder in der
Wurzel.
Entfernen eines Datensatzes
24Fall 1, Beispiel: Entfernen des Datensatzes [ 32, „gray“, ]
Entfernen eines Datensatzes
50 50 „white“
„blue“ „yellow“80 80 90 90
„green“ 60 60
„yellow“ „red“ 20 2010 10
42 „rose“42 3232 „gray“
„brown“ 30 30 „black“ 40 40
Falls der Blattknoten nunmehr weniger als k Datensätze enthält, entsteht ein Knoten-Unterlauf
70 „red“ 70 70
25
Knoten-Unterlauf: Invarianz des B-Baums: Jeder Knoten hat n Datensätze mit
k n 2k. Nach dem Entfernen hat Knoten weniger als k Datensätze. Es wird versucht, Datensätze aus den Nachbarknoten in den
Knoten mit Unterlauf zu verschieben.
Entfernen eines Datensatzes
26Entfernen eines Datensatzes
50 50 „white“
„blue“ „yellow“80 80 90 90
„green“ 60 60
„red“ 20 20„yellow“10 10
42 „rose“42
„brown“ 30 30 „black“ 40 40
„red“ 20 20
„brown“ 30 30
70 „red“ 70 70
27 Problem: Wenn alle Nachbarknoten nur minimal belegt sind,
kann kein Ausgleich stattfinden (das Entfernen von Datensätzen aus den Nachbarknoten würde dort zu einem Unterlauf führen).
In diesem Fall wird der Unterlauf-Knoten mit einem seiner Nachbarknoten zusammengelegt.
Die freiwerdende Seite wird an die Seitenverwaltung zurückgegeben.
Das Zusammenlegen zweier Knoten führt zu dem Verschieben des Separator-Datensatzes aus dem Elternknoten in den neuen, durch das Zusammenlegen entstehenden Knoten.
Wie beim Splitten von Knoten kann sich das Zusammenlegen von Knoten bis zur Wurzel fortsetzen.
Folge: Der Baum schrumpft in der Höhe um 1.
Entfernen eines Datensatzes
28Entfernen eines Datensatzes
50 50 „white“
„blue“ „yellow“80 80 90 90
„green“ 60 60
„yellow“10 10
42 „rose“42
„brown“ 30 30 „black“ 40 40„red“ 20 20
„brown“ 30 30
Fall 1, Beispiel: Entfernen des Datensatzes [ 30, „brown“, ]
„black“ 40 40
70 „red“ 70 70
29
Fall 2: Finde einen neuen Separator-Datensatz als Ersatz für den
zu entfernenden Datensatz. Zwei Alternativen für Auswahl des Separator-Datensatzes:
1. Wähle den Datensatz mit dem kleinsten Schlüssel, der größer ist als der Schlüssel des zu entfernenden Datensatzes (Inorder-Nachfolger).
2. Wähle den Datensatz mit dem größten Schlüssel, der kleiner ist als der Schlüssel des zu entfernenden Datensatzes (Inorder-Vorgänger).
Der ausgewählte Separator-Datensatz wird aus seinem Knoten entfernt (rekursiver Aufruf der
Operation zum Entfernen von Datensätzen!) und ersetzt den zu entfernenden Datensatz in dessen Knoten.
Entfernen von Datensätzen
30Fall 2, Beispiel: Entfernen des Datensatzes [ 30, „brown“, ]
Entfernen eines Datensatzes
50 50 „white“
„blue“ „yellow“80 80 90 90
„green“ 60 60
42 „rose“42 3232 „gray“
„brown“ 30 30 „black“ 40 40„red“ 20 20
„red“ 20 20„yellow“10 10
neuerSeparator-Datensatz
70 „red“ 70 70
31
Gewünschte Aussage:Baumstrukturen bieten einen attraktiven und ausgewogenen
Kompromiss zwischen günstigem direktem Schlüsselzugriff, günstiger sortierter sequenzieller Verarbeitung aller Sätze, flexiblem Verhalten bei Änderungsoperationen.
Bewertung B-Baum
+-+
32
Abhilfe: Führe informationstragende Einträge (Satzdaten Di) ausschließlich in den Blattknoten und organisiere sie dort als verkettete Liste.
Folge: Schlüssel in allen anderen Knoten haben daher ausschließlich Wegweiserfunktion (Redundanzen!).
Charakterisierung: Man spricht daher von „blattorientierten“ oder „hohlen“ Bäumen.
Andere Bezeichnung: B+-Baum. Mehrere Definitionen gebräuchlich, die hier verwendete lehnt
sich eng an den B-Baum an.
B*-Baum
33Ein B-Baum vom Typ (k,h) ist ein leerer Baum oder ein Baum mit folgenden
Eigenschaften:1. Jeder Weg von der Wurzel zu einem Blatt hat die gleiche Länge h (Länge = Zahl
der Knoten). h daher als Höhe bezeichnet.2. Jeder Knoten j, der nicht Blatt ist, hat nj+1 Söhne. Ist der Knoten Wurzel so gilt 1
nj 2k, andernfalls k nj 2k. 3. Jeder Knoten mit nj+1 Söhnen ist mit nj sortiert angeordneten Schlüsseln belegt
(sowie mit Datensätzen).4. Seien S1,…,Sn die Schlüssel eines Knotens j mit nj+1 Söhnen. Seien Z0, Z1, …, Zn
die Zeiger auf diese Söhne.a) Z0 weist auf Teilbaum mit Schlüsseln kleiner S1
b) Zi (i=1, …, nj-1) weist auf Teilbaum, dessen Schlüssel echt zwischen Si und Si+1 liegen.
c) Zn weist auf Teilbaum mit Schlüsseln größer Sn.
d) In den Blattknoten sind die Zeiger nicht definiert.
B-Baum
34Ein B*-Baum vom Typ (k,k*,h) ist ein leerer Baum oder ein Baum mit folgenden
Eigenschaften:1. Jeder Weg von der Wurzel zu einem Blatt hat die gleiche Länge h (Länge = Zahl
der Knoten). h daher als Höhe bezeichnet.2. Jeder Knoten j, der nicht Blatt ist, hat nj+1 Söhne. Ist der Knoten Wurzel so gilt 1
nj 2k, andernfalls k nj 2k.
3. Jeder Knoten mit nj+1 Söhnen ist mit nj sortiert angeordneten Schlüsseln (Wegweisern) belegt.
4. Seien S1,…,Sn die Schlüssel eines Knotens j mit nj+1 Söhnen. Seien Z0, Z1, …, Zn die Zeiger auf diese Söhne.
a) Z0 weist auf Teilbaum mit Schlüsseln kleiner oder gleich S1
b) Zi (i=1, …, nj-1) weist auf Teilbaum, dessen Schlüssel zwischen Si und Si+1 liegen und Si+1 einschließen können.
c) Zn weist auf Teilbaum mit Schlüsseln größer Sn.
5. Jeder Blattknoten enthält mindestens k* und höchstens 2k* Einträge. Ist die Wurzel Blatt, so enthält sie mindestens einen Eintrag.
6. Die Blattknoten sind doppelt verkettet in auf- bzw. absteigender Schlüsselreihenfolge.
B*-Baum
35 Format eines internen Knotens:
Format eines Blattknotens:
Interne Struktur der Knoten
Z0 S1 Z1 S2 … Sn Zn frei
Wegweiser-Schlüssel Kindzeiger
P S1 D1 S2 D2 … NfreiSn Dn
Previous-Zeiger Schlüssel Satzdaten Next-Zeiger
36Annahme: k=1
Beispiel für einen B-Baum
50 50 „white“
„brown“ 70 „red“
„blue“
„yellow“
40 „black“
„green“„red“
„yellow“
30 30 70 70
40 80 80 90 90
60 6020 2010 10
Schlüssel Datensatz
Höhe eines B-Baums mit N Datenseiten:log 2k+1(N+1) h 1+logk+1((N+1)/2) (N 1)
37Beispiel für einen B*-Baum
Annahme: k=2, k*=1
„yellow“ „red“20 2010 10
25 45 65 75
„blue“ „yellow“90 9080 80
„brown“ „black“40 4030 30 „red“70 70
„white“ „green“60 6050 50
Schlüssel Datensatz
Wegweiser
Höhe h eines B*-Baums mit N Datenelementen: )2(
2log2
2log1 112 ≥⎟⎠
⎞⎜⎝⎛+≤≤⎟⎠
⎞⎜⎝⎛+ ∗+∗+ h
kNh
kN
kk
38Beispiel für einen B*-Baum
Annahme: k=2, k*=1
„yellow“ „red“20 2010 10
25 45 65 75
„blue“ „yellow“90 9080 80
„brown“ „black“40 4030 30 „red“70 70
„white“ „green“60 6050 50
Schlüssel Datensatz
Wegweiser
Im Beispiel kommt keiner der Separator-Schlüssel der Wurzel in den Blättern vor; d.h. keiner der Separator-Schlüssel taucht in der Datei auf, die in dem B*-Baum gespeichert ist.
Prinzipiell dürfen die Separator-Schlüssel auch unter den in der Datei vorkommenden Schlüsseln gewählt werden; in diesem Fall werden Schlüssel mehrfach (redundant) gespeichert.
39Vergleich B-Baum mit B*-Baum
B-Baum
B*-Baum
S
S S
…
Indexteil mit Datensätzen
Indexteil mit Schlüsseln
(Wegweisern)
Blattknoten mit Datensätzen
S
40
Blattknoten sind als geclusterte Liste in auf- und in absteigender Reihenfolge verkettet, um die sortierte sequenzielle Verarbeitung der Datensätze zu beschleunigen.
Da die internen Knoten ausschließlich Wegweiser enthalten, ergibt sich ein höherer Verzweigungsgrad
als beim B-Baum. Geringer Preis: Zusätzliche Speicherung der Wegweiser-
Schlüssel. Typischer Wert für die Höhe eines B*-Baums: Höhe 3-4 bei
105 - 107 Datensätzen.
Vergleich B-Baum mit B*-Baum
41
Prinzip wie beim B-Baum: Suche den Schlüssel des neuen Datensatzes im Baum. Die Suche führt beim B*-Baum immer zu einem Blatt, da
Datensätze nur in Blättern gespeichert sind. Füge neuen Datensatz in das Blatt ein. Falls der Blattknoten überläuft, wird der Knoten gespalten. Beim Spalten eines Knotens wird ein neuer Separator-
Schlüssel bestimmt und in den Vaterknoten eingefügt.
Einfügen eines Datensatzes
42Einfügen eines Datensatzes
„yellow“ „red“20 2010 10
25 45 65 75
„blue“ „yellow“90 9080 80
„brown“ „black“40 4030 30 „red“70 70
„white“ „green“60 6050 50
43
...
... 6050 ...
30
Einfügen eines Datensatzes mit Schlüssel 74:
Einfügen eines Datensatzes
... 2010
25 45 65 75
...
... 40 70
... 9080 ...
... ... 74
44
...
... 6050 ...
30
Einfügen eines Datensatzes mit Schlüssel 51:
Einfügen eines Datensatzes
... 2010
25 45 65 75
...
... 40 70
... 9080 ...
... ... 74
k=2, k*=1
Überlauf
45
... 30
Einfügen eines Datensatzes mit Schlüssel 51:
Einfügen eines Datensatzes
... 2010
25 45 65 75
...
... 40 70
... 9080 ...
... ... 74
k=2, k*=1
... 50 ... 51 ... 60
Neuer Separator:55
Überlauf
46
... 30
Einfügen eines Datensatzes mit Schlüssel 51:
Einfügen eines Datensatzes
... 2010
25 45 65 75
...
... 40 70
... 9080 ...
... ... 74
k=2, k*=1
... 50 ... 51 ... 60
55
47
Beachte: Beim B-Baum wurde unter den Datensätzen des
übergelaufenen Knotens ein Separator-Datensatz ausgewählt und in den Vaterknoten verschoben.
Beim B*-Baum wird ein beliebiger Schlüssel bestimmt, der die Datensätze des übergelaufenen Knotens in zwei Teilmengen teilt.
Der Schlüssel braucht nicht in den Datensätzen des Knotens vorzukommen. Hierdurch hat man beim B*-Baum mehr Freiheiten, die Datensätze eines übergelaufenen Knotens in zwei Teilmengen zu separieren.
Einfügen eines Datensatzes
48Wahl eines Separatorschlüssels:
Einfügen eines Datensatzes
20 21 22 23 24 9019 20 21 22 23 24 90
22
19
Einfügen von „19“, k=3
Aufteilung der Datensätze des übergelaufenen Knotens in zwei möglichst gleich große Teilmengen.
Gleichmäßige Füllgrade der beiden Seiten, so dass weitere Einfügungen nicht direkt wieder zu einem Spalten führen. Bei Gleichverteilung der Schlüssel werden sich jedoch sehr viele Datensätze im rechten Teilbaum ansammeln, so dass dort sehr viele Spaltungen vorkommen werden.
49Wahl eines Separatorschlüssels:
Einfügen eines Datensatzes
Einfügen von „19“, k=3
20 21 22 23 24 90 20 21 22 23 24 90
55
19 19
Zukünftige Einfügungen von Datensätzen sollen möglichst gleichmäßig auf die beiden durch den Separatorschlüssel getrennten Teilbäume verteilt werden. (Die Verfolgung dieses Ziels erfordert Wissen über die Verteilung der Schlüssel in der Datei.)
Vorteil: Auf lange Sicht guter Separatorschlüssel, da der „Schlüsselraum“ in zwei gleich große Teile geteilt wird. Nachteil: Kurzfristige Gefahr des Überlaufens der linken Seite, da diese sehr stark gefüllt ist.
50
Spalten der Wurzel bei B- und B*-Baum: Die Wurzel eines Baums ist der Einstiegspunkt in den Baum. Die
Seitennummer des Wurzelknotens ist daher an verschiedenen Stellen der Datenbasis (bspw. in Katalogen, die die physischen Daten-strukturen verwalten) gespeichert.
Wird beim Spalten der Wurzel eine neue Seite für die Speicherung der neuen Wurzel genommen, dann müsste an allen Stellen der Verweis auf die alte Wurzel-Seite durch die Nummer der neuen Wurzel-Seite ersetzt werden.
Um diesen Aufwand zu sparen, wird über die gesamte Lebensdauer eines B- oder B*-Baums dieselbe Seite zur Speicherung der Wurzel genommen.
D.h.: Beim Anlegen eines neuen Wurzelknotens werden die Einträge der bisherigen Wurzel auf zwei neuen Seiten verteilt, und der neue Wurzelknoten wird auf der bisherigen Wurzel-Seite gespeichert.
Einfügen eines Datensatzes
51Einfügen eines Datensatzes
P123
P401 P532
P123
52
Das Entfernen von Datensätzen beginnt beim B*-Baum immer in einem Blattknoten.
Die Unterlauf-Behandlung und die Strategien für den Ausgleich zwischen Knoten sind ähnlich wie beim B-Baum.
Entfernen von Datensätzen
53Beim B-Baum erfolgt die sequenzielle Verarbeitung der Datensätze in Schlüsselreihenfolge durch eine Inorder-Traversierung des Baums.
Sequenzielle Verarbeitung von Datensätzen
Keine gute Unterstützung der sequenziellen Verarbeitung, da auf innere Knoten und die Wurzel mehrfach zugegriffen wird.
54Sequenzielle Verarbeitung von Datensätzen
S
S S
…
S
Beim B*-Baum erfolgt die sequenzielle Verarbeitung durch Verfolgen der Zeiger in den Blattseiten.
Gute Unterstützung der sequenziellen Verarbeitung, da auf jeden Knoten nur einmal zugegriffen wird.
55 Die Suchzeit ist bei hohen Werten von k bzw. k* nicht
vernachlässigbar. Sprung- und Binärsuche statt sequenzieller Suche nur bei
konstanten Datensatzlängen und überwiegend eindeutigen Schlüsselwerten.
Suchzeit innerhalb eines Knotens
Sprungsuche
Sequenzielle Suche
Binärsuche
m m
4m
2m
teSuchschrit 1log2 −≈ m
m
56Welche Anfragen werden häufig gestellt?
1. Exact Match Queries (EMQ): Zugriffe auf einen Schlüsselwertselect A1,A2,...,An
from R where Ai = c2. Range Queries (RQ): Bereichszugriffeselect A1,A2,...,An
from Rwhere Aic2 and Aic1
Leistungsbetrachtungen B*-Baum
57
Dominanz von Exact Match Queries (EMQ):Niedrige Höhe anstreben hohe Werte für k und ggf. k* und hohe Werte für den Füllgrad ni eines Knotens, k ni 2k bzw. k* ni 2k*
Dominanz von Range Queries (RQ): Bei kleinen Schlüsselintervallen wie EMQ Bei großen Schlüsselintervallen kompakte Speicherung der
Datensätze auf den Blattseiten hohe Werte für deren Füllgrad und ggf. k*
Mix von EMQs und RQs:Es dominiert i.allg. die Bearbeitungszeit für die RQs (besonders bei großen Suchintervallen).
Wie bei RQs ist ein hoher Füllgrad der Blattseiten wichtiger als eine niedrige Höhe des Baums.
Leistungsbetrachtungen B*-BaumHöhe h eines B*-Baums mit N Datenelementen:
)2( 2
log22
log1 112 ≥⎟⎠⎞⎜⎝
⎛+≤≤⎟⎠⎞⎜⎝
⎛+ ∗+∗+ hkNh
kN
kk
58 Füllgrad ist bei jedem Knoten außer Wurzel: > 50%. Ungünstigster Fall: sequenzielles Laden des Baums sortiert
nach auf- oder absteigenden Schlüsseln: = 50%. Mittlerer Füllgrad bei zufälligem Einfügen und Löschen:
= 69% Höhere Belegung lässt sich durch Verzögerung des
Spaltens von Seiten erreichen: Spalten erst, wenn m um den Einfügepunkt gruppierte Knoten
voll sind: m (m+1). Abändern des Einfügealgorithmus mit Inspektion der
Nachbarknoten und Ausgleich der Knotenbelegung. Nachteil: Höhere Einfügekosten, steil ansteigend für m > 3.
Beeinflussung des Füllgrads
59
Vergrößerung von k durch Vergrößerung der Seitengröße. Vergrößerung von k bei unveränderter Seitengröße:
Übergang von B-Baum zu B*-Baum (keine Sätze in den Zwischenknoten).
Einsatz von Verfahren zur Schlüsselkomprimierung.
Beeinflussung des Verzweigungsgrades
60 Zeichenkomprimierung, bspw. durch Entfernen führender
Nullen, abschließender Zwischenräume. Bei B*-Baum: Systematische Konstruktion von
Separatoren / Wegweisern minimaler Länge. Folge:
Variable Schlüssellänge k variabel über Knotenmenge und zeitlich schwankend über
Knoten. Aufspalten von Seiten dann nicht mehr über Zahl der Einträge,
sondern nach der Speicherbelegung.
Möglichkeiten zur Schlüsselkomprimierung
61 Gegeben: Schlüssel eines gespeicherten Satzes, der die
Separatorfunktion wahrnehmen könnte. Idee: Beschränkung auf für diese Funktion signifikanten
Teil: Weglassen des für die Unterscheidung unerheblichen hinteren
Teils. Präfix-B-Bäume Zusätzliche Komprimierung des übriggebliebenen Präfix. Präfix-Suffix-Komprimierung (front and rear compression)
Systematische Wegweiserkonstruktion
62 B-Baum:
Originalpublikation: R. Bayer und E. M. McCreight. Organization and Maintenance of Large Ordered Indexes. Acta Informatica, 1:4. 1972. 290-306.
Überblick: D. Comer: The Ubiquitous B-Tree. ACM Computing Surveys, 11:2, Juni 1979, Seiten 121-137.
B*-Baum: Originalpublikation:
D. E. Knuth: The Art of Programming, Vol. 3, Addison-Wesley, 1973. Zur Terminologie: Bei Knuth
B*-Baum ist ein B-Baum mit garantierter 2 / 3-Auslastung der Knoten B+-Baum ist ein hohler Baum derart wie hier dargestellt. Heutige Datenbankliteratur: B*-Baum = B+-Baum.
Historie und Terminologie
