Datenbanksysteme Klausurvorbereitung

Speicher- und Indexstrukturen

Eigenschaften idealen Speichers

nicht-funktionale Eigenschaften

nahezu unbegrenzte Speicherkapazität
kurze Zugriffszeit bei wahlfreiem Zugriff
niedrige Zugriffskosten
geringe Speicherkosten

funktionale Eigenschaften

nichtflüchtig
Unterstützung logischer und arithmetischer Verknüpfung

Speicherhierarchie

Verwaltungsaufgaben

Lokalisieren der Datenobjekte
Allokation und Freigabe von Speicherplatz
Ersetzung
Schreibstrategie (write-through vs. write-back)
(Anpassung an verschiedene Transfergranulate zwischen den Ebenen)

Seitenbasierte Organisation

Datensätze werden in größeren physischen Einheiten fester Größe verwaltet. Diese Seiten (Blöcke) werden nur komplett zwischen Haupt- (RAM) und Externspeicher (Festplatten, SSDs) transferiert.

Eigenschaften von Seiten:

gleiche feste Größe
- PostgreSQL-Standard: 8 KB

eindeutige Kennung

Relation entspricht Array von Seiten

in PostgrSQL sogenannte Tablespaces:


xxxxxxxxxx
create tablespace TBLSPCNAME location '/path/..';
create database DTBSNAME tablespace TBLSPCNAME;

Seitenzuordnungsverfahren

Verfahren	Adressierung	Zugriffskosten	Flexibilität
Statische Datei-Zuordnung	direkt	minimal	keine
Dynamische Datei-Zuordnung	über kleine Tabelle	gering	moderat
Dynamische Block-Zuordnung	über große Tabelle	hoch	maximal

Systempuffer

= vorreservierter Speicher von sogenannten Frames
- Frame hält jeweils genau eine physische Seite
hält oft benötigte Seiten vor

Pufferverwaltung

Aufgabe	Implementierungsmöglichkeit
Prüfung, ob Seite im Puffer und wenn ja in welchem Frame	Verwaltung von (Seiten, Frame)-Paaren in Hashmap
Zurverfügungstellen freier Frames	Verkettung der freien Frames in einer Liste
Bestimmung, welche Seiten auf Puffer entfernt werden	Least-Recently-Used (Verkettung belegter Frames nach letztem Nutzungszeitpunkt der Seite)
Schreiben modifizierter Seiten	Absprache mit Transaktionsverwaltung (siehe ACID-Bedingungen)

Zugriffssystem

Datensätze einer Relation sollen auf Seiten abgebildet werden.

Tuple-Identifier (TID, RowID, RID)

= eindeutige Kennung eines Datensatzes innerhalb Relation/Datenbank
zusammengesetzt aus Seitenadresse und relativer Adresse innerhalb Seite
PostgreSQL: Attribut ctid in jeder Relation (muss explizit in select genannt werden)
stabile TIDs = keine Änderung des TID eines Datensatzes bei Migration in eine andere Seite
- Einrichten von Stellvertreter-TID in Primärseite $\le$ 1)

Recordmanager

= verwaltet Datensätze (in Seiten)
zentrale Aufgabe: Suche nach Seite zur Speicherung neuen Datensatzes
- ggf. Anforderung neuer Seite
wünschenswert: Clusterung von Datensätzen (in einer Seite bei häufigem gemeinsamen Zugriff)
Lösungen
- Datensätze konstanter Länge
  - Verkettung von Seiten, die noch Platz haben
- Datensätze variabler Länge
  - komplex

Zugriff auf Tupel einer Relation

Zugriffsvariante	Beschreibung	Visualisierung	Einsatzzweck
Relationen-Scan	Durchlaufen der zur Relation gehörenden Seiten		niedrige Selektivität (Zugriff auf viele Datensätze)
Index-Scan	indirekter Zugriff über Index		hohe Selektivität (Zugriff auf wenige Datensätze)

Beispiel

Suche nach Datensatz mit Schlüssel 1000

Indexe

Standard-Implementierung: B+-Baum
Primär-/Clusterindex auf sortierter Relation
dichter Primärindex = Indexeintrag für jeden Datensatz
dünner (Cluster-)Index
Sekundärindex
- = Indexierung auf einem oder mehreren Nicht-Schlüssel-Attributen
- z.B. Geburtsjahr

