Erklären Sie die Primärorganisation nach indexsequentieller Art und nach dem Hash-Verfahren und nennen dabei je zwei Vor- und Nachteile dieser Organisationsform
Index Sequentiell: Sätze werden gemäß Primärorganisation gespeichert, zugleich wird für den Primärschlüssel ein Index aufgebaut.
Hash Verfahren: Die Speicheradresse wird durch Umrechnungsformen aus dem Primärschlüssel errechnet.
Hash Verfahren: Die Speicheradresse wird durch Umrechnungsformen aus dem Primärschlüssel errechnet.
Was sind Hot Spots beim Transaktionsbetrieb und wie kann man das Problem beseitigen?
Hotspots sind Blöcke die ständig gelesen & geschrieben werden und somit nie in die permanente DB zurückgeschrieben werden. Es sammelt sich einiges an, was im Fehlerfall zu aufwändigen Recovery Führt
Lösung: Checkpoints: Zeitpunkte an denen zwangsweise Blöcke in die DB geschrieben werden --> Hoher E/A-Verkehr, temporäre Inkonsistenz, aber verbesserte Recovery im Fehlerfall
Lösung: Checkpoints: Zeitpunkte an denen zwangsweise Blöcke in die DB geschrieben werden --> Hoher E/A-Verkehr, temporäre Inkonsistenz, aber verbesserte Recovery im Fehlerfall
Unterscheiden Sie die Begriffe Sicherheit und Integrität
Für Sicherheit wird jeder Benutzer überprüft, ob er berechtigt ist, die Dinge zu tun, die er gerade versucht
Für Integrität wird überprüft, ob die Dinge die gerade versucht werden, auch korrekt ablaufen
Berechtigt, Korrekt müssen genannt werden
Für Integrität wird überprüft, ob die Dinge die gerade versucht werden, auch korrekt ablaufen
Berechtigt, Korrekt müssen genannt werden
Sei ein Knoten eines B-Baums in einem Block gespeichert und sei die Blockgröße x=512 Bytes. Außerdem habe ein Schlüsselfeld die Länge k=9 Bytes und ein Blockzeiger die Länge z=6 Bytes sowie jeder Indexeintrag k* ein Paar (k,v)
Von welcher Ordnung m kann der B-Baum höchstens sein?
Von welcher Ordnung m kann der B-Baum höchstens sein?
(2m+1)*z+2m(k+z) <= 512
2m+1 Blockzeiger auf Sohnkoten
2m Suchschlüsselfelder zu Indexeinträgen
k=9, z=6
(2m+1)*6+2m(9+6) <= 512
m<=12
2m+1 Blockzeiger auf Sohnkoten
2m Suchschlüsselfelder zu Indexeinträgen
k=9, z=6
(2m+1)*6+2m(9+6) <= 512
m<=12
Gegeben sei eine sequentielle Datei mit n = 100.000 Datensätzen, die auf einer Festplatte mit Blockgröße s=1024 Bytes gespeichert sind. Es darf angenommen werden, dass alle Datensätze fester Läge l=100 Bytes sind und Seitengrenzen nicht überschreiten.
Angenommen, dass das Suchschlüsselfeld (Sortierfeld) die Länge k=9 Bytes besitzt und dass ein Zeiger vom Index auf einen Block der Datei z=6 Bytes benötigt.
Wie viele Blockzugriffe benötigt eine binäre Suche auf diese Datei?
Wie viele Blockzugriffe werden zum Auffinden eines Datensatzes benötigt, wenn für die Datei ein dichter bzw. dünner Primärindex erzeugt wird?
Angenommen, dass das Suchschlüsselfeld (Sortierfeld) die Länge k=9 Bytes besitzt und dass ein Zeiger vom Index auf einen Block der Datei z=6 Bytes benötigt.
Wie viele Blockzugriffe benötigt eine binäre Suche auf diese Datei?
Wie viele Blockzugriffe werden zum Auffinden eines Datensatzes benötigt, wenn für die Datei ein dichter bzw. dünner Primärindex erzeugt wird?
Binär:
r=s/l (abgerundet) = 10 Datensätze pro Block
Anzahl der benötigten Blöcke ist b = n/r (aufgerundet) = 100.000/10 = 10.000
Eine binäre Suche benötigt log2(b) (aufgerundet) Zugriffe
log2(10.000) 14 Zugriffe
Dichter Index:
Größe eines Indexeintrages: 9+6 = 15
Indexeinträge 1024/15 = 68 Indexeinträge pro Block
Benötigte Blöcke = 100.000/68 (aufgerundet) = 1.471
log2(1.471) = 11 Zugriffe (aufgerundet)
Dünner Index:
100.000 Blöcke durch 68 Einträge (aufgerundet)
100.000/68 = 148
log2(148) = 8 Zugriffe (aufgerundet)
r=s/l (abgerundet) = 10 Datensätze pro Block
Anzahl der benötigten Blöcke ist b = n/r (aufgerundet) = 100.000/10 = 10.000
Eine binäre Suche benötigt log2(b) (aufgerundet) Zugriffe
log2(10.000) 14 Zugriffe
Dichter Index:
Größe eines Indexeintrages: 9+6 = 15
Indexeinträge 1024/15 = 68 Indexeinträge pro Block
Benötigte Blöcke = 100.000/68 (aufgerundet) = 1.471
log2(1.471) = 11 Zugriffe (aufgerundet)
Dünner Index:
100.000 Blöcke durch 68 Einträge (aufgerundet)
100.000/68 = 148
log2(148) = 8 Zugriffe (aufgerundet)
Vergleichen Sie invertierte Listen und Multiliststrukturen als Möglichkeiten zur Sekundärorganisation für eine Datenbank bezüglich Ihrer Grundstruktur sowie den 3 Kriterien Speicherbedarf, Zugriffsverhalten beim Lesen sowie dem Aufwand beim Einfügen und Ändern (Aufwand bei hoher Fluktuation des Datenbestands)
Worin liegt die Besonderheit eines B*-Baumes gegenüber einem B-Baum und wo liegen die jeweiligen Einsatzgebiete dieser Datenstrukturen
B*-Baum hat eine Höhe h-1 für die Suchstruktur B*-Baum Index, die nicht alle Schlüssel enthält und eine B*-Baum Datei.
Schnellerer wahlfreier Zugriff als B-Baum (höhere Ordnung m-->kleineres h)
B*-Baum Datei enthält auch schnellen logisch fortlaufend ??
Schnellerer wahlfreier Zugriff als B-Baum (höhere Ordnung m-->kleineres h)
B*-Baum Datei enthält auch schnellen logisch fortlaufend ??
Was ist ein Zwei-Phasen-Commit, wie verläuft er und welches Problem ergibt sich daraus?
Ein Zwei-Phase-Commit ist nötig bei dem Zugriff einer Transaktion auf mehrere Datenbanken.
Problem des hohen Kommunikationsaufwands durch lokale und globale Koordination (Verzehnfachung der Antwortzeit)
a)lokales Abarbeiten der Transaktion
b)Melden des Transaktionsendes
c)Globales Transaktionsende
d)endgültiges lokales Transaktionsende
Problem des hohen Kommunikationsaufwands durch lokale und globale Koordination (Verzehnfachung der Antwortzeit)
a)lokales Abarbeiten der Transaktion
b)Melden des Transaktionsendes
c)Globales Transaktionsende
d)endgültiges lokales Transaktionsende
Nennen Sie 6 Regeln aus dem fundamentalen Prinzip von Date für verteilte Datenbanken
Lokale Eigenständigkeit jedes Rechners
Keine zentrale Verwaltungsinstanz
Ständige Verfügbarkeit
Lokale Unabhängigkeit
Unabhängigkeit gegenüber Fragmentierung
Unabhängigkeit gegenüber Datenreplikation
Wer Bock auf mehr hat:
Keine zentrale Verwaltungsinstanz
Ständige Verfügbarkeit
Lokale Unabhängigkeit
Unabhängigkeit gegenüber Fragmentierung
Unabhängigkeit gegenüber Datenreplikation
Wer Bock auf mehr hat:
In einem sicheren DB-Betrieb wurde gerade das Transaktionsende in die Logdatei geschrieben. Noch vor der Rückmeldung der Transaktion an den Benutzer stürzt das System ab. Wird beim nächsten Hochfahren die Transaktion deshalb zurückgesetzt?
Die Transaktion ist gültig, da nur die Information aus der Logdatei zählt
Was sind Checkpoints? Beschreiben Sie den Nachteil, wenn eine DB ohne Checkpoints arbeiten würde.
Checkpoints sind Zeitpunkte an denen alle Datenbankdateien im Arbeitsspeicher auf das nichtflüchtige externe Medium geschrieben werden. Ohne C würden häufig angefasste Daten (Hot Spots) immer in ASP stehen bleiben und nie extern aktualisiert werden. Im Fehlerfall müsste dann immer die gesamte Logdatei durchsucht werden, was sehr zeitaufwendig ist.
In nicht wenigen DB-Anwendungen ist die Recovery-Unterstützung deaktiviert oder zumindest stark eingeschränkt. Woran mag das liegen?
Recovery senkt wegen des zusätzlichen Overheads den Durchsatz und die mittleren Antwortzeiten deutlich ab. Entsprechend schnellere Rechner und Speichermedien sind wesentlich teurer. Abwägung: Zuverlässiger DB-Betrieb oder niedrige Betriebskosten
Ein DBA merkt, dass die Magnetplatte der DB nicht mehr fehlerfrei arbeitet. Welche Maßnahmen müssen ergriffen werden, um mögliche fehlerbehaftete Schreibvorgänge seit der letzten Sicherung zu eliminieren?
Anhalten des gesamten DB-Betriebs.
Rücksetzen aller noch nicht abgeschlossenen TA mittels Rollback. Abklemmen der Platte, montieren einer neuen Festplatte. Kopieren der letzten Sicherung, nachfahren der Änderungen seit der letzten Sicherung mittels Logdateiinformationen.
Starten des DB-Betriebs.
Rücksetzen aller noch nicht abgeschlossenen TA mittels Rollback. Abklemmen der Platte, montieren einer neuen Festplatte. Kopieren der letzten Sicherung, nachfahren der Änderungen seit der letzten Sicherung mittels Logdateiinformationen.
Starten des DB-Betriebs.
Im Parallelbetrieb kann man auch ohne Sperrmechanismen auskommen. Worum handelt es sich und warum wird das Verfahren kaum eingesetzt?
Optimistisches Verfahren: steigt die Konfliktwahrscheinlichkeit auf über 10% so schaukelt sich das System katastrophal auf. (Rücksetzungsaufwand höher als eingesparte Wartezeit)
Was wird unter Unabhängigkeit gegenüber Fragmentierung und gegenüber Replikation verstanden?
Fragmentierung: Verteilung einer Relation auf mehrere Rechner (horizontal/vertikal)
Replikation: Dieselben Daten können auf mehreren Rechnern gleichzeitig gehalten werden
Unabhängigkeit bedeutet dann, dass sich das System an der Benutzerschnittstelle nicht anders verhält, ob mit oder ohne Frag./Rep.
Replikation: Dieselben Daten können auf mehreren Rechnern gleichzeitig gehalten werden
Unabhängigkeit bedeutet dann, dass sich das System an der Benutzerschnittstelle nicht anders verhält, ob mit oder ohne Frag./Rep.
Ist unter Verwendung eines Zwei-Phasen-Commit-Protokolls die Regel 2 erfüllbar, obwohl dafür ein zentraler Koordinator benötigt wird?
Regel zwei ist dann erfüllbar, wenn der Koordinator nicht zentral auf einen Rechner gehalten wird. Übernimmt der Rechner die Koordination, der die globale Transaktion startete, ist Regel 2 nicht verletzt.
In einem Parallelbetrieb ist es nicht immer leicht zu sagen, ob eine Transaktion A vor oder nach einer Transaktion B ablief. Kann dieses Problem immer entschieden werden, wenn wir mit Sperrmechanismen arbeiten?
Nur teilweise: Transaktionen, die auf gemeinsame Daten zugreifen, werden serialisiert, die Reihenfolge kann angegeben werden. Für alle anderen TA, die gleichzeitig laufen, gilt dies nicht.
Welcher Nachteil kann sich beim Baumaufbau beim häufigen Ein- und Ausfügen in Bäumen einstellen? Wie kann man den Nachteil beseitigen? Welcher neue Nachteil stellt sich dann ein?
Bäume können schieflastig werden, entarten (=> Hohe Zugriffszeit). Mit ausgeglichenen Bäumen ( B-Bäume, B*-Bäume, AVL-Bäume). Kann dies verändert werden, aber dann hoher Aufwand bei häufigen Einfügen oder Entfernen.
Wie unterscheidet sich eine relationale DB von nicht relationalen DB?
Relationale DB bestehen ausschließlich aus Tabellen und auch der Zugriff erfolgt über diese Tabellen. Beziehungen durch Verknüpfung der Tabellen aufgrund gemeinsamer Attribute (Fremdschlüssel-Primärschlüssel).Nicht durch seq. 1:N (-Beziehung) Väter - Söhne (seq. Speicherung) oder Navigation mit Adressverweisen bei OWNER und MEMBER
Erklären Sie den Begriff Refenzielle Integrität
Korrektheit der Beziehung wird erzielt durch Prüfung in der Detailtabelle ob der Fremdschlüssel beim Einfügen eines neuen Datensatzes auch als Primärschlüssel in der Mastertabelle existiert.
Optimal: Löschweitergabe, Aktualisierungsweitergabe
Optimal: Löschweitergabe, Aktualisierungsweitergabe
Vor und Nachteile von Primärorganisation nach index sequentieller Art
V:Lesezugriff: Schneller sortierter Zugriff, Binärsuche für wahlfreien Zugriff möglich
N:Speicherbedarf: Zusatzaufwand für Indexstruktur und ggf. Überlaufbereiche
N:Einfügen/löschen: Behandelung der Überlaufbereiche, Reorganisation der Indexstrukturen
N:Speicherbedarf: Zusatzaufwand für Indexstruktur und ggf. Überlaufbereiche
N:Einfügen/löschen: Behandelung der Überlaufbereiche, Reorganisation der Indexstrukturen
Vor und Nachteile Primärorganistion nach Hash-Verfahren
V:Speicherbedarf: kein Index nötig,
V:Lesezugriff: schneller Zugriff bei direkter Adresse
V:Einfügen/Löschen: einfacher Algo für suchen&updaten
N:Speicherbedarf:ggf nicht belegte Speicherplätze; reservierte Überlaufbereiche
N:Einfügen/Löschen: ggf neuer Algo oder Speicherbereich nötig
V:Lesezugriff: schneller Zugriff bei direkter Adresse
V:Einfügen/Löschen: einfacher Algo für suchen&updaten
N:Speicherbedarf:ggf nicht belegte Speicherplätze; reservierte Überlaufbereiche
N:Einfügen/Löschen: ggf neuer Algo oder Speicherbereich nötig
Nenne Attribute zur Multilist
Grundstruktur: Einbettung der Zugriffpfade in Sätze (Listenkopf und Zeiger in Daten
Speicherbedarf: Gering, da nur Listenkopf und Zeiger zusätzlich nötig
Lesezugriff: Erstzugriff auf Listenköpfe, dann verkettete Liste schnell durchlaufbar
Einfügen/Löschen: Zeiger setzen, löschen -> geringer Aufwand
Speicherbedarf: Gering, da nur Listenkopf und Zeiger zusätzlich nötig
Lesezugriff: Erstzugriff auf Listenköpfe, dann verkettete Liste schnell durchlaufbar
Einfügen/Löschen: Zeiger setzen, löschen -> geringer Aufwand
Nenne Attribute zur Invertierte Liste
Grundstruktur: Trennung von Sätzen und Zugriffpfaden (Aufbau je einer Indexdatei pro Sekundärschlüssel)
Speicherbedarf: hoch aufgrund der Indexdatei pro Attribut
Lesezugriff: Zugriff auf sortierten Index über Zeiger auf Sätze, schnell und wahlfrei
Einfügen/Löschen: hoher Verwaltungsaufwand, ggf mehrer Indexdateien zureorganisieren
Speicherbedarf: hoch aufgrund der Indexdatei pro Attribut
Lesezugriff: Zugriff auf sortierten Index über Zeiger auf Sätze, schnell und wahlfrei
Einfügen/Löschen: hoher Verwaltungsaufwand, ggf mehrer Indexdateien zureorganisieren
Welche Daten soll eine IST/SOLLanalyse eines DB-Entwurfs enthalten?
Analyse der Datenmenge, Änderungstendenzen
BSP:
max, min durchschnittliche Tupel/Relation
Fluktuation Tupelanzahl
Analyse Datenbenutzung
BSP:
welche Zugriffe werden benötigt
Häufigkeit der Transaktion pro Stunde/Tag..
Anzahl parallerer Transaktionen
Antwortzeiten
BSP:
max, min durchschnittliche Tupel/Relation
Fluktuation Tupelanzahl
Analyse Datenbenutzung
BSP:
welche Zugriffe werden benötigt
Häufigkeit der Transaktion pro Stunde/Tag..
Anzahl parallerer Transaktionen
Antwortzeiten
Wie wird ein Datensatz über dünne Indexe gefunden?
1.Indexeintrag mit dem
größten Suchschlüsselwert, der kleiner oder gleich dem gesuchten
Suchschlüsselwert ist, ermittelen
2.Man beginnt dann bei dem Datensatz auf
den dieser Indexeintrag zeigt und sucht sequentiell auf der entsprechenden Seite
bis der gewünschte Datensatz gefunden ist.
größten Suchschlüsselwert, der kleiner oder gleich dem gesuchten
Suchschlüsselwert ist, ermittelen
2.Man beginnt dann bei dem Datensatz auf
den dieser Indexeintrag zeigt und sucht sequentiell auf der entsprechenden Seite
bis der gewünschte Datensatz gefunden ist.
Wichtiges zum Sekundärschlüssel:
enthält Duplikate: mehrere unterschiedliche Attributkombinationen für eine Datei möglich -> mehrere Sekundärindexe
häufig eingesetzt bei:
direkten und sequentiellen Zugriff auf die Daten
Da sortiert -> Binärsuche
Da Datensätze der indizierten Datei nicht physisch auf dem Sekundärschlüssel sortiert sind -> kann nur als dichter Index auftreten
benötigt mehr Platz als ein Primärindex da größeren Anzahl von Einträgen (Duplikate)
Suchzeit schneller durch Sekundärschlüssel (keine lineare Suche)
häufig eingesetzt bei:
direkten und sequentiellen Zugriff auf die Daten
Da sortiert -> Binärsuche
Da Datensätze der indizierten Datei nicht physisch auf dem Sekundärschlüssel sortiert sind -> kann nur als dichter Index auftreten
benötigt mehr Platz als ein Primärindex da größeren Anzahl von Einträgen (Duplikate)
Suchzeit schneller durch Sekundärschlüssel (keine lineare Suche)
Nenne den unterschied zwischen invertiert und vollständig invertiert
Eine Datei, die einen dichten Sekundärindex bezüglich eines Attributs besitzt, wird auch invertierte Datei bezüglich dieses Attributs genannt.
Eine Datei, die
einen dichten Sekundärindex bezüglich jeden Attributs besitzt, das nicht gleich dem Primärschlüssel ist, wird vollständig invertierte Datei genannt.
Eine Datei, die
einen dichten Sekundärindex bezüglich jeden Attributs besitzt, das nicht gleich dem Primärschlüssel ist, wird vollständig invertierte Datei genannt.
Wichtiges zum Primärindex:
nur einen Primärschlüssel -> nur einen Primärindex
keine Duplikate, d.h. nicht mehrere Suchschlüssel mit gleichem Werten.
Hauptproblem(wie bei sequentiell): Einfügen und Löschen von Datensätzen. (Neben dem Einfügen des
Datensatzes in die indizierte Datei muss auch ein Eintrag in den Index erfolgen)
keine Duplikate, d.h. nicht mehrere Suchschlüssel mit gleichem Werten.
Hauptproblem(wie bei sequentiell): Einfügen und Löschen von Datensätzen. (Neben dem Einfügen des
Datensatzes in die indizierte Datei muss auch ein Eintrag in den Index erfolgen)
Wie kann das Problem bei geclusterten Indexen gelöst werden?
anfangs sortiert, und jeder Seite wird ein gewisser freier Speicherplatzbereich für zukünftige Einfügungen zugesprochen.
Ist dieser freie Platz durch weitere Einfügungen aufgebraucht, werden weitere Einfügungen auf Überlaufseiten ausgelagert.
Nach einiger Zeit wird die Datei dann reorganisiert
(d.h. neu sortiert).
Ist dieser freie Platz durch weitere Einfügungen aufgebraucht, werden weitere Einfügungen auf Überlaufseiten ausgelagert.
Nach einiger Zeit wird die Datei dann reorganisiert
(d.h. neu sortiert).
Was ist eine Bereichsanfrage
bindet nicht jedes Feld des Suchschlüssels an ein Gleichheitsprädikat.
So bedeutet die Anfrage nach Einträgen mit Name =
„Kunze, Karl“, dass für das Gehalt-Feld jeder vorhandener Wert akzeptabel ist
Man kann aber auch z.B. Name < „Meyer, Alfons“ und Gehalt >
4700 fragen
So bedeutet die Anfrage nach Einträgen mit Name =
„Kunze, Karl“, dass für das Gehalt-Feld jeder vorhandener Wert akzeptabel ist
Man kann aber auch z.B. Name < „Meyer, Alfons“ und Gehalt >
4700 fragen
Mehrdimensionale Indexstrukturen:
keine lineare Ordnung
Organisation der Indexeinträge erfolgt häufig anhand räumlicher Beziehungen
Jeder Wert eines zusammengesetzten Suchschlüssels mit k Feldern wird dabei als ein Punkt im k-dimensionalen Raum aufgefasst, d.h. jeder der k Feldtypen spannt
eine Dimension auf.
Organisation der Indexeinträge erfolgt häufig anhand räumlicher Beziehungen
Jeder Wert eines zusammengesetzten Suchschlüssels mit k Feldern wird dabei als ein Punkt im k-dimensionalen Raum aufgefasst, d.h. jeder der k Feldtypen spannt
eine Dimension auf.
Nenne ein Beispiel für eindimensionale Indexstrukturen
Standarddaten wie alphanumerische Daten.
Position eines Feldes im Suchschlüssel gibt Priorität beim Sortieren an, d.h. ein Feld an i-ter Position wird in i-ter Priorität sortiert
Bereichsanfragen auf dem jeweils ersten Feld können aufgrund der Nähe sehr effizient beantwortet werden, während eine Bereichsanfrage auf dem zweiten Feld eine lineare Suche auf dem gesamten Index
erfordert.
Position eines Feldes im Suchschlüssel gibt Priorität beim Sortieren an, d.h. ein Feld an i-ter Position wird in i-ter Priorität sortiert
Bereichsanfragen auf dem jeweils ersten Feld können aufgrund der Nähe sehr effizient beantwortet werden, während eine Bereichsanfrage auf dem zweiten Feld eine lineare Suche auf dem gesamten Index
erfordert.
Nenne Beispiele für mehrdimensionale Indexstrukturen
sind geometrische Indexstrukturen
wesentlich komplexer als eine eindimensionale Indexstruktur
Einträge werden gemäß Ihrer Nähe im zugrundeliegenden k-dimensionalen Raum abgespeichert.
Alle Felder im Suchschlüssel werden also mit gleicher (!) Priorität behandelt.
Bereichsanfragen können dann sehr effizient ausgewertet werden.
wesentlich komplexer als eine eindimensionale Indexstruktur
Einträge werden gemäß Ihrer Nähe im zugrundeliegenden k-dimensionalen Raum abgespeichert.
Alle Felder im Suchschlüssel werden also mit gleicher (!) Priorität behandelt.
Bereichsanfragen können dann sehr effizient ausgewertet werden.
Wie sucht man bei einem einstufigen
Index?
Index?
ein Index besteht aus einer einzigen geordneten Datei besteh
binäre Suche wird auf dem Index angewendet
Binäre Suche erfordert für einen Index mit b Seiten 1+ ld b Seitenzugriffe.
Bei Überlaufseiten : keine binäre Suche möglich -> sequentielle Suche mit b Seitenzugriffen
-> -> kostenintensiv
binäre Suche wird auf dem Index angewendet
Binäre Suche erfordert für einen Index mit b Seiten 1+ ld b Seitenzugriffe.
Bei Überlaufseiten : keine binäre Suche möglich -> sequentielle Suche mit b Seitenzugriffen
-> -> kostenintensiv
Wie wird bei mehrstufigen Indexen gesucht?
erfordert 1+ logr b Seitenzugriffe was schneller als binäre Suche ist, falls r > 2
Ein mehrstufiger Index mit n Einträgen in der ersten Stufe besitzt ungefähr k Stufen, wobei k = logr n1
Bedingung: die Suchschlüssel der ersten Stufe sind voneinander verschieden und die Einträge haben eine fixe Länge
Ein mehrstufiger Index mit n Einträgen in der ersten Stufe besitzt ungefähr k Stufen, wobei k = logr n1
Bedingung: die Suchschlüssel der ersten Stufe sind voneinander verschieden und die Einträge haben eine fixe Länge
Vor-und Nachteile mehrstufiger Index? Und nennen sie die Lösung für das Problem
V: Reduktion der benötigten Anzahl an Seitenzugriffen anhand eines Suchschlüssels,
N:
Probleme des Einfügens und Löschens, da alle
Stufen des Index physisch sequentielle Dateien sind
Lösung: ein mehrstufiger Index kann benutzt werden, der die Seiten nicht vollständig mit Einträgen füllt, sondern auf jeder
Seite Platz für neue Einträge lässt.
-> dynamischen, mehrstufigen Indexen, zu deren bekanntesten Vertretern der B-Baum und der B+-Baum zählen.
N:
Probleme des Einfügens und Löschens, da alle
Stufen des Index physisch sequentielle Dateien sind
Lösung: ein mehrstufiger Index kann benutzt werden, der die Seiten nicht vollständig mit Einträgen füllt, sondern auf jeder
Seite Platz für neue Einträge lässt.
-> dynamischen, mehrstufigen Indexen, zu deren bekanntesten Vertretern der B-Baum und der B+-Baum zählen.
Nenne Numerische Datentypen! Welche Indexstrukturen bieten sich für alphanumerische Daten an?
numerischen Datentypen: integer real, String-Datentypen, sowie Boolesche Datentypen
-> einfache Struktur ( im Gegensatz zu den geometrischen Datentypen)
-> -> eindimensionale Strukturen, umfassen
indexsequentielle Zugriffsmethode, die B-Baum-Familie und hashbasierte Indexstrukturen
-> einfache Struktur ( im Gegensatz zu den geometrischen Datentypen)
-> -> eindimensionale Strukturen, umfassen
indexsequentielle Zugriffsmethode, die B-Baum-Familie und hashbasierte Indexstrukturen
Was ist eine indexsequentiellen Zugriffsmethode und wie funktioniert sie? Welche Zugriffsmöglichkeiten bietet dies?
ein mehrstufiger, dünner Primärindex
diese Struktur (mit Ausnahme von Überlaufseiten) ist statisch
d.h. sie wird zu Beginn einmal angelegt und (ausgenommen bei
Reorganisationen) danach nie wieder geändert
Datensätze werden dabei als sequentielle Datei organisiert, worüber dann ein mehrstufiger, dünner Primärindex aufgebaut wird
Möglichkeiten für zwei Zugriffsmethoden:
1. der Zugriff kann auf Daten unter Ausnutzung der
sortierten Speicherung, d.h. der sequentiellen Organisation erfolgen
2. unter Verwendung des Index mittels binärer Suche
diese Struktur (mit Ausnahme von Überlaufseiten) ist statisch
d.h. sie wird zu Beginn einmal angelegt und (ausgenommen bei
Reorganisationen) danach nie wieder geändert
Datensätze werden dabei als sequentielle Datei organisiert, worüber dann ein mehrstufiger, dünner Primärindex aufgebaut wird
Möglichkeiten für zwei Zugriffsmethoden:
1. der Zugriff kann auf Daten unter Ausnutzung der
sortierten Speicherung, d.h. der sequentiellen Organisation erfolgen
2. unter Verwendung des Index mittels binärer Suche
Wie wird index-sequentielle Zugriffsstruktur in einem Baum umgesetzt?
statische Baumstruktur
Knoten: entspricht einer Seite der Indexstruktur
Kante von einem Vaterknoten zu einem Sohnknoten: entspricht einem Zeiger des Index von einer Seite der Stufe i zu einer Seite der Stufe i+1
Schlüsselwerte eines Knotens (Primärschlüsselwert): aufsteigend sortiert
Blattseiten: enthalten entweder die Datensätze oder aber
die Indexeinträge auf die Datensätze, die in einer separaten Datei abgelegt sind.
Nichtblattseiten: nur Suchschlüssel, die als Separatoren zum
schnellen Auffinden der richtigen Blattseite dienen
Knoten: entspricht einer Seite der Indexstruktur
Kante von einem Vaterknoten zu einem Sohnknoten: entspricht einem Zeiger des Index von einer Seite der Stufe i zu einer Seite der Stufe i+1
Schlüsselwerte eines Knotens (Primärschlüsselwert): aufsteigend sortiert
Blattseiten: enthalten entweder die Datensätze oder aber
die Indexeinträge auf die Datensätze, die in einer separaten Datei abgelegt sind.
Nichtblattseiten: nur Suchschlüssel, die als Separatoren zum
schnellen Auffinden der richtigen Blattseite dienen
Wie funktionieren Einfüge- und Löschoperationen bei einer statische Baumstruktur?
nur in den Blattseiten durchgeführt, nicht bei Nichtblattseiten
setzen das Suchen und Finden der richtigen Blattseite voraus
soll eingefügt werden aber Blattseite voll:
zusätzliche Seite (Überlaufseite) die den Eintrag aufnimmt
setzen das Suchen und Finden der richtigen Blattseite voraus
soll eingefügt werden aber Blattseite voll:
zusätzliche Seite (Überlaufseite) die den Eintrag aufnimmt
Wichtiges zu B+Bäume
Indexeinträge k* ausschließlich in den Blattknoten enthalten
die Nichtblattknoten enthalten nur Suchschlüssel k und Verweise auf die Wurzeln von Teilbäumen.
Blattseiten in doppelt verketteten Liste-> kann in beiden Richtungen durchlaufen werden ->Bereichsanfragen
Jeder innerer Knoten mit n Suchschlüsseln hat genau n + 1 Söhne.
Welche verschiedenen Hash-Verfahren gibt es?
statisch: Problem: lange Ketten von Überlaufseiten, die die Performance negativ beeinflussen
dynamisch: flexible Anpassung der Anzahl der Überlaufseiten an den jeweiligen Speicherplatzbedarf
erweiterbare: benutzt Verzeichnisstruktur, um Einfügen und Löschen effizient ohne irgendwelche Überlaufseiten zu unterstützen
linear: intelligente Strategie, um neue Behälter zu erzeugen. Einfügen und Löschen werden effizient ohne Einsatz einer Verzeichnisstruktur unterstützt
dynamisch: flexible Anpassung der Anzahl der Überlaufseiten an den jeweiligen Speicherplatzbedarf
erweiterbare: benutzt Verzeichnisstruktur, um Einfügen und Löschen effizient ohne irgendwelche Überlaufseiten zu unterstützen
linear: intelligente Strategie, um neue Behälter zu erzeugen. Einfügen und Löschen werden effizient ohne Einsatz einer Verzeichnisstruktur unterstützt
Wie viele Zugriffe benötigt das Hashverfahren für Tranksaktionen?
n/2rN Zugriffe für eine erfolgreiche Suche
n/rN+1 Zugriffe für ein erfolgreiches Einfügen mit Rückschreiben der Seite
n/2rN +1 Zugriffe für das Löschen eines existierenden Indexeintrags oder das Ändern eines existierenden Indexeintrags sowie das Zurückschreiben der Seite
n/rN Zugriffe für eine erfolglose Suche oder das Überprüfen, dass eine Indexeintrag nicht in der Datei vorhanden ist.
n/rN+1 Zugriffe für ein erfolgreiches Einfügen mit Rückschreiben der Seite
n/2rN +1 Zugriffe für das Löschen eines existierenden Indexeintrags oder das Ändern eines existierenden Indexeintrags sowie das Zurückschreiben der Seite
n/rN Zugriffe für eine erfolglose Suche oder das Überprüfen, dass eine Indexeintrag nicht in der Datei vorhanden ist.
Flashcard set info:
Author: Der Kurssprecher
Main topic: Datenbanken
Topic: Datenbanktechnik
Published: 14.04.2016
Card tags:
All cards (92)
no tags
