Dateiorganisation
Ziel einer intelligenten Dateiorganisation ist es, eine größtmögliche Performanz zu erreichen, d.h. mit möglichst wenigen Zugriffen auf externe Speichermedien auszukommen.
In der Regel sind Datenbanken so groß, dass sie nicht komplett in den Hauptspeicher passen. Auch aus Gründen der Persistenz (Hauptspeicher ist flüchtig, z.B. Stromausfall) ist man gezwungen, Datenbanken auf Sekundärspeichermedien (meistens Festplatten) abzulegen.
Datenbanksysteme verwenden Dateien, die Records enthalten, um die Datenbank zu speichern. Datenbank-Dateien lassen sich untergliedern in
heap files (ungeordnete Folge von Records),
sorted files (nach einem Feld geordnete Folge von Records),
hashed files (die Datei hat die Struktur einer Hash-Tabelle),
B-tree files (die Datei ist Abbild eines B-Baums).
Um größere Datentransferraten zu erreichen, werden diese Dateien aber nicht recordweise gelesen oder geschrieben, sondern in größeren Einheiten, den Blöcken. Ein Block hat eine für das Betriebssystem oder das Hardwaremedium geeignete Größe, bei der der Transfer am schnellsten geht, z.B. 4 kByte.
Geordnete Dateien werden ungeordneten vorgezogen, da bei nach einem Feld des Records geordneten Dateien eine Binärsuche nach einem Wert des Felds durchgeführt werden kann. Anstelle einer linear mit der Dateigröße ansteigenden Suchzeit wächst diese bei der Anwendung der Binärsuche nur noch mit dem Logarithmus der Dateigröße.
Ist eine geeignete Hashfunktion gegeben und die Größenordnung der Datensätze ungefähr bekannt, kann mittels einer Datei in Form einer Hash-Tabelle eine nahezu konstante Suchzeit erreicht werden. Bei intelligenteren (dynamischen) Hashverfahren ist die Kenntnis der Größenordnung der zu speichernden Datensätze nicht nötig.
Ein B-Baum ist ein Baum, bei dem alle Blätter auf gleicher Ebene im Baum liegen. Außerdem ist für die Zahl der Verzweigungen je Nichtblatt eine obere und untere Grenze vorgegeben. Für Datenbanksysteme wählt man den maximalen Verzweigungsgrad so, daß ein Knoten gerade in einen Block passt.
Da eine Datei nur nach einem Feld des Records sortiert werden kann, können Indexdateien angelegt werden. Diese sind nach einem anderen Feld sortiert (effiziente Suche) und enthalten Zeiger auf die eigentlichen Datenrecords.
Von einem Primärindex spricht man dann, wenn die Datenbankdatei nach dem selben Feld sortiert ist, wie die Indexdatei. Diese enthält dann einen Eintrag je Block der Datendatei. Durch einen Primärindex kann die Zahl der nötigen Blockzugriffe verkleinert werden. Da der Primärindex nur einen Eintrag je Block enthält, handelt es sich um einenen dünn besetzten (sparse) Datenbankindex.
Ein Sekundärindex liegt vor, wenn die Datendatei und die Indexdatei nach unterschiedlichen Feldern sortiert sind. Ein Sekundärindex ist ein dichter (dense) Datenbankindex, da er einen Eintrag je Record der Datendatei enthält.
In der Regel sind Datenbanken so groß, dass sie nicht komplett in den Hauptspeicher passen. Auch aus Gründen der Persistenz (Hauptspeicher ist flüchtig, z.B. Stromausfall) ist man gezwungen, Datenbanken auf Sekundärspeichermedien (meistens Festplatten) abzulegen.
Datenbanksysteme verwenden Dateien, die Records enthalten, um die Datenbank zu speichern. Datenbank-Dateien lassen sich untergliedern in
heap files (ungeordnete Folge von Records),
sorted files (nach einem Feld geordnete Folge von Records),
hashed files (die Datei hat die Struktur einer Hash-Tabelle),
B-tree files (die Datei ist Abbild eines B-Baums).
Um größere Datentransferraten zu erreichen, werden diese Dateien aber nicht recordweise gelesen oder geschrieben, sondern in größeren Einheiten, den Blöcken. Ein Block hat eine für das Betriebssystem oder das Hardwaremedium geeignete Größe, bei der der Transfer am schnellsten geht, z.B. 4 kByte.
Geordnete Dateien werden ungeordneten vorgezogen, da bei nach einem Feld des Records geordneten Dateien eine Binärsuche nach einem Wert des Felds durchgeführt werden kann. Anstelle einer linear mit der Dateigröße ansteigenden Suchzeit wächst diese bei der Anwendung der Binärsuche nur noch mit dem Logarithmus der Dateigröße.
Ist eine geeignete Hashfunktion gegeben und die Größenordnung der Datensätze ungefähr bekannt, kann mittels einer Datei in Form einer Hash-Tabelle eine nahezu konstante Suchzeit erreicht werden. Bei intelligenteren (dynamischen) Hashverfahren ist die Kenntnis der Größenordnung der zu speichernden Datensätze nicht nötig.
Ein B-Baum ist ein Baum, bei dem alle Blätter auf gleicher Ebene im Baum liegen. Außerdem ist für die Zahl der Verzweigungen je Nichtblatt eine obere und untere Grenze vorgegeben. Für Datenbanksysteme wählt man den maximalen Verzweigungsgrad so, daß ein Knoten gerade in einen Block passt.
Da eine Datei nur nach einem Feld des Records sortiert werden kann, können Indexdateien angelegt werden. Diese sind nach einem anderen Feld sortiert (effiziente Suche) und enthalten Zeiger auf die eigentlichen Datenrecords.
Von einem Primärindex spricht man dann, wenn die Datenbankdatei nach dem selben Feld sortiert ist, wie die Indexdatei. Diese enthält dann einen Eintrag je Block der Datendatei. Durch einen Primärindex kann die Zahl der nötigen Blockzugriffe verkleinert werden. Da der Primärindex nur einen Eintrag je Block enthält, handelt es sich um einenen dünn besetzten (sparse) Datenbankindex.
Ein Sekundärindex liegt vor, wenn die Datendatei und die Indexdatei nach unterschiedlichen Feldern sortiert sind. Ein Sekundärindex ist ein dichter (dense) Datenbankindex, da er einen Eintrag je Record der Datendatei enthält.