Universität Karlsruhe (TH) © 2008 Univ,Karlsruhe, IPD, Prof. LockemannDBI 6 Kapitel 6 Zugriffsschicht: Satzzugriffsstrukturen

UniversitätKarlsruhe (TH)

© 2008 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 6

Kapitel 6

Zugriffsschicht: Satzzugriffsstrukturen

2


Gegenstand des Kapitels

Mengenorientiertes Datenmodell

Datenmodell

Dateien

Dateiverwaltung

Geräteschnittstelle

Anfragebearbeitung

Satzorientiertes Datenmodell

Speicherstruktur

Schneller Transport zwischen Haupt- und Hintergrundspeicher

Hauptspeicherseiten u. Segmente

Segment- u. Pufferverwaltung Bevorratung von Daten im Hauptspeicher (rechtzeitige Bereitstellung vor Benutzung)

Transparenter homogener Speicher Datentypen:

Seite = feste Anzahl von BytesSegment = var. Anzahl von Seiten

Operatoren:Anforderung/Freigabe von SeitenSegmente anlegen/öffnen/schließen

Datentypen:Block = feste Anzahl von BytesDatei = variable Anzahl v. Blöcken

Operatoren: Dateien anlegen/öffnen/schließen Lesen/Schreiben von Blöcken

Geräte-E/A

Satz- u. Satzmengenverwaltung

Satzzugriffsstrukturen

Zugriffsschicht

Vorschau auf zukünftig benötigte Daten

Vermeiden nicht aktuell benötigter Daten

Datentypen:Sätze und Satzmengen

Operatoren:Operatoren auf Sätzen

Datentypen:Satzmengen

Operatoren:Operatoren auf Mengen

Datentypen:phys. Zugriffsstrukturen auf Sätze

Operatoren:seq. Durchlauf, gezielte Suche

Optimaler Einsatz der logischen Ressourcen

Performanz

3


Anordnung Datensätze auf Seiten: Satzverwaltung

Bei Strukturen mit Gemeinsamkeiten

Datenmodell

Physische DB (satzorientiert)

Zugriffs-struktur

Kl. Physischer Datensatz

enthält▶0..1

enthält▶0..1..

Physische DB (seitenorientiert)

Segment Seite

repräsentiertdurch

▼

gespeichertin▼

1..

1

1..

1enthält▶

0..1enthält▶

0..1

Derselbe Satz kann mehreren Zugriffstrukturen

angehörenPerformanter Zugriff

4


Kapitel 6.1Kapitel 6.1

ZugriffspfadeZugriffspfade

5


Alle Zugriffsstrukturen müssen mindestens folgende Schnittstellenoperationen anbieten:

Einfügen eines Datensatzes in die Zugriffsstruktur, Entfernen eines Datensatzes aus der Zugriffsstruktur.

Sequenzieller Zugriff: Iterieren (scan) über alle Datensätze der Zugriffsstruktur (bspw. Operation first für den Zugriff auf den ersten Datensatz und next für den Zugriff auf den folgenden Datensatz). Erlaubt das systematische Aufsuchen/Bearbeiten der

Datensätze der Zugriffsstruktur.

Operatoren (1)

6


Optional Direkter Zugriff: Jeder Datensatz muss sich anhand eines von anderen Datensätzen unabhängigen Kriteriums bestimmen lassen.

Zugriff anhand Position. Zugriff anhand eines Schlüsselfelds. Zusätzlich optional:

Sortierung der Datensätze anhand eines Schlüsselfelds und Iteration über die Datensätze in auf- oder absteigender Sortierreihenfolge sequenzieller Zugriff.

Überprüfung der Eindeutigkeit von Schlüsselwerten.

Zugriff anhand mehrerer Schlüsselfelder. Optional: Reorganisation der Zugriffsstruktur nach

Performanzabfall.

Operatoren (2)

7


Ziel: Schneller Zugriff auf aktuell benötigte Datensätze möglichst weit gehendes Vermeiden von Zugriffen auf nicht

benötigte Datensätze. Anzahl der Zugriffe bis zum Erreichen des oder der gesuchten

Datensätze ist nicht oder nur sehr schwach abhängig von der Größe der Satzmenge (Skalierbarkeit).

Zugriffspfad: Abstrakter Begriff zur Beschreibung des Kriteriums, nach dem

auf benötigte Datensätze einer Satzmenge zugegriffen wird. Zugriffsstruktur:

Realisierung einer Satzmenge samt Zugriffspfad. Primärdaten: Auf der Nutzerebene sichtbarer Anteil an den

Datensätzen. Sekundärdaten: Daten zu den Zugriffspfaden.

Zugriffspfad

8


Lösung: Ballen als Basistechnik.

Zugriffspfad als Vorhersagemodell.

Erfordert gesteuerte Platzierung der Datensätze.

Erreichen des Ziels beurteilt nach mittlerem oder schlechtestem Aufwand = Anzahl der Seitenzugriffe für das Einfügen von Datensätzen,

das Entfernen von Datensätzen,

das Auffinden von Datensätzen,

das Ändern von Datensätzen.

Umsetzung und Leistungsbeurteilung

9


Beispiele für Zugriffspfade

Kriterium Zugriffspfad Zugriff

Erschöpfendes Aufzählen nach Position

Reihenfolge Iterieren (scan) über alle Datensätze: bspw. Operation first für den Zugriff auf den ersten und next für den Zugriff auf den folgenden Datensatz.

Position Positions-bestimmung

Direkter Zugriff

Einzelner Schlüsselwert

Werte der Schlüsselfelder

Direkter Zugriff

Kombination v. Schlüsselwerten

Werte der Schlüsselfelder

Direkter Zugriff

Erschöpfendes Aufzählen nach Schlüsselwert

Reihenfolge nach Werten d. Schlüsselfelder

Iteration über die Datensätze in auf- oder absteigender Sortierreihenfolge

10



BallenBallen

11


GrundgedankeKriterium Zugriffspfad Zugriff


Reihenfolge Iterieren (scan) über alle Datensätze:. Operation first für den Zugriff auf den ersten, next für den Zugriff auf den folgenden Datensatz.

Position Positionsbestimmung Direkter Zugriff

Einzelner Schlüsselwert Werte der Schlüsselfelder Direkter Zugriff

Kombinierte Schlüsselwerte Werte der Schlüsselfelder Direkter Zugriff


Reihenfolge nach Werten der Schlüsselfelder


Ziel: Minimierung der Zahl der Seitenzugriffe bei erschöpfendem Aufzählen (Iterieren).

Ansatz Ballen (auch: Bündeln, engl.: clustering): Ablage von gemeinschaftlich benötigten Datensätzen auf der selben Seite Mehrere Datensätze mit 1 Seitenzugriff.

Geballte Seiten werden nicht selbst noch einmal geballt. Eigener Zugriffspfad auf Seitenebene, z.B. Verkettung der

Seiten oder Nummern aller Seiten auf der ersten Seite.

12


Geballte Listen

P123 P204 P317

P123

Liste aller Seiten

Datensätze dieser Seite

Länge des Datensatzes

Freispeicher am Ende der Seite

P204 P317

5 24 Satz 1

12 Satz 2

28 Satz 3

8 Sa

tz 4 24 Satz 5

4 32 Satz 6

64

Satz 7

20

Satz 8

8 Satz 9

5 22

Satz 10

24 Satz 11

8 Sat

z 12 16 Satz 13

8

Satz 14

Speicherung entsprechend geforderter Reihenfolge

13


Einfügen eines Datensatzes: Position beliebig: Es wird die letzte Seite ausgewählt oder die

erste Seite, die genügend freien Speicherplatz besitzt. Position nach Eingangsreihenfolge: Es wird die letzte Seite

ausgewählt.

Sequenzielle Zugriffe auf die Datensätze erfolgen entsprechend ihrer physischen Reihenfolge.

Direkte Zugriffe über die Position sind möglich, sofern im Kopf der ersten Seite die Nummern aller Seiten samt Satzanzahl vermerkt sind.

Modifikationen mit Satzverlängerung in der Mitte einer Zugriffsstruktur kann u.U. Verschiebungen von Datensätzen zur Folge haben. Diese können bei „Position nach Eingangsreihenfolge“ zahlreiche Seiten betreffen.

