K7 DB-Zugriffsverfahren Flashcards
GDB K7 DB-Zugriffsverfahren
Übersicht Zugriffsverfahren

GDB K7 DB-Zugriffsverfahren
Listen: Sequentielle Listen auf Externspeichern
- Prinzip: Zusammenhang der Satzmenge wird durch physische Nachbarschaft hergestellt
- Reihenfolge der Sätze: ungeordnet (Einfügereihenfolge) oder sortiert nach einem oder mehreren Attributen (sog. Schlüssel)
- wichtige Eigenschaft: Cluster-Bildung, d. h., physisch benachbarte Speicherung von logisch zusammengehörigen Sätzen
- Sequentielle Listen garantieren Cluster-Bildung in Seiten für die Schlüssel-/Speicherungsreihenfolge
- pro Satztyp kann Cluster-Bildung nur bezüglich eines Kriteriums erfolgen, falls keine Redundanz eingeführt werden soll
GDB K7 DB-Zugriffsverfahren
Listen: Gekettete Listen auf Externspeichern
- Prinzip: Verkettung erfolgt zwischen Datensätzen
- Speicherung der Sätze i. Allg. in verschiedenen Seiten
- Seiten können beliebig zugeordnet werden
- Mehrfachverkettung nach verschiedenen Kriterien (Schlüsseln) möglich

GDB K7 DB-Zugriffsverfahren
Hashing auf Externspeichern
Hash-Adresse bezeichnet Bucket (Behälter, Seite)
- Das Kollisionsproblem wird dadurch entschärft, dass mehr als ein Satz auf seiner Hausadresse gespeichert werden kann.
- Aufnahme von bis zu b Sätzen (b = Bucket-Kapazität)
- Primärbereich kann bis zu b*m Sätze aufnehmen !
Überlaufbehandlung
- Überlauf tritt erst beim (b+1)-ten Synonym auf
- viele (bekannte) Verfahren sind möglich, aber lange Sondierungsfolgen im Primärbereich sollten vermieden werden häufig Wahl eines separaten Überlaufbereichs mit dynamischer Zuordnung der Buckets
- Optionen: Verkettung der Überlauf-Buckets pro Primär-Bucket oder Zuordnung von Überlauf-Buckets zu mehreren Primär-Buckets
Speicherungsreihenfolge im Bucket
- ohne Ordnung (Einfügefolge)
- nach der Sortierfolge des Schlüssels: aufwendiger, jedoch Vorteile beim Suchen (sortierte Liste!)
Bucket-Größe
- Bucket-Adressierung eignet sich besonders gut für die Anwendung auf Externspeichern
- Wahl der Bucket-Größe: meist Seite (Transfereinheit)
- Zugriff auf die Hausadresse bedeutet dann eine physische E/A; jeder weitere Zugriff auf ein Überlauf-Bucket löst jeweils einen weiteren physischen E/A-Vorgang aus.

GDB K7 DB-Zugriffsverfahren
Allgemeine Bäume

GDB K7 DB-Zugriffsverfahren
Implementierung von allgemeinen Bäumen

GDB K7 DB-Zugriffsverfahren
m-Wege-Suchbäume

GDB K7 DB-Zugriffsverfahren
Knotenformat eines m-Wege-Suchbaums

GDB K7 DB-Zugriffsverfahren
Aufbaubeispiel m-Wege-Suchbäume

GDB K7 DB-Zugriffsverfahren
Beobachtung zu m-Wege-Suchbäume
Die Schlüssel in den inneren Knoten besitzen zwei Funktionen. Sie identifizieren Daten(sätze) und sie dienen als Wegweiser in der Baumstruktur.
Der m-Wege-Suchbaum ist im allgemeinen nicht ausgeglichen. Es ist für Aktualisierungsoperationen kein Balancierungsmechanismus vorgesehen. (schlechte Platzausnutzung, Entartung)
GDB K7 DB-Zugriffsverfahren
Wichtige Eigenschaften von m-Wege-Suchbäumen
- Die Di können Daten oder Zeiger auf die Daten repräsentieren. Zur Vereinfachung werden die Di (in den Illustrationen) weggelassen.
- S(Pi) sei die Seite, auf die Pi zeigt, und K(Pi) sei die Menge aller Schlüssel, die im Unterbaum mit Wurzel S(Pi) gespeichert werden können.

