Bernd Brodesser <[EMAIL PROTECTED]> writes: > > Baumstruktur heisst, dass die Elemente (Inhalte) nicht in einer linearen > > Liste geführt werden, sondern halt wie ein Baum. Beispiel: Um in einer > > Gut, ist mir schon klar, aber was bedeutet hier Inhalt? Wo stehen
Du hast dich noch nicht allzu intensiv mit Dateisystemen beschäftigt? OK, dann werde ich mal mein Gedächtnis ein wenig strapazieren: Dir ist ja einigermaßen klar, was man so alles prinzipiell speichern muss, also neben den eigentlichen Daten auch diverse Verwaltungsinformationen. Schauen wir uns das mal an einem der simplesten DS an, die man basteln kann, FAT. Hier gibt es keinen kompakten, zusammenhängenden Bereich, die File Allocation Table, in der gespeichert wird, welche Bereiche der Platte belegt sind, d.h. welche Verzeichnisse es gibt, welche Dateien dort drinliegen und vor allem welche Position auf der Platte der *Anfang* der Datei hat, also der 1. Sektor der Datei. Das waren die Verwaltungsinfos. Jetzt die eigentlichen Daten. Über die FAT kommt man an den 1. Sektor der Daten, aber wo liegt der Rest? Na ja, im 1. Sektor der Daten gibt es eine Stelle, an der die Position des 2. Sektors gespeichert ist und im 2. Sektor findet sich neben den eigentlichen Daten auch noch eine Stelle, an der die Position des 3. Sektors gespeichert ist usw. Dieses Verfahren ist einfach und in bestimmten Bereichen sogar sehr effizient und benutzt eben zum Speichern der Daten eine verkettete Liste und für die Verwaltungsinfos eine Bitmap, also einen gesonderten Bereich. IIRC finden sich die Dateiattribute in der FAT, aber da bin ich mir nicht mehr 100%ig sicher. Die meisten Verbesserungen an Dateisystemen hat man lange Jahre nur in die Art der Speicherung der Verwaltungsinformationen gesteckt, um die Verwaltungsinfos näher an die physikalische Position der Daten zu bekommen, um so Zugriffszeiten zu optimieren. Bei großen Platten muss bei FAT der Kopf erstmal an den Anfang der Platte zur FAT und dann zur eigentlichen Position der Daten. Daher gingen viele Ansätze in die Richtung, die Verwaltungsinformationen als Baum einigermaßen gleichmäßig über die Platte zu streuen bzw. so zu verteilen, dass die Verzeichnis- und Dateiinfos ganz in der Nähe der eigentlichen Daten landen. Dazu noch ein paar Versuche, die Daten nicht allzu sehr zu fragmentieren, um so die Perfomance zu steigern. An eine andere Speicherung der *Daten* hat man bei DS lange nicht gedacht, obwohl dies bei Datenbanken schon sehr lange üblich ist und man in der restlichen Informatik eigentlich über die Vorteile von Bäumen Bescheid weiß. Allerdings vermutete man diverse Performance-Probleme bei vielen kleinen Daten. Inzwischen gibt es aber einige Ansätze (u.a. ReiserFS), eben auch die Daten anders zu speichern (hier sollte BeOS nicht unerwähnt bleiben, die haben gleich eine Datenbank als Dateisystem genommen). Und in den meisten Fällen wirde eine Baumstruktur mit ein paar Varianten und Anpassungen für die Speicherung der Daten benutzt wobei natürlich die Verwaltungsdaten wie bei früheren Ansätzen ebenfalls über die Platte gestreut werden, um sie möglichst nah an die Position der Daten, zu denen sie gehören, zu bekommen. > Ich vermute doch mal recht stark, daß in den Datenblöcken nichts > anderes steht als Daten und alles andere anderswo gespeichert, und > das könnte man dann wieder i-node nennen, auch wenn sie wie ein Baum > aufgebaut ist. Oder sehe ich das falsch? Ja, siehst du. :) Die I-Nodes von ext2 sind z.B. die Verwaltungsdaten, also Attribute, Verzeichnisinhalt und Verweis auf den 1. Sektor der Dateien, ähnlich, wie z.B. auch bei OS/2s HPFS oder NTs NTFS (IIRC). In allen Fällen werden die Daten in einer verketteten Liste gespeichert, wobei jeder Datensektor der Datei auch einen Verweis auf den folgenden Sektor enthält, sonst wäre es keine verkettete Liste und Anhängen an Dateien wäre nicht ganz unproblematisch (zeitaufwendig). -- Until the next mail..., Stefan. -- ----------------------------------------------------------- Um sich aus der Liste auszutragen schicken Sie bitte eine E-Mail an [EMAIL PROTECTED] die im Subject "unsubscribe <deine_email_adresse>" enthaelt. Bei Problemen bitte eine Mail an: [EMAIL PROTECTED] ----------------------------------------------------------- $COUNT eingetragene Mitglieder in dieser Liste.