Unsortierte geballte Listen

14


Wertbasierter Zugriff auf Datensätze: Suche eines Datensatzes kann durch Binärsuche erfolgen,

sofern in der ersten Seite die Nummern der Seiten sortiert vermerkt sind.

Ansonsten muss im Mittel die Hälfte der Datensätze besucht werden; aufgrund der Ballung benötigt man hierzu jedoch nur N / (2B) Seitenzugriffe, wobei N die Anzahl der Datensätze und B die mittlere Anzahl von Datensätzen pro Seite (Blockungsfaktor) ist.

Vorteile auch bei relationalen Operatoren, für die es bei Sortierung besonders effiziente Algorithmen gibt: Join-Operation. Filterung einer Datei (Selektion von Datensätzen, die ein

Selektionsprädikat erfüllen).

Sortierte geballte Listen

15


Einfügen eines Datensatzes: Es wird anhand des Sortierkriteriums die Seite ermittelt, in

die der Datensatz eingefügt werden soll. Falls auf der Seite genügend freier Platz ist, wird der

Datensatz eingefügt. Falls nicht, wird untersucht, ob die Vorgänger- oder Nachfolgerseite genügend Platz hat. Ist dort auch kein Platz vorhanden, wird eine neue Seite allokiert und in die Liste eingefügt.

Die Seiten können entweder soweit wie möglich gefüllt werden, oder beim initialen Anlegen jeder Seite wird ein bestimmter Anteil (0) freigelassen, um (über eine gewisse Zeit) das Einfügen neuer Datensätze und das Vergrößern der Datensätze auf der Seite zu beschleunigen.


16


Einfügen eines Datensatzes: Beispiel mit 0 0,5: Neuverteilung der Sätze auf übergelaufenen und neu

allokierten Satz. Bei Seitenverkettung geringer Aufwand, um neue Seite an

der richtigen Stelle einzufügen.


S1 < S2< … < Sk Sk+1 < … < Sneu < … < S2k

alter Knoten neuer Knoten

S1 < S2< … < Sk < Sk+1 < … < S2k

Sneu

17


Entfernen eines Datensatzes:

Gebe minimalen Füllgrad min (0,5) für die Seiten vor.

Falls nach Entfernen Füllgrad min fertig.

Andernfalls Knoten-Unterlauf: Es wird versucht, Datensätze aus einer der Nachbarseiten in

den Knoten mit Unterlauf zu verschieben.

Misslingt, wenn für beide Nachbarseiten = min. In diesem Fall wird die Unterlauf-Seite mit einer ihrer

Nachbarseiten verschmolzen. Die frei werdende Seite wird an die Seitenverwaltung

zurückgegeben.


18


Aufgabe: Erschöpfendes Aufzählen nach Position, wenn die physische Satzablage durch Ballen nach einem anderen Zugriffspfad bereits festliegt.

Lösung: Eingebetteter Zugriffspfad: Zugriffspfad ist unmittelbarer Bestandteil der Datensätze. Er wird dort durch Stellvertreter für die Datensätze

repräsentiert. Datensätze erhalten spezielle Felder mit Verweisen auf die

Vorgänger / Nachfolger in der Ordnung. Optionen bei der Verkettung:

Einfache Verkettung: Nur ein Zeiger auf Nachfolger. Doppelte Verkettung: Zeiger auf Vorgänger und Nachfolger. Ring: Letzter Datensatz verweist wieder auf den ersten

Datensatz, bei doppelter Verkettung verweist Vorgängerzeiger des ersten Datensatzes auf den letzten.

Eingebetteter Zugriffspfad

19


Zusätzliche eingebettete Zugriffspfade

P123 P204 P317

Satz 1

Satz 2

Satz 3

Kopf Liste 1 Kopf Liste 2

Aufprägen beliebig vieler zusätzlicher Zugriffspfade Bei einer Multiliste enthalten die Datensätze eine

Kettungsstruktur für jede Ordnung der Datensätze außerhalb der Ballung.

20



Assoziativer Zugriff durch AdressrechnenAssoziativer Zugriff durch Adressrechnen

21


Grundgedanke

Kriterium Zugriffspfad Zugriff









Ziel: Direktzugriff nach Schlüsselwert unter Vermeiden jeglichen weiteren Zugriffs.

Lösung Assoziativer Zugriff Berechnung der Satzadresse aus Inhaltsbeschreibung.

22


Kapitel 6.3.1Kapitel 6.3.1

Hash-FunktionHash-Funktion

23


Transformation eines kennzeichnenden Wertes (Schlüssel) in eine intern kontrollierte, logische Adresse.

Die Transformationsfunktion wird als Hash-Funktion bezeichnet.

S: Schlüsselraum (Menge aller möglichen Schlüsselwerte einer Satzmenge).

N: Intervall der natürlichen Zahlen von 1 bis n (logischer Adressbereich).

h: S N Hash-Funktion total.

Hashverfahren: Grundprinzip

24


Mit dem aus dem Schlüssel berechneten Hashwert kann – im Idealfall – direkt ohne weitere Hilfsstrukturen auf den gesuchten Datensatz zugegriffen werden.

Abweichung vom Idealfall: Sei Kt die Menge der zu einem Zeitpunkt t benutzten Schlüssel Kt S, |Kt| |S|

Wirtschaftlich nur N |Kt|

Zudem starke Ungleichverteilung von Kt in S möglich.

Dann ist h nicht injektiv:

k, k' Kt sind synonym h(k) = h(k') Kollision: Aufeinandertreffen synonymer Schlüssel.

Zahlreiche Verfahren unterschiedlicher Leistungsfähigkeit zur Kollisionsbehandlung bekannt.

Hashverfahren im Hauptspeicher

25


Gute Speichernutzung: Mehrere Synonyme pro Seite Synonyme werden unsortiert, Position beliebig geballt. Daher: N: Intervall von Seitennummern; h(k): Seite für

Datensätze mit Schlüsselwert k.

Hier Kollision: k und k' sind synonym, und h(k) ist bereits voll.

Ziel: Anzahl der Seitenzugriffe nahe 1. Daher auch hier Kollisionen unerwünscht. Gesucht: Hash-Funktion, die stets eine gute Ausnutzung des

Speicherraums N und eine gleichförmige Seitenbelegung garantieren soll.

Aus wertbasierter Satzmengensicht: gestreute Satzplatzierung.

Hashverfahren bei DBS

26


Divisionsrestverfahren (Restklassenbildung): k S: Bitdarstellung als ganze Zahl interpretiert h(k) = k mod q, q größte Primzahl |N| Es sollte gelten:

q a bn c (a, c kleine ganze Zahlen, b Zahlensystem des Rechners),

q soll also nicht nahe einer Potenz des Zahlensystems liegen (z.B. q 127), weil sonst die niedrigen Stellen des Schlüssels zu stark ins Gewicht fallen.

Faltung:

1. Zerlegung von k in einzelne Bestandteile2. Deren Verknüpfung additiv, multiplikativ oder logisch 3. Auswahl von t Bitpositionen aus dem Ergebnis, wobei 2t = |N|

Hash-Funktion

27


Empfohlen: Divisionsrestverfahren, evtl. kombiniert mit Faltung. Beispiel: Faltung mit XOR und Divisionsrestverfahren modulo 5 Beispieldatei und Hashwerte für Schlüsselfeld Color:

Hash-Funktion

Cubindex Cuboid Color Pointer

10 “yellow“ 20 “red“ 30 “brown“ 40 “black“ 50 “white“ 60 “green“ 70 “gray“ 80 “blue“ 90 “rose“

Hashwert

410 MOD 5 = 4 11510 MOD 5 = 0 10210 MOD 5 = 2

10310 MOD 5 = 3 10310 MOD 5 = 3 12310 MOD 5 = 3

1310 MOD 5 = 3 3010 MOD 5 = 0 1110 MOD 5 = 1

r 0111 0010e 0110 0101d 0110 0100 0111 0011 =115

„Schlechte“ Wahl von

q!

28


Einige weitere Verfahren: Tabellentransformation: Schlüssel wird zunächst byteweise mit