GDB K7 DB-Zugriffsverfahren
Kostenanalyse für m-Wege-Suchbäume: Die Anzahl der Knoten N in einem vollständigen Baum der Höhe h ist…

GDB K7 DB-Zugriffsverfahren
Kostenanalyse für m-Wege-Suchbäume: bei voller Belegung ergibt sich als Anzahl der Einträge…
n = N*(m-1)
GDB K7 DB-Zugriffsverfahren
Kostenanalyse für m-Wege-Suchbäume: im ungünstigsten Fall ist der Baum völlig entartet…
n = N = h
GDB K7 DB-Zugriffsverfahren
Kostenanalyse für m-Wege-Suchbäume: Schranken für die Höhe eines m-Wege-Suchbaums

GDB K7 DB-Zugriffsverfahren
Kostenanalyse für m-Wege-Suchbäume: Wartungsaufwand
O(n)
GDB K7 DB-Zugriffsverfahren
Aufsuchen eines Schlüssels in einem m-Wege-Suchbaum

GDB K7 DB-Zugriffsverfahren
Durchlaufen eines m-Wege-Suchbaums in symmetrischer Ordnung

GDB K7 DB-Zugriffsverfahren
Mehrwegbäume
Ziel: Aufbau sehr breiter Bäume von geringer Höhe
- in Bezug auf Knotenstruktur vollständig ausgeglichen
- effiziente Durchführung der Grundoperationen
- Zugriffsverhalten ist weitgehend unabhängig von Anzahl der Sätze
- Einsatz als universelle Zugriffs- oder Indexstruktur
Grundoperationen:
- Einfügen/Löschen eines Satzes
- direkter Schlüsselzugriff auf einen Satz
- sortiert sequentieller Zugriff auf mehrere Sätze
Breites Spektrum von Anwendungen
- Dateiorganisation (“logische Zugriffsmethode”, VSAM)
- Datenbanksysteme (Varianten des B*-Baumes in allen DBVS!)
- Text- und Dokumentenorganisation
- . . .
GDB K7 DB-Zugriffsverfahren
B-Bäume: Definition
Seien k, h ganze Zahlen, h ≥ 0, k > 0. Ein B-Baum B der Klasse τ (k,h) ist entweder ein leerer Baum oder ein geordneter Suchbaum mit folgenden Eigenschaften:
- Jeder Pfad von der Wurzel zu einem Blatt hat die gleiche Länge h-1.
- Jeder Knoten außer der Wurzel und den Blättern hat mindestens k+1 Söhne. Die Wurzel ist ein Blatt oder hat mindestens 2 Söhne.
- Jeder Knoten hat höchstens 2k+1 Söhne.
- Jedes Blatt mit der Ausnahme der Wurzel als Blatt hat mindestens k und höchstens 2k Einträge.
Reformulierung der Def.:
- (4) und (3) ‚Eine Seite darf höchstens voll sein.‘
- (4) und (2) Jede Seite (außer der Wurzel) muss mindestens halb voll sein. Die Wurzel enthält mindestens einen Schlüssel.
- (1) Der Baum ist, was die Knotenstruktur angeht, vollständig ausgeglichen.

GDB K7 DB-Zugriffsverfahren
B-Bäume: Einträge

GDB K7 DB-Zugriffsverfahren
Beispiel: B-Baum der Klasse τ(2,3)

GDB K7 DB-Zugriffsverfahren
B-Bäume: Höhe, balacierte Struktur

GDB K7 DB-Zugriffsverfahren
B-Bäume: Einfügen
Einfügealgorithmus (ggf. rekursiv)
- suche Einfügeposition;
- wenn Platz vorhanden ist, speichere Element, sonst schaffe Platz durch Split-Vorgang und füge ein.

