Dateistrukturen

Eine Datei besteht aus einer Ansammlung von Datensätzen ( Records). Eines der Hauptelemente im File-System ist die Organisation und die Struktur der Datensätze. Nun möchte ich die logische Struktur der Dateien behandeln.

Bei der Wahl der Dateistruktur sind folgende Kriterien wichtig:

Schneller Zugriff

Leichtes Ändern und Aufbessern

Geringer Platzverbrauch

Einfache Wartung

Hohe Zuverlässigkeit

Die Priorität dieser Kriterien hängt mit den Applikationen zusammen, für die die Datei benutzt wird. Wenn zum Beispiel eine Datei im Hintergrund (Batch) bearbeitet wird, bei der alle Records jederzeit benützt werden, ist der schnelle Zugriff auf einen einzelnen Record nicht von hoher Bedeutung. Bei einer CD-ROM, die niemals geändert werden kann ist der 2. Punkt nicht von Bedeutung.

Es gibt sehr viele Dateistrukturen, so dass ich nur die fünf wichtigsten behandeln will. Die meisten Strukturen in den derzeit bekannten Systemen werden nach diesen fünf Typen aufgebaut.

Das Pile (Haufen, in einer Kette)

Die sequentielle Datei

Die index-sequentielle Datei

Die indexierte Datei

Die direkte oder gehashte Datei

Das Pile

Das Pile ist die einfachste Struktur, die man verwenden kann. Hier werden die Daten in der Reihenfolge gespeichert, in der sie hineinkommen. Dies sieht so aus:

Jeder Record besteht aus einen Satz der gespeichert wurde. In dieser Struktur ist es einfach die Daten zu sammeln und zu speichern. Die Datensätze können verschiedene Inhalte in irgendeiner Reihenfolge enthalten. Jedes Feld sollte selbstbeschreibend sein und den Feldnamen und einen Wert enthalten. Die Länge eines Feldes wird durch einen Begrenzer angegeben, der vom Programm als untergeordnetes Feld angesehen wird und einen vorgegebenen Wert besitzt.

In dieser Art gibt es keine Struktur. Deshalb wird der Dateigriff durch eine lange Suchprozedur erschwert. Wenn man einen bestimmten Record finden will, muss man in jeden Record sehen und den Inhalt mit dem gesuchten vergleichen bis man ihn gefunden hat. Wenn man verschiedene Sätze mit dem gleichen Inhalt sucht, muss man die ganze Datei durchsuchen.

Dir Pile Dateien werden nicht sehr oft angewendet. man verwendet sie nur, wenn man Daten vor dem Verarbeiten speichert, oder wenn Daten nur schwer zu organisieren sind. Das Pile File nutzt den Platz gut, wenn die Daten in Größe und Struktur variieren.

Die sequentielle Datei

Die sequentielle Datei ist Die Form, die am häufigsten benutzt wird. Ein Datensatz(Record) wird in verschiedene Felder aufgeteilt. Hier wird ein fixes Format für die Felder benutzt. Alle Felder haben dieselbe Länge und haben auch eine vorgegebene Reihenfolge. Man muss nur noch die Werte nur noch eingeben. Die Namen der Felder und die Länge sind ein Teil der Datei und müssen nicht extra gespeichert werden.

Ein spezielles Feld, normalerweise das erste, wird als Schlüsselfeld benutzt. Das Schlüsselfeld identifiziert den Datensatz. Das Schlüsselfeld ist für alle Datensätze verschieden, so dass man immer eine eindeutige Nummer als Schlüssel besitzt. die Datensätze werden noch dem Schlüsselfeld sortiert. Bei einem Text-schlüssel sind die Datensätze alphabetisch sortiert und bei einem numerischen nach den Zahlen.

Schlüssel Felder

(Records)

Die sequentiellen Dateien werden üblicherweise für Hintergrundoperationen benutzt und sind auch die beste Version für die se Operationen. Mit der sequentiellen Dateistruktur kann man auf Bänder und auf Platten gleich gut speichern. Für Änderungen bittet diese Struktur nur geringe Leistung. Bei einem zugriff auf die Daten muss man das ganze File nach einem gleichen Schlüssel durchsuchen. Diesen Zugriff kann man aber beschleunigen wenn man das ganze oder einen großen Teil des Files in den Hauptspeicher befördern kann. Man kann dann schnellere Suchalgorytmen benutzen. In großen Dateien wird das suchen auch verzögert. Üblicherweise werden die Daten in einer einfachen Ordnung gespeichert um der physikalischen Ordnung auf der Platte oder am Band gleich zu kommen. Hier werden üblicherweise die neuen Datensätze in einem Pile-File gespeichert. Von zeit zu Zeit werden dann die Datensätze in die sequentielle Datei eingefügt, um die Datei in Ordnung zu behalten.

Die index-sequentielle Datei