Hilfe einer Tabelle mit „zufälligen“ Zeichenkombinationen umgesetzt, um Regelmäßigkeiten zu „zerstören“.

Basistransformation: Schlüssel wird zunächst als Ziffernfolge einer anderen Basis dargestellt (bei num. Schlüsseln!). Danach wieder Divisionsrestverfahren.

Codierungsmethode: Schlüssel mit n Bits Länge wird aufgefasst als Polynom vom Grad n –1 (die Bits stellen die Koeffizienten dar). Polynom wird durch Polynom vom Grad t geteilt. Der verbleibende Rest (Polynom von Grad t –1) wird als Hashadresse interpretiert. Verfahren kann mit Fehlererkennung kombiniert werden.

Zufallsmethode: Erzeugung der Hashadresse über Zufallszahlengenerator, mit Schlüssel als „Saat“.

Hash-Funktion

29



Statische Hash-VerfahrenStatische Hash-Verfahren

30


Hash-Bereich N und damit h liegen fest. Forderungen an h: Gleichförmige Schlüsselverteilung: Jede Seite soll etwa

dieselbe Zahl unterschiedlicher Schlüsselwerte als Urbilder besitzen.

Gleichförmige Satzverteilung: Jede Seite soll etwa dieselbe Zahl an Sätzen aufnehmen.

Operationen: Suche: Berechne h(k), evtl. Suche gemäß

Kollisionsauflösung. Einfügen: Berechne h(k), evtl. Kollisionsauflösung. Löschen: Suche, dann Entfernen, evtl. Bereinigung. Statische Reorganisation.

Charakterisierung

Problem:Man kennt nur S, nicht aber Kt .Bei Ungleichverteilung widersprechen sich die Forderungen.

31


Überlaufbehandlung von Seiten: Auflösung innerhalb des Hash-Bereichs:

Offene Adressierung: Lineares und quadratisches Sondieren Auflösung durch getrennte Überlaufbereiche:

Verkettung mit zusätzlichen Seiten außerhalb Hash-Bereich. Globalen Überlaufbereich vermeiden!

Kollisionsminderung nach Löschvorgängen: Dynamische Reorganisation:

aufwendig, hält aber Zahl der Seitenzugriffe klein. Setzen von Löschmarken und periodische statische

Reorganisation: weniger aufwendig, Zahl der Seitenzugriffe wächst jedoch bis zur Reorganisation.

Kollisionsbehandlung

32


|N|=5, Seitenkapazität = 3

Getrennter lokaler Überlaufbereich

Beispiel für Überlaufseiten (1)



Hashwert410 MOD 5 = 4

11510 MOD 5 = 010210 MOD 5 = 210310 MOD 5 = 3

10310 MOD 5 = 312310 MOD 5 = 31310 MOD 5 = 3

3010 MOD 5 = 01110 MOD 5 = 1

33


Beispiel für Überlaufseiten (2)

1

„black“40 „white“50 „green“60

„yellow“10

„brown“30

„rose“90

„red“20 „blue“80

0

2

3

4

Seitennummer

„gray“70


11510 MOD 5 = 010210 MOD 5 = 210310 MOD 5 = 3

10310 MOD 5 = 312310 MOD 5 = 31310 MOD 5 = 3

3010 MOD 5 = 01110 MOD 5 = 1

34


Überlaufbehandlung von Seiten: Auflösung innerhalb des Hash-Bereichs:

Offene Adressierung: Lineares und nichtlineares Sondieren Auflösung durch getrennte Überlaufbereiche:

Verkettung mit zusätzlichen Seiten außerhalb Hash-Bereich. Globalen Überlaufbereich vermeiden!

Kollisionsverminderung nach Löschvorgängen: Dynamische Reorganisation:

aufwendig, hält aber Zahl der Seitenzugriffe klein. Setzen von Löschmarken und periodische statische

Reorganisation: weniger aufwendig, Zahl der Seitenzugriffe wächst jedoch bis zur Reorganisation.

Kollisionsbehandlung

35


Sondieren (1)

Für einen Schlüssel k wird überprüft, ob die Seite g(k,0) = h(k) noch über Platz verfügt. Ist dies nicht der Fall, so berechnet man Seiten g(k,1),

g(k,2),... und untersucht diese.

Beim linearen Sondieren ist g(k,i)=(h(k)+ic) mod q,(c eine Konstante, beispielsweise c=1)

Bei hoher Kollisionsrate hoher Aufwand bei Platzierung und Suche!

36


Sondieren (2)

1

„black“40 „white“50 „green“60

„yellow“10

„brown“30

„rose“90

„red“20 „blue“80

0

2

3

4

Seitennummer

„gray“70


11510 MOD 5 = 010210 MOD 5 = 210310 MOD 5 = 3

10310 MOD 5 = 312310 MOD 5 = 31310 MOD 5 = 3

3010 MOD 5 = 01110 MOD 5 = 1

Kann Quelle von Sekundärkollisionen

werden!

37


Ziel: Auch bei Überlauf nur 1 Seitenzugriff.Skizze des Verfahrens (Härder/Rahm, S. 194-199): Satz mit Schlüssel k habe die Sondierungsfolge g(k,0) (=h(k)),

g(k,1), ..., g(k,n). Erzeuge dazu gleichverteilte Signaturfolge s0(k), s1(k), ..., sn(k).

(Signatur: Bitfolge fester Länge). Jeder Seite j ist dynamischer Separator SEP(j) zugeordnet. Suche: Sondiere bis si(k)<SEP(g(k,i)).

Seite enthält gesuchten Satz. Liste der Separatoren im Hauptspeicher, daher erfolgt dort der

Vergleich nur 1 Seitenzugriff! Einfügen: Lokalisiere Seite wie bei der Suche.

Seite nicht voll: Einfügen. Seite voll: Verschiebe Satz mit höchster Signatur (mehrere bei

identischer Signatur, kann auch der aktuelle Satz sein): Kaskadieren möglich!

Setze SEP(g(k,i)) auf niedrigste abgewiesene Signatur.

Anpassbares Sondieren mit Separatoren

38


Wahl von Hash-Algorithmus und Überlaufbehandlung kritisch: Beeinflusst von konkreter Anwendung (Ladereihenfolge!) und

Seitenkapazität Standardverfahren schwierig! Such- oder Einfügeaufwand steigt stark an, sobald |Kt| in die

Nähe von |N|Seitenkapazität kommt. Jedoch: Zugriffsfaktor < 1.5 von keiner anderen

Zugriffstruktur zu schlagen. Abhilfen: Große Wahl von |N| schon von Anfang an

(Platzverschwendung zu Beginn oder - bei Nichteintreten des erwarteten Wachstums - auf Dauer).

Statische Reorganisation mit völliger Neuverteilung der Adressen (sehr hoher Zeitbedarf, längere Betriebsunterbrechung, Anpassen unzähliger Verweise).

Dynamische Verfahren.

Bewertung

39



Dynamische Hash-VerfahrenDynamische Hash-Verfahren

40


Skalierbarkeit: Zugriffsfaktor 2 unabhängig von |Kt|.

Zahl der zur Verfügung stehenden Seiten wird kontinuierlich dem aktuellen Bedarf angepasst.

Hoher Belegungsfaktor unabhängig vom Wachstum der Schlüsselmenge.

Ziele

41


Grundidee: Statt einer einzigen Hash-Funktion h: S N eine Familie von Hash-Funktionen hi: S {0,...,2iN-1}, i{0,1,2,...}. Bedingungen (h0(k){0,1,2,..., N-1}):

hi+1(k) = hi(k) für etwa die Hälfte der kS.

hi+1(k) = hi(k)+ 2iN für die andere Hälfte.

Beispielsweise erfüllt für hi(k):=kmod(2iN)

Zu jedem Zeitpunkt sind für einen Hash-Bereich höchstens zwei „benachbarte“ Hash-Funktionen zuständig.

Parameter für die aktuelle Speicherung: Level lv: „unteres“ i.

Split-Zeiger sp auf die nächste zu teilende Seite.

Lineares Hashing

42


Lineares Hashing

105 111 512 413 144

790 076 477 243

335 837 888

995 002

lv=0, N=5, max.Blockung=40 1 2 3 4

