Datenbanksysteme II - db.inf.uni-tuebingen.de · Acta Informatica, vol. 1, no. 3, September 1972. Architektur und Implementierung von Datenbanksystemen | WS 2009/10 | Melanie Herschel

Datenbanksysteme IIArchitektur und Implementierung von Datenbanksystemen

Winter 2009/10

Melanie HerschelWillhelm-Schickard-Institut für Informatik

Architektur und Implementierung von Datenbanksystemen | WS 2009/10Melanie Herschel | Universität Tübingen

Kapitel 4Baum-basierte Indizes

•Einführung

• ISAM

• B+ Bäume

2

Architektur und Implementierung von Datenbanksystemen | WS 2009/10 | Melanie Herschel | Universität Tübingen

Effizientes Bearbeiten von Bereichsanfragen

3

SELECT *

FROM Kunden

WHERE PLZ >= 30650

AND PLZ < 31000

Ansatz 1

• Sortieren der Tabelle auf der Festplatte (Sortierte Datei, siehe Kapitel 3)

• Beantworten der Anfrage:

• Binäre Suche, um erstes Antwort-Record zu finden.

• Datei scannen, so lange die PLZ < 30100 ist.

30

10

4*

30

12

3*

30

22

2*

30

45

0*

30

52

8*

30

01

2*

30

33

0*

30

42

3*

30

05

0*

30

10

5*

30

18

0*

30

24

5*

30

28

0*

30

40

6*

30

57

0*

30

60

0*

30

60

4*

30

70

0*

30

80

8*

30

88

7*

30

91

0*

30

95

3*

31

01

6*

31

20

0*

31

53

2*

scank* = Record mit Schlüsselwert k

Seiten mitDaten-

Records



4

Diskussion Ansatz 1

+ Sequentieller Seitenzugriff beim Scannen.

