Modul 5 - Dateiorganisation und Zugriffsstrukturen Flashcards
(41 cards)
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