sp

Primärbereich

Überlaufseiten055 117

h0 h0 h0 h0 h0

Vergrößern des Speicherbereiches:Füge neue Seite am Ende an;Verteile Sätze auf Seite sp gemäß hlv+1 auf alte und neue Seite;sp:=sp+1;if sp= 2lvN then {lv:=lv+1; sp:=0}

43


h1 h0 h0 h0 h0 h1

sp

0 1 2 3 4 5

Lineares Hashing

105 111 512 413 144

790 076 477 243

335 837 888

995 002

lv=0, N=5, max.Blockung=40 1 2 3 4

sp

Primärbereich

Überlaufseiten055 117

h0 h0 h0 h0 h0

010

790 111 512 413 144 105

010 076 477 243 335

837 888 995

002 055

117

44


h1 h0 h0 h0 h0 h1

sp

0 1 2 3 4 5

Lineares Hashing

790 111 512 413 144 105

010 076 477 243 335

837 888 995

002 055

117

Suchen nach Schlüssel k:s:= hlv(k);if s < sp then s:= hlv+1(k);// Seite schon gesplittet, daher neue Hash-Funktion anwenden //

Beispiel: k=790

45


Da der Reihe nach gesplittet werden muss, werden u.U. Seiten mit niedrigem Füllgrad gesplittet.

Überlaufseiten werden nicht vermieden und u.U. zu spät beseitigt.

Split-Kriterium liegt nicht fest und belässt Spielräume einschließlich raschem Fortbewegen des Split-Zeigers.

Gesucht: Verfahren, das diese Probleme umgeht. Bringt ein Index etwas?

Bewertung

46



Index-VerfahrenIndex-Verfahren

47


GrundgedankeKriterium Zugriffspfad Zugriff









…

Indexteil mit Wegweisern

Satzmenge physisch gespeichert nach eigenständigem Verfahren (Ballung, Adressrechnung)

48



ZeigerfelderZeigerfelder

49


ZeigerfeldP123 P204 P317

Satz 1

Satz 2

Satz 3

Das Zeigerfeld (Pointer Array) enthält für jeden Datensatz einen Eintrag („Stellvertreter“) mit einem Verweis auf den Datensatz.

Das Zeigerfeld bildet einen eigenen Datensatz. Falls es größer als eine Seite wird, wird es als großer Datensatz verwaltet.

50


Die Anordnung der Stellvertreter kann unabhängig von der Anordnung der Datensätze gewählt werden z.B. Aufprägen einer logischen Ordnung auf eine physische (geballte) Ordnung.

Zugriff über Zeigerfeld: Aufwand fest 2 Seitenzugriffe. Sequenzielle Zugriffe: Aufgreifen der Verweise der Reihe

nach. Direkte Zugriffe über die Position. Eine (zusätzliche) Sortierung der Datensätze wird durch eine

entsprechende Sortierung der Einträge des Zeigerfeldes hergestellt.

Suche eines Datensatzes über Binärsuche auf Zeigerfeld, ansonsten sequenzielles Durchsuchen.

Suche kann beschleunigt werden, wenn zu jedem Verweis der Schlüssel des entsprechenden Datensatzes in dem Zeigerfeld gespeichert wird.

Zeigerfeld

51


Multizeigerfeld

Bei einem Multizeigerfeld existiert ein Zeigerfeld für jeden Zugriffspfad.

P123 P204 P317

Satz 1

Satz 2Satz 3

52



Erweiterbares HashingErweiterbares Hashing

53


Grundgedanke

…


Platzierung der Sätze gemäß Adressrechnung

1-stufig

Gezieltes Splitten an der Bedarfsstelle

Untersetzung des Seitenwachstums in Indexwachstum

Bestimmung der Einträge mittels

Adressrechnung Gruppierung

54


1. Berechne Hashwerte h(k) (Pseudoschlüssel) für die Schlüssel k.

2. Gruppierung: Fasse diejenigen Pseudoschlüssel zusammen, die in den niedrigsten d' Bits übereinstimmen, derart, dass diese Pseudoschlüssel auf eine Seite passen (lokale Tiefe, für verschiedene Seiten u.U. verschieden).

3. Bestimme d = max(d') über alle Seiten (globale Tiefe).

4. Lege Index mit Einträgen für die Bitfolgen der Länge d an.

5. Läuft eine Seite über, setze deren d' um 1 herauf, verteile alten Seiteninhalt über zwei Seiten.

6. Falls d dadurch um 1 wächst, lege neuen Index mit doppelter Zahl von Einträgen an.

Vorgehensweise

55


Beispiel




11510 MOD 5 = 010210 MOD 5 = 210310 MOD 5 = 3

10310 MOD 5 = 312310 MOD 5 = 31310 MOD 5 = 3

3010 MOD 5 = 01110 MOD 5 = 1

Hashwert000001002

011100112

011001102

011001112

011001112

011110112

000011012

000111102

000010112

56


Annahme: Seitenkapazität = 3 Datensätze.

Beispiel

“red“20 “green“60 “rose“90

“gray“70

“yellow“10 “brown“30 “blue“80

“black“40 “white“50

dynamische Grenzlinie

*0

*1 *01

*11*011

*111

57


Beispiel


“gray“70



dynamische Grenzlinie

*0

*1 *01

*11*011

*111

1

2

3

3

seiten-lokale Tiefe

*111

*011

*01

*0

58


Beispiel


“gray“70



1

2

3

3

seiten-lokale Tiefe

*111

*011

*01

*0globale Tiefe 3

*000

*001

*010

*100

*101

*110

*111

*011

59


Beispiel


“gray“70



1

2

3

3

seiten-lokale Tiefe

*111

*011

*01

*0globale Tiefe 3

*000

*001

*010

*100

*101

*110

*111

*011

Einfügen des Datensatzes [11, “yellow“, ]: Seite ist voll, und

lokale Tiefe < globale Tiefe„normales“ Spalten der Seite.

60


Beispiel


“gray“70

“brown“30 “blue“80


2

*10

2

*01

3

3

*011

*000

*001

*010

*100

*101

*110

*111

globale Tiefe 3

*011

“yellow“10 “yellow“11

2

*00

*111

Einfügen des Datensatzes [21, “red“, ]: Seite ist voll, und lokale Tiefe =

globale Tiefe Spalten der Seite + Verdopplung

der Zwischentabelle

61


“red“20 “red“21

Beispiel

“green“60 “rose“90

“gray“70

“brown“30 “blue“80


“yellow“10 “yellow“11

*1001*1000

*1011*1010

*1101*1100

*1111*1110

*0001*0000

*0011*0010

*0101*0100

*0111*0110

2*10

2*01

4

3

2

*00

*0011

*1011

4

*111

globale Tiefe 4

62



BB++-Baum-Baum

63


Grundgedanke

B-Baum

B+-Baum: Kombination der beiden folgenden Strukturen

…

Sortierte geballte Liste mit Doppelverkettung der Seiten in Sortierordnung Effizienter

sequentieller Zugriff in Sortierreihenfolge

Effizienter direkter Zugriff nach Schlüssel

gleicher Schlüssel vorausgesetzt

64


Ziel: Anzahl der Seitenzugriffe auch bei unbekanntem Zugriffsverhalten gering halten.

Vorgehensweise: Schrittweise und zugleich starke Begrenzung des Suchbereichs. Führt auf Baumstruktur.

Forderung: Alle für DB-Zugriff relevanten baumstrukturierten Organisationsformen müssen für Seitenstrukturen konzipiert sein.

Umsetzung: Jeder Schritt beinhaltet einen Zugriff auf eine Seite, auf der dann eine große Zahl von Suchschritten im Hauptspeicher vollzogen werden (Wiederholte Ballung!). 1:1-Zuordnung von Knoten des Baums und Seite.

Baumförmige Anordnungen

65


Sei s Zahl der Wahlmöglichkeiten pro Seite und N die Gesamtzahl der Sätze. Dann ist die Anzahl der Seitenzugriffe beim Fortschreiten in einem ausgewogenen Baum O(logs(N)).

Damit bei direktem Zugriff nur auf wenige Seiten zugegriffen werden muss, ist ein sehr hoher Verzweigungsgrad der Wurzel und der internen Knoten anzustreben. s = 2 Binärbaum

Ziel: s > 100 Mehrwegbaum

Wahl von 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.

Mehrwegbäume

66


Wähle Separatorschlüssel SS so dass

alle Schlüssel SS alle Schlüssel > SS

B-Baum (1)

B-Baum

…

Baue Index auf den Separatorschlüsseln

auf

67


Beispiel

(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

68


Anfragearten

S

S S

…

S

Exact Match Queries (EMQ):select A1,A2,...,Anfrom Rwhere Ai = c

Range Queries (RQ):select A1,A2,...,Anfrom Rwhere Aic2 and Aic1

B+-Baum deckt beide Arten gleichzeitig sehr gut ab.

69


Interessenskonflikt: Geringer Zugriffsaufwand:

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.

Geringer Änderungsaufwand: Keine hohen Anforderungen an Balance und/oder Füllgrad.

Kompromisslösung erforderlich: Wiederherstellen der Balance und/oder eines hohen Füllgrads

sollte auf einen möglichst kleinen Teil des Baums begrenzt bleiben.

Leistungsbetrachtung

70


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 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 (Separator-) 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.

B-Baum (2)

71


Aufbau eines Knotens:

Interne Struktur der Knoten

Z0 S1 Z1 S2 … Sn Zn frei

Wegweiser Sohnzeiger

In den Blattknoten verweisen die Sohnzeiger auf die Seiten einer außerhalb des Baumes

geführten sortierten geballten Liste.

Annahme: Die sortierte geballte Liste wird nach dem früher beschriebenen Seitensplit-Verfahren verwaltet.Charakterisierung durch Konstante k*: Jede Seite enthält mindestens k* und höchstens 2k* Datensätze.

72


Beispiel:

Beispiel


10 20 30 40 50 60 70 80 90

“yellow“ “red“

“brown“ “black“ “white“ “green“

“red“ “blue“

“yellow“

Schlüssel (eindeutig)

Datensätze(Annahme: gleiche, unveränderliche Länge)

73


Beispiel

Annahme: k=2, k*=1

10 ...

25 45 65 75

20 ... 30 ... 40 ... 50 ... 60 ... 70 ... 80 ... 90 ...

Strukturelle Sicht: Separator

Zugriffssicht: Wegweiser

Höhe h eines B+-Baums mit N Datensätzen:

)2( log22

log1 112

h

k

Nh

k

Nkk

Höhe(B-Baum) = 1)Höhe(B+-Baum) = 2)