Indextrukturen

Ziele
- Effizienter Zugriff auf Datensätze, die bestimmtes Suchprädikat erfüllen.
- kein erheblicher Mehraufwand in puncto Änderungsoperationen und Speicherplatz
Klassifizierung
- exakte Prädikate: dynamische Hash-Verfahren
- Bereichsprädikate und exakte Prädikate: B+-Bäume
- $\rightarrow$ Datenbanksysteme II)

B+-Bäume

im Gegensatz zu
- binären Suchbäumen
  - Externspeicher $\rightarrow$ Minimierung der Seitenzugriffe
    - viele Einträge/Datensätze pro Knoten
    - alle Daten in Blattknoten
- ISAM
  - voll dynamisch(statt statisch) $\rightarrow$ Anpassen der Struktur bei Einfügen/Löschen eines Datensatzes (statt periodischer Reorganisation)
RECAP: Binäre Suchbäume
- $log_2(n+1)$ mit n Datensätzen
- z.B. AVL-Bäume, Rot-Schwarz-Bäume
- worst-case $\rightarrow$ Kosten = Anzahl Externspeicherzugriffe
  - $O(n)$
  - $O(log\ n)$
  - $O(log\ n)$
  - $O(log\ n + r)$ mit r Antworten
- Probleme
  - $\rightarrow$ $\Rightarrow$ schnechte Strukturen
    - worst case: ein Knotenzugriff = ein Plattenzugriff
    - exakte Suche sehr teuer $10⁷$ Datensätzen)
- damit nicht zur Datenverwaltung auf Externspeicher geeignet

Idee: "fette" Knoten mit maximaler Anzahl an Einträgen (so dass gerade noch in Seite passt)

Definition: B+Baum Typ (b, c)

Suchbaum: $\le$ $\ge$ Teilbäume rechts
Jeder Weg von Wurzel zu Blatt hat gleiche Länge
Wurzel $\ge 2$ $\le 2b - 1$ Kinder
Zwischenknoten $\ge b$ $\le 2b-1$ Kinder
Blatt $\ge c$ $\le 2c-1$ Einträge

Beispiel

$b = c = 2, n = 17$

Exakte Suche

Suche Datensatz mit Attributwert 42

Suche Datensatz mit Attributwert 41

auf einen Pfad beschränk $\rightarrow$ $O(h)$ mit Höhe des Baums h

Bereichssuche

Suche alle Datensätze im [40, 50]

Algorithmus
1. durchläuft Suchpfad bis zu Blatt, in dem linke Bereichsgrenze liegt/liegen könnte
  $\rightarrow O(h)$ Knotenzugriffe
2. folgt Blättern bis zu Blatt, der Attributwert größer als rechte Bereichsgrenze enthält
  $\rightarrow O(\frac{r}{c})$ mit r Antworten Blätter werden besucht

Einfügen in B+-Baum

Algorithmus: (Einfügen von Schlüssel k)

Exakte Suche nach k
Einfügen von k
Konfliktbeseitigung (wenn maximale Anzahl der Einträge pro Blatt verletzt)
1. Knotenaufteilung bei der Hälfte
2. Hinzufügen von Verweis auf höherer Ebene: Obergrenze von neuem (aufgeteiltem) Knoten
Konfiktbeseitigung (wenn maximale Anzahl der Kinder pro Zwischenknoten verletzt)
1. Verschieben von mittlerem Eintrag auf höhere Ebene
  Ergebnis:

Löschen aus B+-Baum

Algorithmus: (Löschen von Schlüssel k)

Löschen von k (im Beispiel 24)
Konfliktbeseitigung (wenn minimale Anzahl der Einträge pro Blatt verletzt)
Verschiebe restliche Einträge in rechtes Blatt
Konfliktbeseitigung (wenn maximale Anzahl der Einträge pro Blatt verletzt)
1. Knotenaufteilung bei der Hälfte
2. Hinzufügen des Index (höchster Wert des neuen Knotens) im höheren Knoten

Leistung

Operation	worst-case-Kosten
exakte Suche	$O(log_b\ N)$
Bereichanfrage	$O(log_b\ N + \frac{r}{b})$
Einfügen	$O(log_b\ N)$
Löschen	$O(log_b\ N)$

Speicherplatzausnutzung $\ge 50\%$