Verkettung ? Fragen für Info-Klausur

[Christian Seehase]

Moin VeeJay,

also irgendwie komme ich dabei in's Schleudern, wenn ich mir auf der einen Seite Dein Sourcecodebeispiel ansehe, und dann auf der anderen Seite etwas von Verkettung bei Datenbanken höre.

Im zweiten Falle würde ich, wie Hansa auch, an den Begriff verkettete Listen denken.

Das dahinterstehende Prinzip ist recht einfach:

Jeder Datensatz in einer Datei fängt an einem Bestimmten Byte relativ zum Dateianfang an.
Das heisst, der erste Satz fängt immer am Offset (Dateibeginn + Offset = Position in der Datei) 0 an.
Ist die Datei als verkettete Liste aufgebaut, enthält jeder Satz auch noch den Offset des in der logischen Reihenfolge als nächstes kommenden Datensatzes. Ist dieser Wert z.B. 0 oder ein besonderer Wert, der real nicht vorkommen kann, oder entsprechend festgelegt wird, hat man das Ende der Liste erreicht.
Durch diese Methode ist es dann relativ einfach, eine Satz in der logischen Reihenfolge einzufügen.
Man schreibt ihn an das Ende der Datei, sucht den Satz, der vor diesem kommen muss, merkt sich den Offset des Folgesatzes, und ersetzt ihn durch den des neu hinzugefügten.
Anschliessend, wird dann der gespeicherte Offset des Folgesatzes in das dafür vorgesehene Feld des neuen Satzes geschrieben und fertig.
Löschen geht dann ahnlich (Offset des dem zu löschenden Datensatzes folgenden Satzes in den des vorher kommenden schreiben)
Dadurch entstehen dann, mit der zeit Dateien, die auch viel Datenmüll enthalten, und die man deshalb gelegentlich, komprimieren muss.

Schneller geht's dann mit doppelt verketteten Listen, wo jeder Eintrag den Offset des folgenden und den des vorhergehenden erhält.

Wenn man statt des Offsets Indizes verwendet kann man mit diesem Prinzip auch Arrays verwalten.