74


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 hoher Verzweigungsgrad notwendig. Verzweigungsgrad ist von k abhängig, k von der

Schlüssellänge! Errechne sich die maximal mögliche Zahl der Einträge pro Seite zu m. Dann ist k = (m/2).

Bei gegebenem k ist Verzweigungsgrad vom Füllgrad der Datenseiten und Blattknoten abhängig.

Baumhöhe

Höhe h eines B+-Baums mit N Datensätzen:

)2( log22

log1 112

h

k

Nh

k

Nkk

75


Obere Grenze für die Anzahl der Knoten, die schlimmstenfalls in Abhängigkeit von der Knotengröße und der Anzahl der Datensätze zu lesen sind:

Abschätzung der Baumhöhe

Größe einesKnotens (2k)

Anzahl der Datensätze

103 104 105 106 107

10 3 4 5 6 750 2 3 3 4 4100 2 2 3 3 4150 2 2 3 3 4

76


Suche

10 ...

25 45 65 75

20 ... 30 ... 40 ... 50 ... 60 ... 70 ... 80 ... 90 ...

suche (s);seite p := wurzel;do

eintrag := 0; while s > eintrag.separator and eintrag < Zahl der Einträge do eintrag+;if eintrag = Zahl der Einträgethen p := letzter Zeiger auf Seiteelse p := eintrag.zeiger;

until p verweist auf Seite mit Datensatz;end suche; // p verweist auf Seite mit Satz mit Schlüssel s //

77


Neubalancierung durch Wachstum nach oben

Einfügen eines neuen Datensatzes erfordert 2 Phasen:

1. Suche mit dem Schlüssel des neuen Datensatzes.

2. Falls (gefunden und Schlüssel nichteindeutig) oder falls nicht gefunden: Einfügen des neuen Datensatzes in die Ergebnisseite der Suche.

Falls die Seite überläuft, wird sie gespalten. Dabei wird ein neuer Separator-Schlüssel bestimmt und in den

Indexbaum eingefügt. Hierbei kann es zu einem weiteren Überlauf kommen. Dann wird

auch der Indexknoten gespalten, ein Separator-Schlüssel bestimmt, und das Verfahren setzt sich u.U. mehrfach nach oben fort.

Wenn sogar die Wurzel überläuft, wird auch sie gespalten mit der Folge: Der Baum wächst in der Höhe um 1.

Einfügen eines Datensatzes

78


Beispiel

10 ...

25 45 65 75

20 ... 30 ... 40 ... 50 ... 60 ... 70 ... 80 ... 90 ...

Einfügen eines Datensatzes mit Schlüssel 74:

74 ...

74 ...

k=2, k*=1

79


Beispiel

10 ...

25 45 65 75

20 ... 30 ... 40 ... 50 ... 60 ... 70 ... 80 ... 90 ...


74 ...

51 ...

Überlauf

k=2, k*=1

80


Beispiel

10 ...

25 45 65 75

20 ... 30 ... 40 ... 50 ... 51 ... 70 ... 80 ... 90 ...


74 ...

60 ...

Neuer Separator:55

Überlauf

k=2, k*=1

81


Beispiel

10 ...

65 75

20 ... 30 ... 40 ... 50 ... 51 ... 70 ... 80 ... 90 ...


74 ...

60 ...

25 45

55

k=2, k*=1

82


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 Zugriffsstrukturen verwalten) gespeichert.

Wie kann man vermeiden, dass beim Spalten der Wurzel sehr viele (unbekannte) Verweise ersetzt werden müssen? Die Seite zur Aufnahme der Wurzel bleibt über die gesamte

Lebensdauer eines B+-Baums erhalten. 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.

Spalten der Wurzel

83


P123

Spalten der Wurzel

P401 P532

P123

84


Das Entfernen von Datensätzen beginnt immer in der geballten Liste.

Entfernen ohne weitere Auswirkung: Index nicht betroffen. Entfernen mit Satzverschiebung (z.B. bei Ausgleich):

Wähle neuen Separatorschlüssel. Ersetze alten Separatorschlüssel durch neuen überall wo er

im Baum vorkommt. Entfernen mit Verschmelzen von Seiten:

Entferne alten Separatorschlüssel aus dem entsprechenden Blattknoten.

Gelegentlich kann dies dort einen Unterlauf bewirken. Insbesondere kann sich das Verschmelzen von Knoten bis zur

Wurzel fortsetzen. Folge: Der Baum schrumpft in der Höhe um 1.

Entfernen von Datensätzen

85


Beispiel

10 ...

65 75

20 ... 30 ... 40 ... 50 ... 51 ... 70 ... 80 ... 90 ...

Entfernen eines Datensatzes mit Schlüssel 60:

74 ...

60 ...

25 45

55

k=2, k*=1, Annahme min 0,5 X Unterlauf

86


Beispiel

10 ...

65 75

20 ... 30 ... 40 ... 50 ... 51 ... 70 ... 80 ... 90 ...


74 ...

25 45

55

k=2, k*=1, Annahme min 0,5

X

Unterlauf

X

87


Beispiel

10 ...

55 75

20 ... 30 ... 40 ... 50 ... 51 ... 70 ... 80 ... 90 ...


74 ...

25 45

k=2, k*=1, Annahme min 0,5

88


min < 50% kann sinnvoll sein:

Da Einfügen gegenüber Entfernen dominiert, belässt man es beim Löschen des Satzes.

Spalten mit Vorausschau: Spalte so, dass zukünftige Einfügungen von Datensätzen möglichst gleichmäßig auf die beiden durch den Separatorschlüssel getrennten Teilbäume verteilt werden.

Geringere Füllgrade (1)

89


Geringere Füllgrade (2)

20 21 22 23 24 9019 20 21 22 23 24 90

