K7 DB-Zugriffsverfahren Flashcards

Question 1

Q

GDB K7 DB-Zugriffsverfahren

Übersicht Zugriffsverfahren

Question 2

Q

GDB K7 DB-Zugriffsverfahren

Listen: Sequentielle Listen auf Externspeichern

Answer

A

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

Question 3

Q

GDB K7 DB-Zugriffsverfahren

Listen: Gekettete Listen auf Externspeichern

Answer

A

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

Question 4

Q

GDB K7 DB-Zugriffsverfahren

Hashing auf Externspeichern

Answer

A

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.

Question 5

Q

GDB K7 DB-Zugriffsverfahren

Allgemeine Bäume

Question 6

Q

GDB K7 DB-Zugriffsverfahren

Implementierung von allgemeinen Bäumen

Question 7

Q

GDB K7 DB-Zugriffsverfahren

m-Wege-Suchbäume

Question 8

Q

GDB K7 DB-Zugriffsverfahren

Knotenformat eines m-Wege-Suchbaums

Question 9

Q

GDB K7 DB-Zugriffsverfahren

Aufbaubeispiel m-Wege-Suchbäume

Question 10

Q

GDB K7 DB-Zugriffsverfahren

Beobachtung zu m-Wege-Suchbäume

Answer

A

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)

Question 11

Q

GDB K7 DB-Zugriffsverfahren

Wichtige Eigenschaften von m-Wege-Suchbäumen

Answer

A

Die D_i können Daten oder Zeiger auf die Daten repräsentieren. Zur Vereinfachung werden die D_i (in den Illustrationen) weggelassen.
S(P_i) sei die Seite, auf die P_i zeigt, und K(P_i) sei die Menge aller Schlüssel, die im Unterbaum mit Wurzel S(P_i) gespeichert werden können.

Question 12

Q

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…

Question 13

Q

GDB K7 DB-Zugriffsverfahren

Kostenanalyse für m-Wege-Suchbäume: bei voller Belegung ergibt sich als Anzahl der Einträge…

Answer

A

n = N*(m-1)

Question 14

Q

GDB K7 DB-Zugriffsverfahren

Kostenanalyse für m-Wege-Suchbäume: im ungünstigsten Fall ist der Baum völlig entartet…

Answer

A

n = N = h

Question 15

Q

GDB K7 DB-Zugriffsverfahren

Kostenanalyse für m-Wege-Suchbäume: Schranken für die Höhe eines m-Wege-Suchbaums

Question 16

Q

GDB K7 DB-Zugriffsverfahren

Kostenanalyse für m-Wege-Suchbäume: Wartungsaufwand

Question 17

Q

GDB K7 DB-Zugriffsverfahren

Aufsuchen eines Schlüssels in einem m-Wege-Suchbaum

Question 18

Q

GDB K7 DB-Zugriffsverfahren

Durchlaufen eines m-Wege-Suchbaums in symmetrischer Ordnung

Question 19

Q

GDB K7 DB-Zugriffsverfahren

Mehrwegbäume

Answer

A

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

Question 20

Q

GDB K7 DB-Zugriffsverfahren

B-Bäume: Definition

Answer

A

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.

Question 21

Q

GDB K7 DB-Zugriffsverfahren

B-Bäume: Einträge

Question 22

Q

GDB K7 DB-Zugriffsverfahren

Beispiel: B-Baum der Klasse τ(2,3)

Question 23

Q

GDB K7 DB-Zugriffsverfahren

B-Bäume: Höhe, balacierte Struktur

Question 24

Q

GDB K7 DB-Zugriffsverfahren

B-Bäume: Einfügen

Answer

A

Einfügealgorithmus (ggf. rekursiv)

suche Einfügeposition;
wenn Platz vorhanden ist, speichere Element, sonst schaffe Platz durch Split-Vorgang und füge ein.

Question 25

Q

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

Question 26

Q

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

Question 27

Q

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

Question 28

Q

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

Question 29

Q

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

Question 30

Q

GDB K7 DB-Zugriffsverfahren

B-Bäume: Kostenanalyse für Direkte Suche

Answer

A

Anzahl der zu holenden Seiten: f (fetch)
Anzahl der zu schreibenden Seiten: w (write)

Question 31

Q

GDB K7 DB-Zugriffsverfahren

B-Bäume: Kostenanalyse für Sequentielle Suche

Answer

A

Durchlauf in symmetrischer Ordnung: f_seq = N

Pufferung der Zwischenknoten im HSP wichtig!

Question 32

Q

GDB K7 DB-Zugriffsverfahren

B-Bäume: Kostenanalyse für Einfügen

Question 33

Q

GDB K7 DB-Zugriffsverfahren

B-Bäume: Löschen

Answer

A

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.

Question 34

Q

GDB K7 DB-Zugriffsverfahren

B-Bäume: Löschalgorithmus

Question 35

Q

GDB K7 DB-Zugriffsverfahren

B-Bäume
Beispiel: Löschen

Question 36

Q

GDB K7 DB-Zugriffsverfahren

B-Bäume
Beispiel: Löschen

Question 37

Q

GDB K7 DB-Zugriffsverfahren

B-Bäume: Kostenanalyse für Löschen

Question 38

Q

GDB K7 DB-Zugriffsverfahren

B-Bäume: Überlaufbehandlung

Question 39

Q

GDB K7 DB-Zugriffsverfahren

B-Bäume: Überlaufbehandlung

Question 40

Q

GDB K7 DB-Zugriffsverfahren

B-Bäume: Überlaufbehandlung

Question 41

Q

GDB K7 DB-Zugriffsverfahren

B-Bäume: Überlaufbehandlung Einfügekosten bei m=2

Question 42

Q

GDB K7 DB-Zugriffsverfahren

B-Bäume: Verbesserung des Belegungsgrades

Question 43

Q

GDB K7 DB-Zugriffsverfahren

B-Bäume: Speicherplatzbelegung

Question 44

Q

GDB K7 DB-Zugriffsverfahren

B-Bäume: Suche innerhalb einer Seite

Question 45

Q

GDB K7 DB-Zugriffsverfahren

B*-Bäume: Definition

Answer

A

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.

Question 46

Q

GDB K7 DB-Zugriffsverfahren

B*-Bäume: 2 Knotenformate

Question 47

Q

GDB K7 DB-Zugriffsverfahren

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

Question 48

Q

GDB K7 DB-Zugriffsverfahren

Beispiel: B*-Baum der Klasse τ(2, 2, 3)

Question 49

Q

GDB K7 DB-Zugriffsverfahren

Erklärungsmodell für den B*-Baum

Answer

A

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.

Question 50

Q

GDB K7 DB-Zugriffsverfahren

Grundoperationen beim B*-Baum: Direkte Suche

Answer

A

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 f_avg 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.

Question 51

Q

GDB K7 DB-Zugriffsverfahren

Grundoperationen beim B*-Baum: Sequentielle Suche

Answer

A

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.

Question 52

Q

GDB K7 DB-Zugriffsverfahren

Grundoperationen beim B*-Baum: Einfügen

Answer

A

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.

Question 53

Q

GDB K7 DB-Zugriffsverfahren

Grundoperationen beim B*-Baum: Beispiel Einfügen

Question 54

Q

GDB K7 DB-Zugriffsverfahren

Grundoperationen beim B*-Baum: Schema Split-Vorgang

Question 55

Q

GDB K7 DB-Zugriffsverfahren

Grundoperationen beim B*-Baum: Löschen

Answer

A

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.