Modul 5 - Dateiorganisation und Zugriffsstrukturen Flashcards
Agenda
- Allgemeines
- Primär- und Sekundärindizes
- Speicherverfahren
a) Heap
b) Sequentiell
c) Indexsequenziell
d) Indiziert-nichtsequenziell - Baumverfahren (evtl. weglassen da in DBI)
- Hash Verfahren
- Spezielle Speicherverfahren
Was bedeutet Dateiorganisation und Zugriffsstrukturen im Kontext von Datenbanken und welchen Zweck haben die beiden Konzepte in der Datenbankdomäne?
• Datenbankinhalte werden in physischen Dateien auf Seiten gespeichert
• Auf den Seiten sind die Tupel der Relation in Datensätzen organisiert
• Reines Speichern der Datensätze nicht ausreichend: müssen effizient
zugreifbar sein
Datensätze müssen innerhalb der Dateien geschickt organisiert werden
• Außerdem müssen zusätzliche Strukturen (Indexdateien, Zugriffspfade)
eingerichtet werden
• Verschiedene Zugriffsverfahren (unterscheiden sich nach verschiedenen
Kriterien)
Definition Dateiorganisationsform
Dateiorganisationsform:
• Form der Speicherung der internen Relation
• Grundlegende Dateiorganisationsformen (ohne Index) :
o Heap-Organisation: unsortierte Speicherung
o Sequenzielle Organisation: sortierte Speicherung
o Hash-Organisation: gestreute Speicherung
Definition Zugriffspfad
Zugriffspfad:
• jede über die grundlegende Dateiorganisationsform hinausgehende
Zugriffsstruktur
• Wie jede Indexdatei über eine interne Relation
Worst Case: Unsortierte Daten ohne Zugriffspfad
Statistisch gesehen müsste hierbei die Hälfte aller Datensätze durchsucht werden bis zu
einem Treffer
Deshalb liegen Daten meist sortiert vor und/oder haben mindestens einen
Index
Composite Index
Indizierung von mehreren Spalten. Höhepunkt:= ganze Tabellenzeilen werden indiziert
Beispiel:
o Nachname, Vorname
o „Müller“ gibt es viele, „Hans Müller“ weniger
o Suche nach Hans bringt allerdings nichts
Definition Primärschlüssel
Unterstützung durch Primärschlüssel:
o Wesentliche Eigenschaft: Duplikatfreiheit der zugeordneten Attributwerte
o Identifizierende Attributmenge
o Verknüpfung von Relationen
Definition Sekundärschlüssel
o Neben dem Primärschlüssel zusätzliches Suchkriterium zum Auffinden von Datensätzen
o Sehr sinnvoll zur Unterstützung bestimmter Anfragen
o Kann auch eines oder mehrere Attribute umfassen
o Nicht unbedingt eindeutig (im Gegensatz zu einem Primärschlüssel)
o Kann also mehrere Datensätze als Ergebnis einer Suche liefern:
• Z.B.: In einer Adressdatenbank wird nach dem Namen Müller als Suchkriterium gesucht. Es gibt zahlreiche
Treffer, da der Name Müller ein häufiger Nachname ist
Primärindex vs. Sekundärindex
- Pro interne Relation ein Primärindex, mehrere Sekundärindexe
- Ein Primärindex ist ein Zugriffspfad auf die interne Relation
- Primärindex über Primärschlüssel definiert
•Sekundärindex: jeder weitere Zugriffspfad auf die interne Relation
• Nicht jede interne Relation muss einen Primärindex besitzen
• Einige kommerzielle relationale DBSysteme nutzen in der Regel nur
Sekundärindexe als Zugriffspfad
Indexdatei
Einträge der Form (K, s)
o K = Wert eines Primär- oder Sekundärschlüssels („Suchschlüssel“, Zugriffsattributwert/en)
o s = Datensatz oder Verweis auf einen Datensatz, der K als Attributwert des Schlüssels hat
Definition Dünn besetzter Index
Dünn besetzter Index:
• Nur einige Datensätze sind im Index repräsentiert.
• Interne Relation sortiert nach den Zugriffsattributen => im Index reicht nur
jeweils 1 Eintrag pro Seite der internen Relation:
o Index verweist mit (K1
, S1
) auf den Seitenanführer, d.h. auf den bezüglich der Ordnung ersten Wert auf dieser
Seite
o Nächster Indexeintrag (K2
, S2
) verweist auf Seitenanführer der Nachfolgeseite
o Datensatz mit Zugriffsattributwert Kn wobei K1 ≤ Kn < K2 muss auf Seite von S1 zu finden sein.
Definition Dicht besetzter Index
Dicht besetzter Index:
• Speichert für jeden Datensatz der internen Relation einen Eintrag
in der Indexdatei
• Ermöglicht die Bearbeitung einiger Anfragen ohne Zugriff auf die
gespeicherte Tupel:
o Index nimmt weniger Speicherplatz ein, als die Originaldatei => Kann
deutlich bessere Antwortzeiten ergeben.
Definition Geclusterter Index
Geclusterter Index:
• In der gleichen Form sortiert, wie die interne Relation:
o Z.B. interne Relation mit Kundendaten nach Kundennummern sortiert => Indexdatei über dem Attribut KNr
üblicherweise geclustert
• nicht unbedingt dünn besetzt
• Beispiel Telefonbuch
o Einträge sind sortiert nach Nachname, Vorname und enthalten die komplette Information
Definition nicht-Geclusterter Index
Anders organisiert als die interne Relation
• Beispiele
o Inhaltsverzeichnis in einem Kochbuch: Suche nach Kartoffelpuffer ergibt Seitenanzahl, Rezept findet sich auf
der entsprechenden Seite
o Sekundärindex für Kundendaten-Relation über Attribut Name, aber Datei selbst sortiert nach
Kundennummern -> Sekundärindex nicht geclustert
Statische vs. dynamische Struktur
• Statische Zugriffsstruktur: optimal nur bei bestimmter (fester) Anzahl von zu
verwaltenden Datensätzen
• Dynamische Zugriffsstrukturen: können die Datensätze unabhängig von der
Anzahl optimal verwalten
o in DBMS üblich
Statische Verfahren
Heap → wahllos
• Indexsequenziell → Daten sortiert nach Index
• Indiziert-nichtsequenziell → Index greift auf Daten zu, aber Daten unsortiert
Statische Verfahren 1: Heap-Organisation
Grundlegende und einfachste Dateiorganisationsform
• Heap-Datei oder Stapeldatei
• Datensätze werden völlig unsortiert auf „einem Haufen gestapelt“
• Physische Reihenfolge der Datensätze = zeitliche Reihenfolge der Aufnahme
von Datensätzen in die Datenbank
Heap: Operationen
Insert:
o Erfordert Zugriff auf letzte Seite der Datei
o Letzte Seite pro Datei festgehalten im Data Dictionary
o Genügend freier Platz Satz anhängen.
o Nicht genügend freier Platz nächste freie Seite holen
Delete:
o “Lookup” um den zu löschenden Satz zu suchen
o Dann Löschbit auf 0 setzen (im Header des
Lookup:
o Erfordert ein sequentielles Durchsuchen der Gesamtdatei!
o Somit maximaler Aufwand
o Aufwand kann nur durch einen zusätzlichen Index reduziert werden
o Deshalb werden Heap-Dateien meistens mit Indexen eingesetzt
o Sonst nur für sehr kleine RelationenDatensatzes)
Vorteil und Nachteil der Heap Datenorganisationsform
• Vorteile:
o Extrem schnelle insert
o Einfügen erzwingt kein Verschieben anderer Tupel
• Nachteil:
o Maximaler Aufwand beim lookup (und also delete)
Statisches Verfahren 2: Sequenzielle Speicherung
Datensätze werden sortiert abgelegt:
Z.B. nach Kundennummern sortiert
Sortierung erfolgt nach einem Sortierattribut und in nicht nach einem Index
Operationen der Sequentiellen Speicherung
Insert:
o Sortierung muss eingehalten werden einfügen komplizierter
o Zunächst Seite suchen, auf der der Datensatz eingefügt werden soll
o Datensatz zwischen zwei existierenden Datensätzen einzusortieren:
nachfolgende Datensätze verschieben
im Header-Feld der Seite die Offsets der TID-Zeiger verändern
o Sortiertes einfügen einfacher machen: beim Anlegen oder sequentiellen Füllen einer Datei, jede Seite nur bis zu
gewissem Grad füllen (z.B. 66%)
Delete:
o Lookup um den zu löschende Satz zu suchen
o Dann Löschbit auf 0 setzen (im Header des Datensatzes)
Lookup:
o Schneller durch die Sortierung
o Auf welcher Seite sollen wir starten mit der Suche? -> dazu indexsequenzielle Dateien
dynamisches Verfahren 1: Index Sequenzielle Speicherung
• Sequenzielle Dateiorganisation ergänzt durch eine Indexdatei über dem
Sortierattribut der sequenziellen Datei
• Sortierung der Hauptdatei und die Sortierung der Indexdatei stimmen
überein
indexsequenzielle Datei als Baumdarstellung
o Wurzel des Baumes wäre die Seite der Indexdatei (links)
o Mit Verweise auf die Seitenanführer der Hauptdatei (Datensätze 4711 und 8832)
o Hauptdatei: Datensätze = Blätter des Baumes
Aufbau der Indexdatei bei indexsequenzieller Speicherung:
o Datensätze in Indexdatei sind sortiert nach Primärschlüsselwert
o Struktur der Datensätze in Indexdatei:
(Primärschlüsselwert, Seitennummer)
o Primärschlüsselwert: Ist der Indexwert des ersten Satzes auf der Seite
o Für jede Seite der Hauptdatei: also genau ein Datensatz in Indexdatei
Aufbau der Hauptdatei:
Alle Datensätze werden bezüglich einer Attributkombination sequenziell gespeichert
Probleme der indexsequenziellen Speicherung
Indexdatei kann aus vielen Seiten bestehen o Verkettete Liste von Seiten (kennt nächste aber nicht vorherige) o Diese Indexseiten müssen sequenziell durchsucht werden -> kann zu Problemen führen
Indexsequenzielle Dateiorganisation:
Mehrstufiger Index
Optional: Indexdatei wieder indexsequentiell verwalten => Zweistufiger
Index
• Index zweiter Stufe kann wieder indexsequentiell organisiert sein usw.
=> mehrstufiger Index
• Idealerweise: Index höchster Stufe nur noch eine Seite
• So auch in der Wurzel der Baumstruktur keine sequenzielle Suche über
mehrere Seiten benötigt
Operationen bei indexsequentiellen
Dateien
Lookup (bei einstufiger Indexdatei):
• Sucht einen Datensatz zum Zugriffsattributwert w
• Indexdatei wird sequenziell durchlaufen
• Gesucht wird einen Datensatz zum Zugriffsattributwert w
• Indexdatei wird sequenziell durchlaufen und sucht Satz (v1
, s) (Attributwert
v1
, Satz s) mit v1 ≤ w
• Mögliche Fälle:
o Nächste Satz (v2
, s‘) im Index hat v2 > w:
• => Satz mit Attributwert w ist auf Seite s gespeichert (wenn
vorhanden)
o Satz (v1
, s) ist der letzte Satz der Indexdatei:
• => Satz mit Attributwert w muss auf Seite s gespeichert sein (wenn vorhanden)
• „(v1
, s) „überdeckt“ Zugriffsattributwert w“
Insert (bei einstufiger Indexdatei):
• Zunächst: mit lookup Seite finden
o Auf welcher Seite müsste der Datensatz gespeichert werden
• Falls Platz:
o Satz wird sortiert in der gefundene Seite gespeichert
• Falls kein Platz:
o Neue Seite von der Freispeicherverwaltung holen
o Sätze der „zu vollen“ Seite können gleichmäßig auf alte und neue Seite verteilt werden
o Indexeintrag für neue Seite
delete:
• Zunächst mit lookup Seite finden
• Satz auf Seite löschen (Löschbit auf 0)
• Erster Satz auf Seite => Index anpassen
• Falls Seite nach Löschen leer => Seite an Freispeicherverwaltung zurück,
Index anpassen
Probleme indexsequentieller
Dateien
Bei stark wachsenden Dateien:
o Zahl der Indexseiten wächst
o Suche in den linear verketteten Indexseiten kann ineffizient werden
o (Lösung: mehrstufiger Index)
• Stark schrumpfende Dateien: nur zögernde Verringerung der Index- und
Hauptdatei-Seiten:
o Freier Platz wird erst zurück gegeben an Freispeicherverwaltung wenn ganze Seite leer ist
• Nach vielen Änderungsoperationen:
o Unausgeglichene Seiten in der Hauptdatei
• Neue Seite -> Datensätze werden verteilt -> viel Freiplatz
• Datensatz löschen -> freier Platz auf der Seite
• Unnötig hoher Speicherplatzbedarf
o Zu lange Zugriffszeit
Dynamisches Verfahren 2: Indexiert-nichtsequentieller
Zugriffspfad
(Daten sind indexiert abgelegt, aber der Zugriffspfad (Index) ist nicht
notwendigerweise sequentiell)
• Zur Unterstützung von Sekundärschlüsseln einer Relation
• Verschiedene Zugriffpfade dieser Form pro Datei möglich (über
verschiedenen Sekundärschlüssel)
• Einstufig oder mehrstufig: höhere Indexstufen werden wieder
indexsequentiell organisiert
Indexiert-nichtsequentieller
Zugriffspfad: Aufbau der Indexdatei
Zu jedem Satz der Hauptdatei: ein Satz (w, s) in der Indexdatei:
o (w Sekundärschlüsselwert, s zugeordnete Seite).
• Sekundärschlüsselwert kann mehrfach vorkommen:
o entweder für ein w mehrere Sätze in die Indexdatei
• Sortierung der Indexdatei zunächst nach Sekundärschlüsselwerten, dann nach Seitenadressen
o oder für ein w Liste von Hauptdatei-Adressen
Operationen auf indexiertnichtsequentiellen Zugriffpfaden
• Weitgehend analog zu den Operationen bei indexsequenziellen
Dateien
• Lookup:
o Suchen in Indexdatei nach Sekundärschlüsselwert w
o w kann mehrfach auftreten:
Seiten der ermittelten Seitenadressen müssen dann komplett durchsucht werden
• Insert:
o Zunächst Lookup
o Einfügen in Hauptdatei
o Anpassen der Indexdateien
Delete:
o Zunächst Lookup
o Löschen in Hauptdatei
o Indexeintrag entfernen
Definition Baumverfahren
- Stufenanzahl (Index) dynamisch verändern
- Wichtigste Baumverfahren: B-Bäume und ihre Varianten
- B-Baum-Varianten Grundtechnik in allen Datenbanksystemen
Klassische Hash-Verfahren
• Daten in Hashtabelle gespeichert
• Praxis: Tabelle als Array (Reihe)
• Hashfunktion = Mathematische Funktion, berechnet zu jedem Datensatz
einen Hashwert:
o Schlüssel des Objektes zum berechnen des Hashwertes
o Hashwert wird als Adresse (Bucket) in der Tabelle verwendet
o Hashwert basiert nur auf dem Wert des Zugriffsschlüssels
• Idealfall: jedes Objekt ein eigenes Bucket
• Hashfunktionen müssen aber nicht eindeutig sein, zwei verschiedene
Objekte können denselben Hashwert (Bucket) haben = Kollision
• Kollision benötigt spezielle Behandlung
Operationen bei Hash Verfahren
• Suchen:
oZunächst aus Suchschlüssel Hashwert berechnen
o Hashwert bestimmt Bucket des gesuchten Datenobjektes
o Kollision => direkter Vergleich des Suchschlüssels mit den Objekten
Einsatz von Hash-Verfahren in
Datenbanken
Einsatz als Datenbankindex:
• Schlüsselwerte werden auf Bucket-Adressen abgebildet
• Statt Positionen in einem Array: Hintergrundseiten als Speicherplatz
• Bucket = Speicherbereich von ein oder mehreren Seiten
• Auch Überlauf von Seiten möglich durch Häufung von Kollisionen (mehrere
Strategien dabei möglich)
• Speicherstelle eines Datensatzes kann mit einem einzigen Zugriff gelesen
werden (durch Hashfunktion):
o Dadurch Hash-Tabellen als Speicherstruktur sehr interessant
• Eignung als Dateiorganisationsform natürlich stark abhängig von der Wahl
der Hashfunktion
• Verbreitete Hashfunktion : h(k) = k mod m
Hash-Verfahren in DB: Operationen
Suchen von Datensatz mit Schlüsselwert w mittels lookup:
o h(w) berechnen (Bild von w unter der Hashfunktion h)
o Zugeordnete Zeiger aus Hashverzeichnis holen
o Erste Seite des Buckets über Zeiger holen
o Sätze auf der Seite werden durchsucht
o w wird nicht gefunden -> nächste Seite
o Alle Seiten erfolglos durchsucht -> Satz nicht vorhanden
Ändern mittels modify:
o Suchen von Datensatz mit Schlüsselwert w mittels lookup
o Modifizierende Attribute Teil des Primärschlüssels -> Satz wird gelöscht und neu eingefügt
o Anderenfalls: Attributwerte werden geändert
Einfügen mittels insert:
o Suchen von Datensatz mit Schlüsselwert w mittels lookup
o Satz gefunden: Fehler (Natürlich nur bei Primärindex)
o Satz nicht gefunden:
• in Seite mit Bild von w wird letzter Satz gesucht
• Einzufügende Satz wird dahinter eingetragen
Löschen mittels delete:
o Suchen von Datensatz mit Schlüsselwert w mittels lookup
o Satz wurde gefunden -> wird gelöscht (Bit auf 0)
Probleme bei Grundversion
Hashverfahren
•Leistungsfähigkeit stark abhängig von Hashfunktion
• Schlechte Wahl kann fast alle Datensätze auf die gleiche Seite einordnen
• Beispiel:
o Hashindex von 100 Buckets
o Kundendatensätze identifiziert durch 6-stellige Kundennummer KNr (fortlaufend vergeben)
o Ersten beiden Stellen von KNr als Hashwerte => Datensätze auf wenigen Seiten abgespeichert
o Letzten beiden Stellen von KNr als Hashwerte => Datensätze gleichmäßig auf alle Seiten verteilt
•Anpassung der Hashfunktion an wachsende und schrumpfende
Datenmengen: Fehlende Dynamik:
o Zu großer Speicherbereich erlaubt Wachstum der Datenmengen, aber schlechte Speicherauslastung
o Gut ausgelasteter Speicherbereich: schlechter Performanz bei Wachstum der Datenmengen
• Vergrößerung des Speicherbereichs und damit Änderung der Hashfunktion
einzige Möglichkeit bei Wachstum der Datenmengen:
o Alle Datensätzen müssen neu „gehasht“ werden
• Alternative zur kompletten Reorganisation: dynamischen Hashverfahren
Klassisches vs dynamisches Hashing
Klassische Variante:
• Klassische Hashfunktionen bilden Datenwerte auf einen festen Bereich ab
• Skaliert nicht
• Vergrößerung des Bildbereichs erfordert Festlegung neue Hashfunktion,
erfordert komplettes Neu-Hashen aller Datensätze
• Mangelnde Dynamik
Dynamische Variante:
• Lösung: dynamische Hashverfahren:
o Automatische Vergrößerung oder Verkleinerung des Bildbereichs
o Hashfunktionen mit feste Berechnungsvorschrift, aber deren Bildbereich dynamisch vergrößert werden kann
o Kein komplettes Neu-Hashen erforderlich
o Lineares Hashing, Erweiterbares Hashing, Spiralhashing, Kombinierte Methoden.
Spezielle Indexstrukturen
• Weitere Indexverfahren:
o Basieren auch auf Grundprinzipien der Datenorganisation:
• z.B. ausgeglichene Suchbäumen oder Hashfunktionen
o Berücksichtigen aber zusätzlich Besonderheiten spezieller Anwendungsgebiete
Mehrdimensionale
Speichertechniken
bisherige Speichertechniken eindimensional
Mehrdimensionale Speichertechniken:
• Erlauben symmetrischen Zugriff über mehrere Attributen:
o Z.B. Anfrage nach gut verdienenden jungen Angestellten: Attribut Alter zwischen 22 und 25; Attribut Gehalt
zwischen 80K und 120K
o Statt 2 Anfragen und dann Durchschnitt berechnen: gleich mehrere Attribute berücksichtigen
• Anzahl der unterstützten Attribute bestimmt Anzahl der Dimensionen dieses
Datenraums
• Mehrdimensionale Varianten von B-Bäumen, Mehrdimensionale Varianten
von Hashverfahren