- Wir müssen log2(#Records) Records während der Binärsuche lesen. Da die Binärsuche darauf basiert, Große Sprünge in der Datei zu machen, müssen wir i.A. genauso viele direkte Seitenzugriffe machen.

- Einfüge- und Löschoperationen teuer.

30

10

4*

30

12

3*

30

22

2*

30

45

0*

30

52

8*

30

01

2*

30

33

0*

30

42

3*

30

05

0*

30

10

5*

30

18

0*

30

24

5*

30

28

0*

30

40

6*

30

57

0*

30

60

0*

30

60

4*

30

70

0*

30

80

8*

30

88

7*

30

91

0*

30

95

3*

31

01

6*

31

20

0*

31

53

2*

scank* = Record mit Schlüsselwert k

Seiten mitDaten-

Records



5

30

10

4*

30

12

3*

30

22

2*

30

45

0*

30

52

8*

30

01

2*

30

33

0*

30

42

3*

30

05

0*

30

10

5*

30

18

0*

30

24

5*

30

28

0*

30

40

6*

30

57

0*

30

60

0*

30

60

4*

30

70

0*

30

80

8*

30

88

7*

30

91

0*

30

95

3*

31

01

6*

31

20

0*

31

53

2*

Seiten mit Daten-

Records

Seiten im Index

30

10

4

30

52

8

30

05

0

30

28

0

30

60

4

30

91

0

31

53

2

scan

Ansatz 2

• Wir erstellen einen Index über die Daten Records.

• In diesem Index speichern wir den Schlüsselwert des ersten Records einer Seite und ein Pointer auf den Beginn der Seite.

• Binärsuche über den Index, um die erste Seite, die der Suchanfrage entspricht, zu finden.

• Laden der entsprechenden Seite der Daten Datei und von da an sequentielles Lesen, bis PLZ >= 31000.



6

Diskussion Ansatz 2

+ Sequentieller Seitenzugriff beim Scannen.

+ Daten der Indexseiten entsprechen einem Bruchteil der Daten in der Daten Datei.

! Indexdatei benötigt weniger Seiten.

!Binärsuche auf Indexdatei weniger I/O Operationen.

- Bei großen Daten-Dateien kann Indexdatei immer noch zu groß!für effiziente Bearbeitung sein.

30

10

4*

30

12

3*

30

22

2*

30

45

0*

30

52

8*

30

01

2*

30

33

0*

30

42

3*

30

05

0*

30

10

5*

30

18

0*

30

24

5*

30

28

0*

30

40

6*

30

57

0*

30

60

0*

30

60

4*

30

70

0*

30

80

8*

30

88

7*

30

91

0*

30

95

3*

31

01

6*

31

20

0*

31

53

2*

Seiten mit Daten-

Records

Seiten im Index

30

10

4

30

52

8

30

05

0

30

28

0

30

60

4

30

91

0

31

53

2

scan



7

30

10

4*

30

12

3*

30

22

2*

30

45

0*

30

52

8*

30

01

2*

30

33

0*

30

42

3*

30

05

0*

30

10

5*

30

18

0*

30

24

5*

30

28

0*

30

40

6*

30

57

0*

30

60

0*

30

60

4*

30

70

0*

30

80

8*

30

88

7*

30

91

0*

30

95

3*

31

01

6*

31

20

0*

31

53

2*

Seiten mit Daten-

Records

30

10

4

30

52

8

30

05

0

30

28

0

30

60

4

30

91

0

31

53

2

Ansatz 3: Hierarchische Indexstrukturen

• Wir wiederholen rekursiv Ansatz 2 (Index über Index usw.) bis alle Index Einträge auf eine Seite passen.

!Hierarchischer Index

30

10

4

30

60

4

Seiten im Index über mehrere Ebenen

scan



8

Diskussion Ansatz 3: Hierarchische Indexstrukturen

• Um ein Daten-Record zu finden, muss stets ein Knoten pro Ebene der Indexhierarchie betrachtet werden.

• Ein Knoten entspricht einer Seite.

• Daher ist maximale Anzahl Seiten I/Os = maximale Tiefe der Indexstruktur.

• Tiefe im Allgemeinen deutlich geringer als log2(#Records) (I/O Kosten für Suche von Ansatz 1).

!Hierarchische Indexstrukturen erlauben effizientes Bearbeiten von Suchanfragen.

!Sequentieller Scan durch Prefetching effizient bei Bereichsanfragen.


Baum-Basierte Indizes

9

Zwei hierarchische Indizes im Fokus

• ISAM

• Basiert direkt auf dem gerade vorgestellten Verfahren zum Erstellen einer hierarchischen Datenstruktur.

• Statische Index Datei, daher problematisch bei Einfüge- und Löschoperationen.

• B+-Baum

• Dynamische Indexdatei, somit effizientes Einfügen und Löschen möglich.



• Einführung

•ISAM

• B+-Bäume

10


• Gegeben eine Anfrage mit einer Selektion auf Feld k.

• Records der Daten-Datei sind auf Festplatte nach k sortiert.

• Dateneinträge in Blattknoten des Index (eine der 3 Varianten, siehe Kapitel 3)

• Dateneinträge und Daten-Records nach Schlüsselwert k sortiert (clustered Index).

• Indexeinträge sind <k,p> Paare (k: Schlüsselwert, p: Pointer auf eine Seite) in inneren Knoten des Baumes.

• Eine Indexseite enthält i Schlüsselwerte und i+1 Pointer, denn Schlüsselwerte dienen als Separatoren zwischen Pointern.

• Es gilt ki-1 < ki für i = 2, ..., n.

• Ist keys(pi) die Menge aller Schlüsselwerte, die man über pi erreicht, so gilt für jeden Schlüssel kl in keys(pi) und ku in keys(pi+1), kl < ki+1 < ku.

Index Sequential Access Method (ISAM)

11

p0 k1 p1 k2 p2 ... kn pn

IndexeintragSeparator Pointer


90* 91* 92* 93* 94* 95* 96* 97*

Index Sequential Access Method (ISAM)

12

p0 106 p1 k2 p2 ... kn pn

9* 10* 11* 12* 13* 14* 15* 16*

1* 2* 3* 4* 5* 6* 7* 8*

p0 9 p1 17 p2 ... kn pn

k < 9 9 <= k < 17

p0 k1 p1 k2 p2 ... 90 pn

90 <= k < 98

p0 k1 p1 k2 p2 ... 98 pn

k >= 98


Initialisierung eines ISAM

13

init(file F, Searchkey k)

begin

1. Sortiere Records in F nach k auf Platte;

2. Erstelle Blattknoten der Indexstruktur;

3. p := Anzahl Seiten auf aktueller Indexebene;

4.while p > 1 do

Erstelle neue Indexebene;

end

Anzahl Knoten pro Ebene? Im Baum?


Überlaufseiten für inserts, die nicht auf primäre Seiten passen.

Blattknoten bzw. Primärseiten(statisch nach init)

Innere Knoten(statisch nach init)

Überlaufseiten

14

...

... ...

... ... ... ...


Einfügen von Records

15

insert(Searchkey k)

Finde Blattknoten L, der Wert von k

entspricht.

L hat freie Record Slots?

Füge Dateneintrag k* in L ein.

Hat L Überlaufknoten mit freien Slots?

Füge Dateneintrag k* in Überlaufknoten

ein.

Erstelle einen Überlaufknoten und

verlinke ihn mit vorangehendem Knoten.

Ja

Ja

Nein

Nein


Einfügen von Records

16

delete(Searchkey k)

Finde Blattknoten L, der Wert von k

entspricht.

L ist Überlaufknoten?Lösche k* aus L.

Ist L nach Löschen von L

leer?

Lösche L.

Nein

Nein

Ja

Ja

k*


Nachteil• Die inneren Knoten der ISAM Struktur bleiben bei Lösch- und Einfügeoperationen

unverändert.

• Kann zu Indexeinträgen führen, die keinem Dateneintrag mehr entsprechen.

• Um Separatoreigenschaft von Schlüsselwerten in Indexeinträgen beizubehalten, müssen Ketten von Überlaufseiten verwaltet werden.

! ISAM kann bei vielen Updateoperationen seine Ausgeglichenheit verlieren, da einige Pfade von der Wurzel bis zu einem Dateneintrag deutlich länger sind als andere.

! Ineffizientere Suche.

!Um Überlaufseiten zu vermeiden, werden typischerweise 20% einer Blattseite bei der Initialisierung frei gelassen.

Vor- und Nachteile einer statischen Indexdatei

17


Vorteil• Die inneren Knoten der ISAM Struktur bleiben bei Lösch- und Einfügeoperationen

unverändert.

• Bei gleichzeitigem Zugriff auf den Index durch mehrere Anwendungen sind keine Locks auf den Indexseiten nötig.

• Locking ist problematisch bei dynamischen Indizes, insb. wenn Zugriff zu Knoten nahe der Wurzel durch eine Anwendung gesperrt sind.

! ISAM kann die beste Indexstruktur sein, wenn Daten sich nur gering verändern.

Vor- und Nachteile einer statischen Indexdatei

18



• Einführung

• ISAM

•B+Bäume

19


• Die Struktur eines B+-Baumindex ist von ISAM abgeleitet.

• Großer Vorteil: dymanisch bezüglich updates.

• Lösch- und Einfügeoperationen auf dem Baum selbst halten diesen ausgeglichen/ausbalanciert.

• Keine Überlaufketten, da ein B+-Baum immer balanciert bleibt.

• Suchperformance hängt ausschließlich von der Höhe des B+-Baums ab (aufgrund hoher Fan-Outs ist die Höhe selten größer als 3).

• Einfügen / Löschen von Daten in der Daten Datei führt nicht mehr zu steigender Ineffizienz der Anfragebearbeitung.

• Der Speicherplatz eines Knotens in einem B+-Baum (ausgenommen der Wurzel) wird garantiert zu mindestens 50% genutzt (typischerweise 2/3).

B+-BäumeDynamische Indexstruktur

20

Weitherführende Literatur

R. Bayer and E.M. McCreight.Organization and Maintenance of Large Ordered Indexes. Acta Informatica, vol. 1, no. 3, September 1972.


Blattknoten• Blattknoten bilden in der Praxis eine doppelt verlinkte Liste (sequence set).

• Nur Blattknoten enthalten Dateneinträge, entweder in Form der Daten Records selbst (Dateneintrag-Variante (1)) oder Referenzen zu Daten Records (Dateneintrag-Varianten (2) und (3)).

Aufbau eines inneren Knotens• Die Anzahl Indexeinträge n wird durch

den Grad d eines B+-Baums beschränkt:

• Innere Knoten: d <= n <= 2d

• Wurzel: 1 <= n <= 2d

• Gleicher interner Aufbau wie innere Knoten eines ISAM-Index.

• Knoten enthält n + 1 Pointer, wobei Pointer pi auf einen Sub-Baum zeigt, bei dem für alle Schlüsselwerte k gilt: ki <= k < ki+1.

• p0 zeigt zu einem Sub-Baum mit Schlüsselwerten < k1, p2d zeigt aug einen Sub-Baum mit Schlüsselwerten >= k2d.

B+-BäumeAufbau

21

p0 k1 p1 k2 p2 ... k2 p2d



Suche in B+-Bäumen

22

search(Searchkey k)

function search(Searchkey k) returns nodepointer

root := Wurzel des B+Baums;

return tree_search(root, k);

end function

function tree_search(Nodepointer p, Searchkey k) returns nodepointer

if p zeigt auf einen Blattknoten then return p;

else if k < k1 then return tree_search(p0, k);

else if k >= kn then return tree_search(pn, k);

else

begin

Finde i so dass ki <= k < k+1 gilt;

return tree_search(pi, k)

end

end function

p0 k1 p1 k2 p2 ... k2 pn



Beispiel: Suche von 5* in einem B+-Baum mit Grad d = 2 (Anzahl Einträge Pro Knoten zwischen 2 und 4)

Suche in B+-BäumenBeispiel

23

2* 3* 5* 7* 14* 16*

13 17 24 30

19* 20* 22* 24* 27* 29* 33* 34* 38* 39*

5*

5 < 13


Beispiel: Suche von 14* und 15* in einem B+-Baum mit Grad d = 2 (Anzahl Einträge Pro Knoten zwischen 2 und 4)

Suche in B+-BäumenBeispiel

24

2* 3* 5* 7* 14* 16*

13 17 24 30

19* 20* 22* 24* 27* 29* 33* 34* 38* 39*

14*

keine 15*

15*

13 <= 15 < 1713 <= 14 < 17


Beispiel: Suche von 24* in einem B+-Baum mit Grad d = 2 (Anzahl Einträge Pro Knoten zwischen 2 und 4)

Suche in B+-BäumenBeispiel: Suche von 24*

25

2* 3* 5* 7* 14* 16*

13 17 24 30

19* 20* 22* 24* 27* 29* 33* 34* 38* 39*

24*

24 <= 15 < 30


Einfügen in B+-Bäumen

26

Grundidee bei Einfügeoperationen1.Gegeben ein Record mit Schlüsselwert k.

2.Rufe search(k) auf, um die Seite P zu finden, die neues Record enthalten soll.

3.Sei n die Anzahl Einträge in P.

a. Ist n < 2d, so ist noch genügend Platz auf P frei, und Record wird dort gespeichert.

b.Sonst...?

Annahmen• B+-Bäume bleiben bei Updates ausgeglichen.

• Einfüge- und Löschoperationen müssen diese Invariante beibehalten.

• Keine Überlaufketten (wegen Invariante Ausgeglichenheit)

• Kosten für search(k) sollen nur von der Höhe des Baumes abhängen, daher können wir k* auch nicht einfach irgendwo (selbst nahe P) speichern.


Einfügen in B+-BäumenSplitting

27

• Splitting: Lösung, wenn die Seite p, in die k* eingefügt werden müsste voll ist.

• Dabei wird p in zwei Seiten p und p’ aufgeteilt und ein neuer Separator muss in den Elternknoten von p eingefügt werden.

• Splitting kann sich rekursiv fortsetzen und kann letztendlich zu einem Split des Wurzelknotens führen.

• Bei einem Split des Wurzelknotens wird ein neuer Wurzelknoten generiert und die Höhe des Baums erhöht sich um 1.

• Die Einträge von p und der neue Eintrag mit Schlüsselwert k werden auf den Seiten p und p’ gleichmäßig verteilt.


Beispiel: Einfügen von 8*

2* 3*5* 7* 8*

Einfügen in B+-BäumenBeispiel Splitting

28

2* 3* 5* 7* 14* 16* 19* 20* 22* 24* 27* 29* 33* 34* 38* 39*

5 1324 30

14* 16* 19* 20* 22* 24* 27* 29* 33* 34* 38* 39*

13 17 24 30

8*

8 < 13

Seite für 8* voll


Beispiel: Einfügen von 8*

2* 3* 5* 7* 8*

Einfügen in B+-BäumenBeispiel Splitting

28

14* 16* 19* 20* 22* 24* 27* 29* 33* 34* 38* 39*

5 13 24 30

14* 16* 19* 20* 22* 24* 27* 29* 33* 34* 38* 39*

17



29

Split einer Seite auf Blattebene P in 2 Seiten P und P’

•Die Hälfte der Dateneinträge auf P bleibt auf P (2* und 3* im Beispiel)

•Die andere Hälfte wird von P auf P’ kopiert und der neue Wert wird hinzugefügt (5*, 7*und 8* im Beispiel).

•Neue Seite auf Blattebene muss in Indexeinträgen reflektiert werden (z.B., <5,p>)

• Copy up: wir kopieren den ersten Schlüsselwert von P’ und fügen diesen zu entsprechendem Indexknoten als neuen Separator hinzu.

• Redundanz der Schlüsselwerte.

• Durch Redundanz können Bereichsanfragen nur mittels Blattknoten beantwortet werden --> Effizienzsteigerung



30

Split einer inneren Seite P in 2 Seiten P und P’

• Sei N die Anzahl Indexeinträge vor Einfügeoperation, die zu Split führt.

• In diesem Fall müssen beim Einfügen N+1 Einträge verteilt werden.

• Indexeintrag i, 1 <= i < (N+1)/2 auf P (z.B., <5. p1>, <13,p2>)

• Indexeintrag i, (N+1)/2 < i <= N+1 auf P’ (z.B., <24. p3>, <30, p4>)

• Push up: Indexeintrag (N+1)/2 nicht auf P oder P’ gespeichert, sondern erscheint nun als Separator zwischen P und P’ eine Ebene höher (z.B., 17).

• Keine Redundanz von Schlüsselwerten in inneren Knoten des B+-Index.

Architektur und Implementierung von Datenbanksystemen | WS 2009/10 | Melanie Herschel | Universität Tübingen 31

Split des Wurzelknotens

•Splitting beginnt immer auf der Blattebene, wenn ein neuer Suchschlüsselwert hinzugefügt wird.

•Rekursives Splitting kann sich bis zur Wurzel fortsetzen.

•Splitting der Wurzel

• Wie Splitting eines inneren Knotens.

• Erstellen einer neuen Wurzel, die den pushed-up Separator enthält.

•Der Wurzelknoten ist der einzige Knoten der Indexstruktur der einen Füllgrad < 50% aufweisen kann.

•Root Splitting ist das einzige Ereignis, das die Höhe der Baumstruktur erhöht.



Einfügen in B+-BäumenAlgorithmus

Einfügen eines Eintrags e in einen B+-Baum mit Grad d - Teil 1

procedure insert(nodepointer, e, e')

if nodepointer zeigt auf einen Blattknoten L then

if L hat freien Speicherplatz then

begin

Füge e auf L ein;

Setze e’ auf null;

return;

end

else

begin

Split L, indem die ersten d Indexeinträge auf L bleiben und die restlichen auf neu erstelltem Knoten L’ verschoben werden;

e’ := Indexeintrag <k,p>, wobei p auf L’ zeigt und k kleinster Schlüsselwert von L’;

Setze Nachbarpointer von L und L’ neu;

return;

end

if nodepointer zeigt auf einen inneren Knoten N then ...


Einfügen in B+-BäumenAlgorithmus

Einfügen eines Eintrags e in einen B+-Baum mit Grad d - Teil 2

...

if nodepointer zeigt auf einen inneren Knoten N thenbegin

Finde i so dass ki < Schlüsselwert von e < ki+1;insert(pi, e, e’);

if e’ = null then return;

else if N hat freien Speicherplatz thenbegin

Füge Indexeintrag von e’ auf N ein;e’ := null;

return;

end

else

begin

Split N, indem die ersten d Schlüssel und die ersten d+1 Pointer auf N bleiben und die letzten d Schlüssel und d+1 Pointer auf neuen Knoten N’ verschoben werden;e’ := Indexeintrag <k,p>, wobei p auf N’ zeigt und k kleinster Schlüsselwert von N’;if N ist Wurzelknoten thenbegin

N’’ := neuer Knoten mit p0 = Pointer auf N und <k1, p1> = e’;Setzte den Zeiger, der auf die Wurzel des B+-Baums zeigt auf N’’;return;

end

end

end

end procedure


Beispiel: Einfügen von 8* bei Wiederverteilung

34

Einfügen in B+-BäumenWiederverteilung (Redistribution)

•Idee: Umverteilen von Einträgen im Baum um durchschnittlichen Füllgrad zu erhöhen.

•Ziel: kompakterer Baum, dadurch weniger Disk I/O.

2* 3* 5* 7* 14* 16*

13 17 24 30

19* 20* 22* 24* 27* 29* 33* 34* 38* 39*

Seite für 8* voll

8*


Beispiel: Einfügen von 8* bei Wiederverteilung

34


•Idee: Umverteilen von Einträgen im Baum um durchschnittlichen Füllgrad zu erhöhen.

•Ziel: kompakterer Baum, dadurch weniger Disk I/O.

2* 3* 5* 7* 14* 16*

13 17 24 30

19* 20* 22* 24* 27* 29* 33* 34* 38* 39*

Seite für 8* voll

8*

Nachbar noch Platz

8* 14* 16*

8



Wiederverteilung in Blattknoten

•Gegeben: Seite P, die voll ist und in die k* eingefügt werden müsste.

• Lade Nachbar P’ in den Hauptspeicher.

• Ein Knoten P’ ist Nachbar von P wenn P’ direkt links bzw. rechts von P ist und P und P’ den gleichen Elternknoten haben.

• Ist P’ ebenfalls voll, wird Splitting durchgeführt.

• Hat P’ freien Platz

• Sei E = entries(P) ! entries(P’) ! {k*} die Menge aller Dateneinträge, die über P und P’ wiederverteilt werden. Es werden jeweils |E|/2 Einträge auf P und P’ gespeichert.

• Aktualisiere Separator im Elternknoten.

Wiederverteilung in inneren Knoten


Löschen in B+-Bäumen

36

Grundidee bei Löschoperationen1.Gegeben ein Record mit Schlüsselwert k.

2.Rufe search(k) auf, um die Seite P zu finden, aus der Record gelöscht wird.

3.Sei n die Anzahl Einträge in P.

a. Ist n > d, so ist noch genügend Platz auf P besetzt, und Record wird einfach gelöscht.

b.Sonst...?


Löschen in B+-BäumenBeispiel für einfaches Löschen (Füllgrad >= d)

37

Beispiel: Löschen von 19* aus einem Baum mit d = 2

2* 3* 14* 16*

5 13

14* 16* 19* 20* 22* 24* 27* 29*5* 7* 8*

24 30

17


Löschen in B+-BäumenBeispiel für einfaches Löschen (Füllgrad >= d)

37


2* 3* 14* 16*

5 13

14* 16* 19* 20* 22* 24* 27* 29*5* 7* 8*

24 30

17

20* 22*


Löschen in B+-BäumenWiederverteilung (Redistribution)

38


2* 3* 14* 16*

5 13

14* 16* 19* 20* 22* 24* 27* 29*5* 7* 8*

24 30

17

20* 22*


Löschen in B+-BäumenWiederverteilung (Redistribution)

38


2* 3* 14* 16*

5 13

14* 16* 19* 20* 22* 24* 27* 29*5* 7* 8*

24 30

17

20* 22*22* 24* 27* 29*

27*


Löschen in B+-BäumenMerge von Blattknoten

39

Beispiel: Löschen von 24* aus einem Baum mit d = 2, Teil 1 (Merge der Blattknoten)

2* 3* 14* 16*

5 13

14* 16* 19* 20* 22* 27* 29*5* 7* 8*

27 30

17

20* 22*22* 24*


Löschen in B+-BäumenMerge von Blattknoten

39


2* 3* 14* 16*

5 13

14* 16* 19* 20* 22*5* 7* 8*

27 30

17

20* 22*22* 24*22* 27* 29*

30


Löschen in B+-BäumenMerge von inneren Knoten

40

Beispiel: Löschen von 24* aus einem Baum mit d = 2, Teil 2 (Merge innerer Knoten)

2* 3* 14* 16*

5 13

14* 16* 19* 20* 22*5* 7* 8* 20* 22*22* 24*22* 27* 29*

17 30


Löschen in B+-BäumenRedistribution über innere Knoten

41


2* 3*

14* 16*

5 13 17 20

14* 16*

20* 21*

22* 24*

5* 7* 8*

27 30

22

... ...

27* 29*



41


2* 3*

14* 16*

5 13 17 20

14* 16*

20* 21*

22* 24*

5* 7* 8*

22

...

22* 27* 29*

30

...



42

Beispiel: Löschen von 24* aus einem Baum mit d = 2, Teil 2 (Wiederverteilung über Elternknoten)

2* 3* 14* 16*

5 13 17 20

14* 16* 20* 21* 22* 24*5* 7* 8*

27 30

22

...

22* 27* 29*

30

...

2220

17


Löschen in B+-BäumenAlgorithmus

Löschen eines Eintrags e in einen B+-Baum mit Grad d - Teil 1

procedure delete(parentpointer, nodepointer, e, e')

if nodepointer zeigt auf einen Blattknoten L then

if L hat Füllgrad > d then begin

Lösche e aus L;


return;

end

else begin

S:= Nachbar von L;

if S hat Füllgrad > d then begin

Redistribution zwischen L und S;

R := L wenn L rechts von S ist, sonst S;

P := Eintrag in Elternknoten von L und S, der auf R zeigt;

Ersetze Schlüsselwert von P durch neuen niedrigsten Wert von R;


return;

end

else begin

Verschmelze L und S;

R := L wenn L rechts von S ist, sonst S;

e’ := Indexeintrag im Elternknoten, der auf R zeigt;

Verschiebe alle Einträge von R auf den linken Knoten;

Lösche R und setzte entsprechende Nachbarpointer um;

return;

end

end

if nodepointer zeigt auf einen inneren Knoten N then ...


Löschen in B+-BäumenAlgorithmus

Löschen eines Eintrags e in einen B+-Baum mit Grad d - Teil 2

if nodepointer zeigt auf einen inneren Knoten N then begin

Finde i so dass ki < Schlüsselwert von e < ki+1;delete(nodepointer, pi, e, e’);

if e’ = null then return;

else begin

Entferne Indexeintrag e’ von N;if N hat Füllgrad > d then begin

Setze e’ auf null; return;

end

else begin

S := Nachbar von N;if S hat Füllgrad > d then begin

Gleichmäßige Verteilung von Einträgen zwischen S und N über den Elternknoten;Setze e’ auf null;return;

end

else begin

Verschmelze N und S;R := L wenn L rechts von S ist, sonst S;e’ := Indexeintrag in Elternknoten, der auf R zeigt;Ziehe Separator vom Elternknoten in den linken der Knoten S und L; Verschiebe alle Einträge von R in den linken Knoten;Lösche M;return;

end

end

end

end

end procedure


Duplikate in B+-Bäumen

45

• Die Algorithmen search, insert, delete nehmen an, dass keine Duplikate in den Suchschlüsselwerten vorkommen.

• Per Definition stimmt diese Annahme bei Primär- bzw. Unique-Indizes.

• Stimmt diese Annahme nicht, gibt es 2 Lösungsansätze

1. Die Algorithmen werden angepasst (Unterscheidung zwischen Dateneintragsvarianten 1 - 3 ).

2. Der Suchschlüssel wird mit einer eindeutigen, vom DBMS generierten ID erweitert um einen Unique-Index zu simulieren.

Handhabung von Duplikaten in Suchschlüsselwerten in DB2

Since duplicate keys add to the B+-tree complexity, IBM DB2forces uniqueness by forming a composite key of the form <k, id>

where id is the unique tuple identity of the data record withkey k.Tuple identitiesare system-maintained unique identitifers for each tuple in a table, andare not dependent on tuple order and never rise again.

Introduction

Torsten Grust

Architecture of aDBMS

OrganizationalMatters

1.10

These Slides. . .

• . . . prepared/updated throughout the semester — watch outfor bugs and please let me know. Thanks.

• Posted to course web home on the day before the lecture —bring a printout and take notes.

Example

Open Issues/Questions

Take notes.

Code Snippets, Algorithms

IBMDB2 Specifics

If possible and insightful, discuss how IBMDB2 does things.


Key Compression in B+-Bäumen

46

• I/O Kosten bei Verwendung von hierarchischen Indizes proportional zur Höhe des Baumes.

• Fan-out F bestimmt Höhe h des Baumes für einer Datei von N Seiten : h = logF N

• Für einen Indexeintrag <k, pointer zu pi> gilt i.A. |k| >> |pointer|

• Haben wir lange Schlüssel wie “Devarakonda Venkataramana Sathyanarayana Seshasayee Yellamanchali Murthi”, so haben wir einen geringen fan-out.

• Schlüsselwerte werden nur zur Weiterleitung zum entsprechenden Dateneintrag verwendet.

!Der Schlüsselwert muss nicht dem exakten Datenwert entsprechen, sondern muss nur die Separatoreigenschaft gewährleisten.

!Minimierung der Schlüsselgröße |k| für höheren Fan-out.



46








Beispiel: Key Compression in einem B+-Baum

Daniel Lee David Smith Devarakonda...... ...



46









Daniel Lee David Smith Devarakonda...... ... ?Dan Dav Dev...... ...



46










Dante Wu Darius Rex ... Davey Jones

k < David Smith

?Dan Dav Dev...... ...



46











k < David Smith

?Dan Dav Dev...... ...

Überprüfe größten Wert für k im linken Unterbaum (analog: kleinster Wert im rechten Unterbaum)



46











k < David Smith

Dan Dav Dev...... ...Davi

Überprüfe größten Wert für k im linken Unterbaum (analog: kleinster Wert im rechten Unterbaum)


Bulk-Loading eines B+-Baums

47

• Ziel: Gegeben eine Tabelle T mit 1.000.000 Tupeln, erstelle einen B+-Baum-Index über Attributwert A von T.

1. Alternative

• Führe 1.000.000 Mal insert() über wachsende Baum-struktur aus.

! Das DBMS muss 1.000.000 Mal den wachsenden Baum traversieren.

2. Alternative: Bulk-loading

Bulk-loading Algorithmus

1.Für jedes Record in T mit Suchschlüsselwert k, erstelle eine sortierte Liste L von Seiten mit Blatteinträgen k*.

2.Sei R eine leere Indexseite.

3.R.po := Erster Pointer in R, der auf die erste Seite von L zeigt.

4.Für jede Seite S in L

a.Erstelle einen Indexeintrag I := <minimales k von S, Pointer auf S>.

b.Füge I so weit rechts wie möglich in eine Seite R direkt über der Blattebene ein.

c.Ist R voll, wird diese Seite gesplittet.

•Für Dateneintragsvarianten 2 und 3 impliziert dies keine Sortierung der Daten Records.

•Für Variante 1 erstellen wir in diesem Fall einen clustered Index.

•Splitting passiert stets auf dem am weitesten rechts liegenden Pfad von den Blättern zur Wurzel.


Zusammenfassung

ISAM

• Statische Indexdatei, Einfüge- und Löschoperationen verwenden Überlaufseiten.

• Nachteil: Höhe des Baumes und somit I/O Kosten schwanken und bei zunehmenden Einfügeoperationen kann Effizienz wegen langer Ketten von Überlaufseiten sinken.

• Vortei: Keine Locks auf Indexseiten bei gleichzeitigem Zugriff verschiedener Prozesse nötig.

B+-Baum

• Dynamische Indexdatei, die garantiert, dass alle Wurzel-zu-Blatt Pfade gleich lang sind.

• Änderung der Seiten im Index Einfüge- und Löschoperationen möglich

• splitting bzw merging

• redistribution

• Key Compression, um einen höheren Fan-out zu erzielen.

• Bulk Loading zur effizienten Initialisierung einer Indexdatei.

48

Documents

Datenbanksysteme II - db.inf.uni-tuebingen.de · Acta Informatica, vol. 1, no. 3, September 1972. Architektur und Implementierung von Datenbanksystemen | WS 2009/10 | Melanie Herschel