GDB K7 DB-Zugriffsverfahren
B-Bäume Beispiel: B-Baum der Klasse τ(2, h), Einfügen
Einfügereihenfolge: 77, 12, 48, 69, 33, 89, 97, 91, 37, 45, 83, 2, 5, 57, 90, 95, 99, 50


GDB K7 DB-Zugriffsverfahren
B-Bäume Beispiel: B-Baum der Klasse τ(2, h), Einfügen
Einfügereihenfolge: 77, 12, 48, 69, 33, 89, 97, 91, 37, 45, 83, 2, 5, 57, 90, 95, 99, 50


GDB K7 DB-Zugriffsverfahren
B-Bäume Beispiel: B-Baum der Klasse τ(2, h), Einfügen
Einfügereihenfolge: 77, 12, 48, 69, 33, 89, 97, 91, 37, 45, 83, 2, 5, 57, 90, 95, 99, 50


GDB K7 DB-Zugriffsverfahren
B-Bäume Beispiel: B-Baum der Klasse τ(2, h), Einfügen
Einfügereihenfolge: 77, 12, 48, 69, 33, 89, 97, 91, 37, 45, 83, 2, 5, 57, 90, 95, 99, 50


GDB K7 DB-Zugriffsverfahren
B-Bäume Beispiel: B-Baum der Klasse τ(2, h), Einfügen
Einfügereihenfolge: 77, 12, 48, 69, 33, 89, 97, 91, 37, 45, 83, 2, 5, 57, 90, 95, 99, 50

GDB K7 DB-Zugriffsverfahren
B-Bäume: Kostenanalyse für Direkte Suche
- Anzahl der zu holenden Seiten: f (fetch)
- Anzahl der zu schreibenden Seiten: w (write)

GDB K7 DB-Zugriffsverfahren
B-Bäume: Kostenanalyse für Sequentielle Suche
Durchlauf in symmetrischer Ordnung: fseq = N
Pufferung der Zwischenknoten im HSP wichtig!
GDB K7 DB-Zugriffsverfahren
B-Bäume: Kostenanalyse für Einfügen

GDB K7 DB-Zugriffsverfahren
B-Bäume: Löschen
Die B-Baum-Eigenschaft muss wiederhergestellt werden, wenn die Anzahl der Elemente in einem Knoten kleiner als k wird.
Durch Ausgleich mit Elementen aus einer Nachbarseite oder durch Mischen (Konkatenation) mit einer Nachbarseite wird dieses Problem gelöst. Beim Ausgleichsvorgang sind in der Seite P k-1 Elemente und in P’ mehr als k Elemente.

GDB K7 DB-Zugriffsverfahren
B-Bäume: Löschalgorithmus

GDB K7 DB-Zugriffsverfahren
B-Bäume
Beispiel: Löschen


GDB K7 DB-Zugriffsverfahren
B-Bäume
Beispiel: Löschen


GDB K7 DB-Zugriffsverfahren
B-Bäume: Kostenanalyse für Löschen

GDB K7 DB-Zugriffsverfahren
B-Bäume: Überlaufbehandlung


GDB K7 DB-Zugriffsverfahren
B-Bäume: Überlaufbehandlung


GDB K7 DB-Zugriffsverfahren
B-Bäume: Überlaufbehandlung


GDB K7 DB-Zugriffsverfahren
B-Bäume: Überlaufbehandlung Einfügekosten bei m=2

GDB K7 DB-Zugriffsverfahren
B-Bäume: Verbesserung des Belegungsgrades

GDB K7 DB-Zugriffsverfahren
B-Bäume: Speicherplatzbelegung

GDB K7 DB-Zugriffsverfahren
B-Bäume: Suche innerhalb einer Seite