22

19

Einfügen von „19“, k=3. Vergleiche:

Schlecht falls Gleichverteilung der Schlüssel, da sich sehr viele Datensätze im rechten Teilbaum ansammeln werden, so dass dort sehr viele Spaltungen vorkommen werden.

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.

20 21 22 23 24 90 20 21 22 23 24 90

55

19 19

90


Verallgemeinerung

…

Physikalisch beliebig gespeicherte Satzmenge

B-Baum

…Sortierte geballte Stellvertreter-Liste

mit Doppelverkettung der Seiten

Aufgabe: Aufprägen eines weiteren Schlüssels

B*-Baum: Kombination der Strukturen

B+-Baum

91


Begriffe: B-, B+- und B*-Baum

Vorsicht: Die Begriffe werden in der Literatur sehr uneinheitlich verwendet.

Die hier verwendete Terminologie dient der klaren Abgrenzung, weicht aber von einem Teil der Literatur ab.

92


Zur Erinnerung: Höhe h bestimmt Performanz. h hängt von Verzweigungsgrad ab, Verzweigungsgrad ist

proportional Füllgrad β. Füllgrad ist bei jeder Seite außer Wurzel: β min, üblich min =

50%. Ungünstigster Fall: Sequenzielles Laden der geballten Liste

sortiert nach auf- oder absteigenden Schlüsseln: β = 50%. Mittlerer Füllgrad bei zufälligem Einfügen und Löschen: β = 69%.

Verbesserung durch Verzögerung des Spaltens von Seiten: 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 der Höhe (1)

93


Zur Erinnerung: Höhe h bestimmt Performanz. h hängt von Verzweigungsgrad ab, Verzweigungsgrad ist

proportional Wert von k.

Vergrößerung von k durch Vergrößerung der Seitengröße. Seitengröße selten beeinflussbar.

Vergrößerung von k bei unveränderter Seitengröße: Einsatz von Verfahren zur Schlüsselkomprimierung.

Beeinflussung der Höhe (2)

94


Separatorschlüssel muss automatisch bestimmt werden können:

Übernahme aus den Datensätzen: Üblich ist die Verwendung des höchsten Schlüssels auf der Seite.

Systematische Konstruktion von Separatoren minimaler Länge.

Kann mit Schlüsselkomprimierung kombiniert werden.

Wahl eines Separatorschlüssels

95


Zeichenkomprimierung durch Beseitigen von Redundanzen 1. Maßnahme: Entfernen führender Nullen und

abschließender Zwischenräume. 2. Maßnahme: Schlüsselvergleiche mit Weglassen der für die

Unterscheidung unerheblichen Teile.

Folge: Variable Schlüssellänge k variabel über Knotenmenge und zeitlich schwankend über

Knoten. Seiten-Spalten dann nicht mehr über Zahl der Einträge,

sondern nach der Speicherbelegung.

Schlüsselkomprimierung

96


Die Schlüssel einer Seite werden fortlaufend komprimiert derart, dass nur der Teil des Schlüssels

vom Zeichen, in dem er sich vom Vorgänger (Position V) unterscheidet,

bis zum Zeichen, in dem er sich vom Nachfolger (Position N) unterscheidet,

zu übernehmen ist (front and rear compression).

Eintrag enthält Anzahl F = V – 1 der Zeichen des Schlüssels, die mit

Vorgänger übereinstimmen (erster Eintrag: F = 0) Länge L = max(N – V, 0) + 1 des komprimierten Schlüssels dazugehörige Zeichenfolge

Präfix-Suffix-Komprimierung

97


BeispielSchlüssel V N F L Komprimat PräfixCity_of_New Orleans 1 6 0 6 City_o City_oCity_to_City 6 2 5 1 t City_tCloset_Chronicles 2 2 1 1 l ClCocaine 2 3 1 2 oc CocCold_as-Ice 3 6 2 4 ld_a Cold_aCold_Wind_to_Walhalla 6 4 5 1 w Cold_wColorado 4 5 3 2 or ColorColours 5 3 4 1 u ColouCome_Inside 3 12 2 10 me_inside# Come_inside#Come_Inside_of_my_Guitar 12 6 11 1 _ Come_inside_Come_on_over 6 6 5 1 o Come_oCome_together 6 4 5 1 t Come_tComing_into_Los_Angeles 4 4 3 1 i ComiCommotion 4 4 3 1 m CommCompared_to_what? 4 3 3 1 p CompConclusion 3 4 2 2 nc ConcConfusion 4 1 3 1 f Conf

abgespeichert

Aufsuchalgorithmus (mit Kellermechanismus) kann zwar nicht die Schlüssel in ihrer Gänze, aber doch bis zur Eindeutigkeitslänge rekonstruieren.

98



Mehrdimensionale IndexeMehrdimensionale Indexe

99



VorüberlegungenVorüberlegungen

100


Wertbasierter Zugriff auf der Grundlage mehrerer Attribute, dies einzeln oder in beliebigen Kombinationen.

1. Exact Match Queryspezifiziert Suchwert für jede Dimension Di

2. Partial Match Query spezifiziert Suchwert für einen Teil der Dimensionen

3. Range Queryspezifiziert ein Suchintervall [ugi, ogi ] für jede Dimension

4. Partial Range Query spezifiziert ein Suchintervall für einen Teil der Dimensionen

Anfragearten

relation PERS (PNR, PNAME, ANR, GEBJAHR, ORT) Partial Match Query:

ANR =„K55“ GEBJAHR = 1945 ORT = „KA“ Partial Range Query:

GEBJAHR 1940 GEBJAHR 1950

101


Lösung mit eindimensionalen Indexen Erfordert Indexe auf Stellvertretersätzen.

Konjunktive Zerlegung von Anfragen in Einattributanfragen mit nachfolgender Schnittmengenbildung über den Stellvertretern.

Flexible Lösung auf der Grundlage von Standardverfahren. Performanz?

Mehrere eindimensionale Indexe

102


Wertebereiche D0,..., Dk-1:

alle Di sind endlich, linear geordnet und besitzen kleinstes (-i) und größtes (i) Element

Datenraum D = D0...Dk-1

k-dimensionaler Schlüssel entspricht Punkt im Datenraum, p D

Mehrdimensionale Datenstrukturen

103



Lineare EinbettungenLineare Einbettungen

104


Lineare Einbettungen

Bevorzugung von Range Queries: Linearisierung unter Bewahren mehrdimensionaler Nachbarschaftsverhältnisse.

Transformation von Mengen mehrdimensionaler Punktobjekte in eindimensionale Folge unter möglichst gutem Erhalten der topologischen Struktur. Anschließend Abbildung auf eindimensionale Struktur, z.B.

B*-Baum.

Möglichkeiten der Transformation: Partitionieren des Datenraums durch gleichförmiges Raster. Jede Zelle besitzt Nummer, die ihre Position in der linearen

Ordnung definiert. Definition der linearen Ordnung mittels eindimensionaler

Einbettung (space filling curve).

105


Wichtige Einbettungen

0

1

2

3

0

1

3

2

0

1

3

2

0

1

2

3

4

5

6

7

12

13

14

15

8

9

10

11

0

1

3

2

6

7

5

4

10

11

9

8

12

13

15

14

0

1

3

2

14

15

13

12

8

11

9

10

4

7

5

6

z-Ordnung Gray-Code Hilberts Kurve

0 1

3 2

Nummerierung: Kurvennummern gemäß Abfolge auf der Kurve

106


Beispiel Hilbert-Kurve

0

1

3

2

14

15

13

12

8

11

9

10

4

7

5

6

0 400

40

Index Kurvennummer Seitenadresse

Range-Query bzgl. dem Suchintervall [12, 38] x [1,29]

Zu lesende Kurvennummern: 2, 3, 4, 5, 6, 7, 8, 9 und 13

Es bieten sich daher folgende Suchschritte an:

1. Einstieg in Seite zu Kurvennummer 2 über Index

2. Dann lineares Lesen der Seiten zu 2 bis 9 über Listenverkettung

3. Einstieg in Seite mit Hilbertkurvennummer 13 über Index

107


Beispiel Z-Kurve

0

1

2

3

4

5

6

7