Die populärste Form um die Schwachstellen der sequentiellen Datei zu übergehen ist die Form von index-sequentiellen Dateien. In dieser Form wird die Hauptcharakteristik von sequentiellen Dateien behalten. Die Datensäzte werden mit Hilfe eines Schlüsselfeldes geordnet. Aber es werden noch 2 Zusatzfunktionen dazugegeben: die erste ist ein Index, um einen wahllosen zugriff zu ermöglichen und die zweite ist ein Übertrags-File. Der Index ermöglicht einen schnellen Zugriff auf die Daten ohne langes Suchen. Eine Indexnummer kann mehr als einen Datensatz beinhalten. Die Übertragsdatei ist eine sequentielle Datei in der Überträge der Vorgängerdatei gespeichert werden. Ein Pointer zeigt auf den jeweiligen Datensatz.

In der einfachsten Form der Index nur eine Schicht. Hier ist er eine sequentielle Datei. Jeder Datensatz im Index besteht dann aus zwei Feldern: ein Schlüsselfeld, welches denselben Inhalt hat wie der Schlüssel in der Hauptdatei, und einen Pointer auf die Hauptdatei. Wenn man nun ein spezielles Feld sucht, muss man nun nach dem höchsten Schlüssel suchen, der gleich mit dem Schlüssel ist oder der vor dem gewünschten Schlüssel liegt. Die Suche wird in der Hauptdatei fortgesetzt, auf die der Pointer im Index verweist.

Um die erhöhte Leistungsfähigkeit dieser Struktur darzustellen gebe ich ein Beispiel:

Um in einer sequentiellen Datei mit einer Million Datensätze nach einem speziellen Schlüssel zu suchen, muss man ungefähr 500.000 Zugriffe durchführen um ihn zu finden. Um jetzt in einer index-sequentielle Datei mit denselben Inhalten nach einen bestimmten Datensatz zu durchsuchen, benötigt man 500 Zugriffe im Index und 500 Zugriffe für die Hauptdatei. Hier schrinkt die Zahl der Zugriffe auf 1000.

Wenn man die Übertragsdatei benutzt, werden die neuen Datensätze in der Übertragsdatei gespeichert. Der Vorgänger des neuen Datensatzes im Hauptfile besitzt einen Pointer auf den neuen Datensatz. Wenn auch der Vorgänger in der Übertragsdatei ist, dann muss der Pointer geändert werden.

Die index-sequentielle Datei ermöglicht einen sehr schnellen Zugriff auf einen bestimmten Datensatz, ohne seine sequentielle Natur aufzuheben..

Um das ganze File sequentiell zu durchsuchen muss man das Hauptfile durchsuchen, bis man einen Pointer auf die Ãœbertragsdatei findet. Dann wird die Ãœbertragungsdatei durchsucht, bis man einen Null-Pointer gefunden hat. Nachher setzt man die Suche im Hauptfile fort, wo man es verlassen hat.

Um diese Struktur noch zu beschleunigen kann man den Index mit mehreren Stufen benutzen. Die erste Stufe ist eine sequentielle Datei. Auf diesen Index kommt dann noch ein höherer Index. Bei einer Datei mit 1 Million Datensätze Hat man einen höheren Index mit 100 Einträgen. Diese verweisen auf 10.000 Einträge im niedrigeren Index. Die Suche beginnt im höheren Index. Dort benötigt man 50 Zugriffe um in den nächsten Index zu springen. In diesen Index benötigt man auch ca.50 Zugriffe. Im Hauptfile braucht man auch wieder 50 Zugriffe. Im Vergleich zu einer sequentielle Datei und einer index-sequentiellen Datei, die nur einen Index hat ist die Ersparnis enorm. Die Zugriffe werden von 500.000 auf 1000 und dann auf 150 beschränkt.

Die indexierte Datei

Wenn man nun in einem index-sequentiellen File nach etwas anderem sucht als einen Schlüssel, dann wird die Effizienz des index-sequentiellen Files eingeschränkt. Um diese Flexibilität zu erreichen, dann muss man mehrere Indizes erstellen. Jede Art von Feldtyp in einem Datensatz besitzt einen Index. Die Datensätze können nur durch ihren Index erreicht werden. Deshalb kann die Position der Felder egal sein, Hauptsache ein Pointer aus einem Index zeigt auf das Feld. Es können auch Datensätze mit verschiedener Länge gespeichert werden.

Es werden bei dieser Form zwei Typen von Indizes verwendet: Der erste ist ein Index für jeden Datensatz in der ganzen Datei. Der Index selbst wird als sequentielle Datei verwaltet. Der zweite Index ist der Teilindex. Er zeigt auf jedes Feld, das möglicherweise schnell benötigt wird, oder nach dem gesucht werden soll. Wenn ein neuer Datensatz eingetragen wird, muss man alle Indizes ändern.

Die direkte oder gehashte Datei

Die direkte oder gehashte Datei wird dort gefunden, wo man direkten Zugriff zu jeden Block einer bekannten Adresse benötigt. Hier wird auch ein Schlüsselfeld benötigt.

Direkte Dateien werden dann benutzt, wenn man schnellen Zugriff benötigt. Dies geschieht z.B. bei Directories.

1287 Worte in "deutsch"  als "hilfreich"  bewertet