Modul 5 - Dateiorganisation und Zugriffsstrukturen

Question 1

Agenda

Answer 1

1. Allgemeines
2. Primär- und Sekundärindizes
3. Speicherverfahren
   a) Heap
   b) Sequentiell
   c) Indexsequenziell
   d) Indiziert-nichtsequenziell
4. Baumverfahren (evtl. weglassen da in DBI)
5. Hash Verfahren
6. Spezielle Speicherverfahren

Question 2

Was bedeutet Dateiorganisation und Zugriffsstrukturen im Kontext von Datenbanken und welchen Zweck haben die beiden Konzepte in der Datenbankdomäne?

Answer 2

• 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)

Question 3

Definition Dateiorganisationsform

Answer 3

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

Question 4

Definition Zugriffspfad

Answer 4

Zugriffspfad:
• jede über die grundlegende Dateiorganisationsform hinausgehende
Zugriffsstruktur
• Wie jede Indexdatei über eine interne Relation

Question 5

Worst Case: Unsortierte Daten ohne Zugriffspfad

Answer 5

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

Question 6

Composite Index

Answer 6

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

Question 7

Definition Primärschlüssel

Answer 7

Unterstützung durch Primärschlüssel:
o Wesentliche Eigenschaft: Duplikatfreiheit der zugeordneten Attributwerte
o Identifizierende Attributmenge
o Verknüpfung von Relationen

Question 8

Definition Sekundärschlüssel

Answer 8

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

Question 9

Primärindex vs. Sekundärindex

Answer 9

• 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

Question 10

Indexdatei

Answer 10

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

Question 11

Definition Dünn besetzter Index

Answer 11

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.

Question 12

Definition Dicht besetzter Index

Answer 12

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.

Question 13

Definition Geclusterter Index

Answer 13

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

Question 14

Definition nicht-Geclusterter Index

Answer 14

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

Question 15

Statische vs. dynamische Struktur

Answer 15

• 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

Question 16

Statische Verfahren

Answer 16

Heap → wahllos
• Indexsequenziell → Daten sortiert nach Index
• Indiziert-nichtsequenziell → Index greift auf Daten zu, aber Daten unsortiert

Question 17

Statische Verfahren 1: Heap-Organisation

Answer 17

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

Question 18

Heap: Operationen

Answer 18

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)

Question 19

Vorteil und Nachteil der Heap Datenorganisationsform

Answer 19

• Vorteile:
o Extrem schnelle insert
o Einfügen erzwingt kein Verschieben anderer Tupel
• Nachteil:
o Maximaler Aufwand beim lookup (und also delete)

Question 20

Statisches Verfahren 2: Sequenzielle Speicherung

Answer 20

Datensätze werden sortiert abgelegt:
Z.B. nach Kundennummern sortiert

Sortierung erfolgt nach einem Sortierattribut und in nicht nach einem Index

Question 21

Operationen der Sequentiellen Speicherung

Answer 21

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

Question 22

dynamisches Verfahren 1: Index Sequenzielle Speicherung

Answer 22

• Sequenzielle Dateiorganisation ergänzt durch eine Indexdatei über dem
Sortierattribut der sequenziellen Datei
• Sortierung der Hauptdatei und die Sortierung der Indexdatei stimmen
überein

Question 23

indexsequenzielle Datei als Baumdarstellung

Answer 23

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

Question 24

Aufbau der Indexdatei bei indexsequenzieller Speicherung:

Answer 24

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

Question 25

Aufbau der Hauptdatei:

Answer 25

Alle Datensätze werden bezüglich einer Attributkombination sequenziell gespeichert

Question 26

Probleme der indexsequenziellen Speicherung

Answer 26

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

Question 27

Indexsequenzielle Dateiorganisation:

Mehrstufiger Index

Answer 27

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

Question 28

Operationen bei indexsequentiellen

Dateien

Answer 28

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

Question 29

Probleme indexsequentieller

Dateien

Answer 29

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

Question 30

Dynamisches Verfahren 2: Indexiert-nichtsequentieller

Zugriffspfad

Answer 30

(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

Question 31

Indexiert-nichtsequentieller

Zugriffspfad: Aufbau der Indexdatei

Answer 31

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

Question 32

Operationen auf indexiertnichtsequentiellen Zugriffpfaden

Answer 32

• 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

Question 33

Definition Baumverfahren

Answer 33

• Stufenanzahl (Index) dynamisch verändern
• Wichtigste Baumverfahren: B-Bäume und ihre Varianten
• B-Baum-Varianten Grundtechnik in allen Datenbanksystemen

Question 34

Klassische Hash-Verfahren

Answer 34

• 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

Question 35

Operationen bei Hash Verfahren

Answer 35

• 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

Question 36

Einsatz von Hash-Verfahren in

Datenbanken

Answer 36

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

Question 37

Hash-Verfahren in DB: Operationen

Answer 37

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)

Question 38

Probleme bei Grundversion

Hashverfahren

Answer 38

•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

Question 39

Klassisches vs dynamisches Hashing

Answer 39

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.

Question 40

Spezielle Indexstrukturen

Answer 40

• 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

Question 41

Mehrdimensionale

Speichertechniken

Answer 41

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