12

13

14

15

8

9

10

11

0 400

40

Index Kurvennummer Seitenadresse

Range-Query bzgl. dem Suchintervall [12, 38] x [1,29]

Zu lesende Kurvennummern: 2, 3, 6, 8, 9, 10, 11, 12 und 14

Es bieten sich daher folgende Suchschritte an:

1. Einstieg in Seite mit Z-Kurvennummer 2 über Index

2. Dann lineares Lesen der Seiten zu 2 und 3 über Listenverkettung

3. Einstieg in Seite mit Z-Kurvennummer 6 über Index

4. Dann lineares Lesen der Seiten 6 bis 14 über Listenverkettung

108



RaumstrukturenRaumstrukturen

109


Charakterisierung gemäß der Art der Aufteilung des Datenraums in Gebiete:

1. nur atomare Gebiete (beschreibbar durch ein Rechteck)

2. vollständig (die Vereinigung aller Gebiete ergibt den gesamten Datenraum)

3. disjunkt (die Gebiete überlappen nicht)

Charakterisierung

Grid-File (Gitter-Datei): atomar, vollständig, disjunkt

110






Charakterisierung

K-D-B-Baum: atomar, vollständig, disjunkt

111






Charakterisierung

R+-Baum: atomar, disjunkt

112






Charakterisierung

R-Baum: atomar

113






Charakterisierung

Z-B-Baum: vollständig,disjunkt

114


Varianten

Quad-Baum (1974)

KdB-Baum (1985)

Mehrdimensionaler B-Baum (1982)

Z-B-Baum (1982)

R+-Baum (1987)

Buddy-Hash-Baum (1989)

Grid-File (1984)

Ausführlicher Überblick bei Härder/Rahm Kap. 9

Indextechniken sind auch heute noch ein intensiv bearbeitetes Gebiet der (Datenbank-)Algorithmik mit anwendungsspezifischer Ausrichtung!

115



Gitter-Datei (Grid File)Gitter-Datei (Grid File)

116


Grundgedanke (1)

…


Platzierung der Sätze gemäß Raumpunktrechnung

1-stufig

Gezieltes Splitten an der Bedarfsstelle

Untersetzung des Seitenwachstums in in Breitenwachstum des Index

Bestimmung der Einträge mittels Raumpunktrechnung

Ansatz: Grundgedanke aus dem Erweiterbaren Hashing: Gleichförmige, dynamische Unterteilung des Schlüsselraums, um Zugriffsfaktor auf 2 zu begrenzen.

Datenseiten

117


Gitterbildung durch Einteilung der Achsen in Intervalle. Eine Partitionierung einer Dimension Di ist gegeben durch einen

Vektor, der die Einteilung in Intervalle definiert: Pi = (di,0, di,1,...,di,ki

) ::= [-i, di,0], (di,0, di,1],...,(di,ki, i]

Grundgedanke (2)

D1

d1,2

d1,1

d1,0

d0,0 d0,1 d0,2 D0d0,2

Gleichförmige Speicherplatzbelegung durch Anpassung des Gitters an die Dichte des Datenraums D = D0… Dk-1. Modifikation einer Gitter-Partition erfolgt durch Änderung

entlang einer Dimension (Spalten oder Zusammenlegen).

118


Menge von Seiten zur Speicherung von Datensätzen. Jede Seite kann bis zu c Sätze speichern.

Grid-File-Struktur

Katalogstruktur (Grid Directory): Repräsentation des Gitters. Zentrale Datenstruktur des Grid File.

Aufgabe: Definition und Wartung der dynamischen Beziehungen zwischen den Gitter-Gebieten des abstrakten Satzraums und den gespeicherten Sätzen auf den Seiten. Prinzip der zwei

Plattenzugriffe: KatalogSeiteD1

d1,2

d1,1

d1,0

d0,0 d0,1 d0,2 D0

119


Zuordnung von Seiten zu Gitter-Gebieten: Für eine gute Seitenbelegung erfolgt wie beim Erweiterbaren

Hashing eine n:1-Zuordnung zwischen Gitter-Gebieten und Seiten.

„Bereich“ von Seite B: Menge der Gitter-Gebiete, die B zugeordnet sind.

Seitenorganisation (1)

Seiten

Gitter-Gebiete (Gridblöcke)

120


Seitenorganisation (2)

121


Aufgabe des Katalogs: Darstellung und Verwaltung der dynamischen Beziehung zwischen den Gitter-Gebieten und den Seiten mit den gespeicherten Sätzen.

Struktur des Katalogs:

1.Grid-Matrix: dynamische, k-dimensionale Matrix, deren Einträge die Beziehung zwischen Gitter-Gebieten, Bereichen und Seiten regeln.

2. k ein-dimensionale Vektoren, die jeweils eine Unterteilung einer Dimension definieren.

Katalog-Struktur (1)

122


Katalog-Struktur (2)

Grid-Matrix

FIND(K55,KL)

AA

DA

FR

MK

ZZ

K00 K17 K39 K52 K89 K99

Seite

D1

D0

(K55,KL)

123


AA

ZZ

K99K00A

Seite

Seitenkapazität: 3 Einträge

Alternierende Spaltstrategie

Registrieren mittels eines k-dimensionalen Buddy-Systems

Einfügen und Löschen (1)

I(K54, DA)

A

Buddy-Anordnung

I(K02,AB)

I(K87,ST)

124


AA

ZZ

K99K00A

Seitenkapazität: 3 Einträge

Alternierende Spaltstrategie

Registrieren mittels eines k-dimensionalen Buddy-Baums

Einfügen und Löschen (2)

I(K54, DA)

I(K02,AB)

I(K87,ST)

I(K75, MO)

K60

I(K03,ZO)

B

A B

I(K55,KL)

D(K54,DA)

I(K15, DA)

125


Einfügen und Löschen (3)K00

I(K15, DA)

I(K25,KA)

I(K51,FR)

AA

ZZ

A

K99

K00

I(K56, DA) AA

ZZ

AK99K60

B

B

D

C

A C

B

C

A D

B

C

K40

K60

JA

JA

126


k-dimensionaler Buddy-Baum

Erkennung der potenziellen Partner für Verschmelzen.

Jede Seite hat einen eindeutigen Zwilling:

Ein Zwillingspaar wird erzeugt, wenn sein Bereich geteilt wird.

Verschmelzen in umgekehrter Reihenfolge.

Verwaltung der Grid-File-Struktur

C

A D

B

127


Grid-Matrix kann sehr groß werden und muss daher auf den Hintergrundspeicher ausgelagert und bei Zugriffen seitenweise eingelagert werden. Erzwingt Linearisierung der Matrix. Die k ein-dimensionalen Vektoren sollten unbedingt im

Hauptspeicher gehalten werden. Alle Frageformen lassen sich zu Range Queries

vereinheitlichen point query: Untergrenze = Obergrenze partially specified query: Für nicht spezifizierte Attribute:

Untergrenze = Minimalwert (Domäne) Obergrenze = Maximalwert (Domäne)

Linearisierung führt zu Ungleichbehandlung der Attribute bei Range Queries.

Leistungsbetrachtungen

128



KdB-BaumKdB-Baum

129


Grundstruktur (1)

KdB-Baum

…


Satzmenge physisch gespeichert abhängig vom Index-Verfahren

Bessere Gleichbehandlung aller Attribute auch bei der Realisierung.

130


KdB-Baum besteht aus einer Menge von Seiten und einem Verweis auf die Wurzel-Seite.

2 Arten von Seiten: R-Seiten enthalten eine Menge von Paaren

(region, nachf) region: Spezifikation einer Region. nachf: Verweis auf Nachfolger-Seite im Baum. Die R-Seiten definieren die Aufteilung des Datenraums in

Regionen. P-Seiten enthalten eine Menge von Paaren

(punkt, location) punkt: Spezifikation eines Punktes. location: Verweis auf zugehörigen Datensatz (im Folgenden

vereinfachend weggelassen). Die P-Seiten sind die Blätter des Baums.

Grundstruktur (2)

131


D0=D1=[0,..., 100), Seitenkapazität = 3

Beispiel

D1

D0

100

100

3 P-Seiten1 R-Seite

50

30

