Post on 05-Apr-2015
transcript
ISAM
Indexed Sequential
Access Method
Sortierte Indizes
Idee:• i.d.R. kleiner als Daten
können schneller durchsucht werden
• Aufbau Index: (key, pointer)
• Insgesamt schnellerer Zugriff
Tree
Index ist kleiner als die
Daten, kann aber
trotzdem recht groß
werden
Vorteil schwindet Index vom Index
(vgl. Binäre Suche)
Zwei Basis-Strukturen
• Indexed Sequential Access Method (ISAM)– für statische Daten
geeignet– Overflow-Page für
neue Einträge
• B / B+ Bäume– Voll dynamische
Index-/Speicherungsstruktur
– Was teuer erkauft wird
Applet zu B-Baum auf:http://www-user.tu-chemnitz.de/~chu/ViA/Applets/Finals/BBaum/
Index, Daten, Overflow
Aufbau• Block- und Datengröße bestimmen Kapazität eines Blockes.
Gibt es initialen Füllungsgrad?• Daten sortiert und sequentiell ablegen, ggf. Füllungsgrad
beachten• Indexkapazität bestimmen, Index anlegen.
Indexblöcke komplett füllen, Indizierung standardmäßig bzgl. Maximalwert Maximalwert in den Daten miteinbeziehen (ZZZZZZZZ)
• Letztlich werden die Overflow-Pages zugeteiltwelche / wieviele Blöcke teilen sich welche Overflow-Pages?
statische Struktur aufgebaut• Zum einfügen richtigen Block bestimmen, wenn Block bereits
gefüllt Overflow-page bestimmenDaten sortiert ablegen
suchen, einfügen und löschen
suchen• Indexeintrag Seite
– Kosten: logfN
f: Anzahl Einträge pro Indexseite
N: Anzahl der Blätter
löschen• auch wieder suchen, dann löschen, wenn nötig
Overflow-page freistellen
einfügen• richtige Stelle suchen• wenn nötig, Overflow-
page zuteilen• Daten sortiert
speichern