GDB K7 DB-Zugriffsverfahren
B*-Bäume: Definition
Seien k, k* und h* ganze Zahlen, h* ≥ 0, k, k* > 0. Ein B*-Baum B der Klasse τ(k,k*,h*) ist entweder ein leerer Baum oder ein geordneter Suchbaum, für den gilt:
- Jeder Pfad von der Wurzel zu einem Blatt besitzt die gleiche Länge h*-1.
- Jeder Knoten außer der Wurzel und den Blättern hat mindestens k+1 Söhne, die Wurzel mindestens 2 Söhne, außer wenn sie ein Blatt ist.
- Jeder innere Knoten hat höchstens 2k+1 Söhne.
- Jeder Blattknoten mit Ausnahme der Wurzel als Blatt hat mindestens k* und höchstens 2k* Einträge.
GDB K7 DB-Zugriffsverfahren
B*-Bäume: 2 Knotenformate

GDB K7 DB-Zugriffsverfahren
B*-Bäume: Es gilt für L, k und k*…

GDB K7 DB-Zugriffsverfahren
Beispiel: B*-Baum der Klasse τ(2, 2, 3)

GDB K7 DB-Zugriffsverfahren
Erklärungsmodell für den B*-Baum
Der B*-Baum lässt sich auffassen als eine gekettete sequentielle Datei von Blättern, die einen Indexteil besitzt, der selbst ein B-Baum ist. Im Indexteil werden insbes. beim Split-Vorgang die Operationen des B-Baums eingesetzt.

GDB K7 DB-Zugriffsverfahren
Grundoperationen beim B*-Baum: Direkte Suche
Da alle Schlüssel in den Blättern sind, kostet jede direkte Suche h* Zugriffe. h* ist jedoch im Mittel kleiner als h in B-Bäumen. Da favg beim B-Baum in guter Näherung mit h abgeschätzt werden kann, erhält man also durch den B*-Baum eine effizientere Unterstützung der direkten Suche.
GDB K7 DB-Zugriffsverfahren
Grundoperationen beim B*-Baum: Sequentielle Suche
Sie erfolgt nach Aufsuchen des Linksaußen der Struktur unter Ausnutzung der Verkettung der Blattseiten. Es sind zwar ggf. mehr Blätter als beim B-Baum zu verarbeiten, doch da nur h*-1 innere Knoten aufzusuchen sind, wird die sequentielle Suche ebenfalls effizienter ablaufen.
GDB K7 DB-Zugriffsverfahren
Grundoperationen beim B*-Baum: Einfügen
Es ist von der Durchführung und vom Leistungsverhalten her dem Einfügen in einen B-Baum sehr ähnlich. Bei inneren Knoten wird die Spaltung analog zum B-Baum durchgeführt. Beim Split-Vorgang einer Blattseite muss gewährleistet sein, dass jeweils die höchsten Schlüssel einer Seite als Wegweiser in den Vaterknoten kopiert werden. Die Verallgemeinerung des Split-Vorgangs lässt sich analog zum B-Baum einführen.
GDB K7 DB-Zugriffsverfahren
Grundoperationen beim B*-Baum: Beispiel Einfügen


GDB K7 DB-Zugriffsverfahren
Grundoperationen beim B*-Baum: Schema Split-Vorgang


GDB K7 DB-Zugriffsverfahren
Grundoperationen beim B*-Baum: Löschen
Datenelemente werden immer von einem Blatt entfernt (keine komplexe Fallunterscheidung wie beim B-Baum). Weiterhin muss beim Löschen eines Schlüssels aus einem Blatt dieser Schlüssel nicht notwendigerweise aus dem Indexteil entfernt werden; er kann seine Funktion als Wegweiser behalten.
GDB K7 DB-Zugriffsverfahren
Grundoperationen beim B*-Baum: Beispiel Löschen


GDB K7 DB-Zugriffsverfahren
B*-Bäume: Optimierungsmöglichkeiten

GDB K7 DB-Zugriffsverfahren
B*-Bäume: Eigenschaften

GDB K7 DB-Zugriffsverfahren
B- und B*-Baum: Quantitativer Vergleich

GDB K7 DB-Zugriffsverfahren
Zusammenfassung