ws [0,100) x [50,100)

[0,30) x [0,50)

[30,100) x [0,50)

132


Definierende Eigenschaften 1. R-Seiten enthalten keine Null-Zeiger und sind nicht leer.2. Die Länge aller Pfade von der Wurzel zu den Blättern (P-

Seiten) ist identisch.3. Alle Regionen in einer R-Seite sind disjunkt; ihre

Vereinigung ergibt wieder eine Region.4. Falls die Wurzel-Seite eine R-Seite ist, ergibt die

Vereinigung ihrer Regionen den gesamten Datenraum.5. Falls ein Eintrag (region, nachf) in einer R-Seite vorkommt,

und a) nachf ist eine R-Seite, dann ist die Vereinigung aller Regionen

in nachf gleich region. b) nachf ist eine P-Seite, dann liegen alle Punkte von nachf in

region.

Grundstruktur (3)

133


Vorbereitende Definitionen

Sei xi Di und R = I0...Ik-1 eine Region mit Ii = [mini ,maxi), 0 i k-1

Falls xi Ii, definiere linke Teilregion von R bezüglich xi:

leftregion (R, xi):= I0...[mini,xi)...Ik-1 rechte Teilregion von R bezüglich xi:

rightregion (R,xi):=I0...[xi,maxi)...Ik-1

Falls xi Ii, dann gilt R liegt links von xi gdw. maxi xi R liegt rechts von xi gdw. xi < mini

Sei p=(p0,..., pk-1) D ein Punkt. Dann gilt p liegt links von xi gdw. pi < xi p liegt rechts von xi gdw. pi xi

134








Sei p=(p0,..., pk-1) D ein Punkt. Dann gilt p liegt links von xi gdw. pi < xi p liegt rechts von xi gdw. pi xi

R

max1

min1

max0min0 x0

D0

D1

135








Sei p= (p0,..., pk-1) D ein Punkt. Dann gilt p liegt links von xi gdw. pi < xi p liegt rechts von xi gdw. pi xi

R

max1

min1

max0min0 x0

D0

D1

136


Split (page, xi):if page verweist auf eine R-Seite return (R-Split (page xi )); else return (P-Split (page, xi ));

Spalten von Seiten (1)

P-Split (page, xi):Erzeuge neue P-Seiten leftpage und rightpage;forall Punkte p in page:

if p links von xi: Füge p in leftpage ein; else Füge p in rightpage ein;

Lösche page;return (leftpage, rightpage);

137


Spalten von P-Seiten

D0

D1

x0

leftpage

x0 D0

D1

rightpage

x0D0

D1

138


R-Split (page, xi):Erzeuge neue R-Seiten leftpage und rightpage;forall Paare (region, nachf) in page:

if region links von xi: Füge (region, nachf) in leftpage ein;

else if region rechts von xi: Füge (region, nachf) in rightpage ein;

else begin (leftpage', rightpage'):= Split (nachf,xi);Füge (leftregion(region, xi), leftpage') in leftpage ein; Füge (rightregion(region, xi), rightpage') in rightpage ein;

end; Lösche page;return (leftpage, rightpage);

Spalten von Seiten (2)

139


Spalten von R-Seiten

D0

D1

x0

x0

leftpage

x0 D0

D1

x0

rightpage

x0D0x0

D1

140


Insert (ws, p): // ws: Wurzelseite, p: ein Punkt //if ws=Null do begin

Erzeuge neue P-Seite page; Füge p in page ein; Setze ws := page; return

end; Führe Exact Match Query nach p durch;Ergebnis: Verweis auf Seite page, in die p eingefügt werden soll;if p schon in page do begin Sonderbehandlung; return end;Füge p in page ein;if kein Überlauf von page do return;

Einfügen von Datensätzen

141


Marke M1; // Überlauf von pageWähle (erneut) eine Domain Di und einen Wert xi Di so, dass durch das

Splitten von page entlang xi zwei nicht volle Seiten entstehen;(leftpage, rightpage) := Split (page, xi)if page Wurzel-Seite ws do begin

Erzeuge neue R-Seite newpage mit den Einträgen (D0… [-i,xi) … Dk-1, leftpage)und (D0… [xi,i) … Dk-1, rightpage);

Setze ws := newpage; return

end;Sei parentpage die Vaterseite von page;Ersetze in parentpage(region, page) durch

(leftregion(region, xi),leftpage) und (rightregion(region, xi), rightpage);

if Seitenüberlauf von parentpage do beginSetze page := parentpage; goto M1 end;else return;

end Insert ;

Einfügen von Datensätzen

142



Einfügen von Sätzen

D1

D0

100ws

100

Insert(ws,(75,80))

Insert(ws,(5,15))Insert(ws,(20,40))Insert(ws,(80,30))

P-Seiten

50

143




D1

D0

100

100

ws [0,100) x [50,100)

[0,100) x [0,50)

Insert(ws,(20,90))

Insert(ws,(75,80))


P-SeitenR-Seiten

Insert(ws,(55,20))

50

30

144




D1

D0

100

100

Insert(ws,(20,90))

Insert(ws,(75,80))


P-SeitenR-Seiten

Insert(ws,(55,20))

50

30

Insert(ws,(60,60))Insert(ws,(50,60))

ws [0,100) x [50,100)

[0,30) x [0,50)

[30,100) x [0,50)

70

145




D1

D0

100

100

P-SeitenR-Seiten

50

30

Insert(ws,(60,60))

70ws [0,100) x [70,100)

[0,100) x [50,70)

[0,30) x [0,50)

[30,100) x [0,50)

146




D1

D0

100

100

P-SeitenR-Seiten

50

30

Insert(ws,(60,60))

70

[0,100) x [70,100)

[0,100) x [50,70)

[30,100) x [0,50)

[0,30) x [0,50)

[0,100) x [50,100)

[0,100) x [0,50)

ws

147


Aufteilung des Datenraums:

Strategien für das Spalten

D1

D0

Zyklisches Spalten von Seiten: Wenn Partial Match Queries auf D0 bevorzugt unterstützt werden sollen: Spalten entlang D0 wann immer möglich.

D1

D0

Falls Verteilung der Daten in D = D0… Dk-1 bekannt: Definiere Länge eines Intervalls Ii Di als Erwartungswert der Wahrscheinlichkeit, dass Komponente ki eines Schlüssels k D in Ii liegt. Wähle beim Splitten einer Region I0 … Ik-1 immer das längste Intervall.

148


Auswahl eines Wertes xi: Wähle xi so, dass in der zu splittenden Seite gleich viele

Punkte links und rechts von xi liegen. u.U. muss eine Neuwahl der Spalt-Dimension erfolgen:

Strategien für das Spalten

x0

D0

D1

149


Bearbeitung von Range Queries: Rekursives Durchlaufen der Äste des Baumes, deren Knoten Regionen enthalten, die geschnitten mit der Anfrage-Region nicht die leere Menge ergeben.

Für den Seitenfüllgrad kann im K-D-B-Baum keine untere Grenze garantiert werden.

Daher gelegentliche Reorganisation notwendig. Es existieren mehrere mögliche Reorganisations-Maßnahmen.

Beispiel: Zusammenlegen benachbarter Seiten.

Problem: Die Vereinigung der Regionen der beiden Seiten muss wieder eine Region ergeben. Dies ist nicht immer der Fall!

Eigenschaften des K-D-B-Baumes

D0

D1

AB

C

A kann weder mit B noch mit C zusammengelegt werden.

150


KdB-Baum:+ Gleichbehandlung der Attribute

besser steuerbar - Auslastung der Seiten bei

Löschoperationen nicht garantiert, daher:

größere Tiefe des Baums 5–6 Seitenzugriffe für Exact

Match Queries

Vergleich K-D-B-Baum mit Grid-File

D0

D1

Grid-File:

+ Nur 2 Seitenzugriffe bei Exact Match Query

± Verschmelzen von Seiten einfacher

- Ungleichbehandlung der Attribute bei Range Query

D1

D0

Documents

Universität Karlsruhe (TH) © 2008 Univ,Karlsruhe, IPD, Prof. LockemannDBI 6 Kapitel 6 Zugriffsschicht: Satzzugriffsstrukturen