# Baumstruktur/Datenstruktur in Datei speichern



## Sekundentakt (6. Dez 2009)

Hallo Gemeinde,

als Schüler (Gymnasium, nicht Berufsschule) ist es äußerst schwierig an verständliches Material aus einem Informatikstudium - speziell zum Thema Datenstrukturen - zu kommen.
Ich möchte eine Struktur, sagen wir mal ein B-Baum oder B+-Baum, in eine Datei speichern.

Es gibt tolle Quellen im Internet, die erklären, wie man so einen Baum erstellt, wie man Knoten rotieren lässt und wie man ihn durchsucht.
Leider beziehen sich all diese Quellen auf einen Baum, welcher im Arbeitsspeicher vorgehalten wird und somit behandelt werden kann, wie jedes andere Objekt.

Mir geht es aber an dieser Stelle darum, einen Baum zu erstellen, ihn in eine Datei zu speichern und ihn - ohne ihn noch einmal komplett in den Speicher einzulesen - manipulieren zu können.

Ich habe aber keinen Schimmer wie ich das Speichern oder Durchsuchen praxisnah anstellen soll. Das einzige Beispiel (STRG + F + "Inorder Traversierung" - dann ist man im richtigen Absatz), was einen guten Speicher-Denkanstoß lieferte, zielte auf einen völlig ausgeglichenen Baum ab. Das mein Baum ausgeglichen ist, ist ein schönes Ziel, kann aber niemals garantiert werden - oder etwa doch?

Weiterhin frage ich mich, wie ich so eine Datei dann durchsuchen soll, ohne sie komplett einzulesen.
Schließlich kann ich nicht sagen, dass ich 10 Bytes weiterspringen muss, um an das Kind zu kommen, weil nicht klar ist, ob die Knoten dazwischen nicht deutlich länger sind und man somit im falschen Knoten landet.

Ziel ist es, nachvollziehen zu können, wie z.B. Datenbanken ihre Daten ablegen und auch den größten Index in so rasanter Geschwindigkeit durchsuchen können.

Ich erhielt hierzu einen Beitrag aus einem Fachinformatiker-Forum:



> Du speicherst, zuerst die Baumstruktur (mindestens von der letzten Abzweigung bis zum Blatt) und danach den Wert
> 
> 
> 
> ...



Leider ging man dann auf weiterführende Fragen nicht mehr ein, z.B. wie so eine Speicherung in der Praxis dann aussehen soll (z.B. vom 500. Knoten bis zum Blatt? -> Das ergibt in der Datei eine umgekehrte Pyramide in meiner Vorstellung).

Ich bin gespannt auf eure Denkanstöße und Referenzen, ein paar Diskussionen zu diesem Thema gab es schließlich schon in dieser Community. 
Danke! 

Kleine Anmerkung vielleicht noch hinten dran:
Da das Thema - zumindest für mich - etwas exotischer zu sein scheint, habe ich diese Fragen auch in anderen Communities gestellt. Wenn es von deren Seite ein paar Rückmeldungen gibt, bring' ich die hier mal direkt mit ein.


----------



## Spacerat (6. Dez 2009)

Ganz banal, mehrere Dateien... In einer Datei liegen die eigentlichen Daten (Daten-Datei). Für jeden Datensatz wird die Maximallänge vorherbestimmt und jeder Datensatz besitzt mindestens ein Index-ID-Feld. In mindestens einer weiteren Datei (Index-Dateien) speichert man für jeden Datensatz die Index-ID, die Position und die eigentliche Länge des Datensatzes. Das Problem, welches man nun hat, ist, dass sich Daten nicht mehr aus der Daten-Datei entfernen lassen, ohne diese vollständig neu zu schreiben. Deswegen muss ein gelöschter Datensatz in der Index-Datei mit Datensatzlänge 0 und ungültiger Index-ID gekennzeichnet werden (übrig bleibt die Position, an welcher Daten eingefügt werden können). Neue Daten werden einfach an das Ende der Daten-Datei angehängt. Dies muss aber erst dann passieren, wenn in der Index-Datei kein Datensatz der Länge 0 mehr auftaucht.
Diese Art Datenspeicherung heist Relativer Datenspeicher und hat keineswegs etwas mit einer Baumstruktur zu tun. BTW.: Hatte mich auch schonmal damit befasst. Ich wollte dazumal grosse Mengen an Zahlen (Primzahlen) speichern. Die Zahlen legte ich Byteweise in einer Baumstruktur ab, damit sie nicht soviel Speicher vergeudeten. Die Datei auf der Platte war jedoch stets unverhältnismässig grösser. Ich kam letztlich zu dem Schluss, dass man Baumstrukturen nicht speichern kann.


----------



## Marco13 (6. Dez 2009)

Ob's 100% passt oder ein technisches Detail ist: Ich werfe mal das Stichwort "Memory Mapped Files" hier rein (hat aber weniger mit den Datenstrukturen zu tun, als vielmehr mit der Implementierung am Ende...)


----------



## Sekundentakt (6. Dez 2009)

Danke für das Feedback euch beiden!
Ich hab' auch gleich eine ganze Wagenladung Fragen parat .



> Ich kam letztlich zu dem Schluss, dass man Baumstrukturen nicht speichern kann.


Man kann alles speichern . Auch Baumstrukturen (siehe Beispiellink). MySQL implementiert z.B. einen B*-Baum in seinem MyISAM-Speicherengine. 
Wenn ich deinen Beitrag richtig interpretiere, war Dein Baum größer als die Ursprungsdatei, weil Du die leeren Stellen mit NULL-Bytes auffüllen musstest, damit jeder Index-Datensatz eine Länge von X hat?
Unter der Bedingung, dass Du deinen Index-Datensätzen eine bestimmte Länge aufzwingst, wäre die Suchgeschwindigkeit natürlich ungemein größer.
Hast Du damals auch mal ausprobiert, wie es wäre, wenn du relativ kurze Index-Werte in eine spezielle Datei für Kurz-Werte schreibst, um Speicherplatz zu sparen?



> Ganz banal, mehrere Dateien... In einer Datei liegen die eigentlichen Daten (Daten-Datei). Für jeden Datensatz wird die Maximallänge vorherbestimmt und jeder Datensatz besitzt mindestens ein Index-ID-Feld. In mindestens einer weiteren Datei (Index-Dateien) speichert man für jeden Datensatz die Index-ID, die Position und die eigentliche Länge des Datensatzes. Das Problem, welches man nun hat, ist, dass sich Daten nicht mehr aus der Daten-Datei entfernen lassen, ohne diese vollständig neu zu schreiben. Deswegen muss ein gelöschter Datensatz in der Index-Datei mit Datensatzlänge 0 und ungültiger Index-ID gekennzeichnet werden (übrig bleibt die Position, an welcher Daten eingefügt werden können). Neue Daten werden einfach an das Ende der Daten-Datei angehängt. Dies muss aber erst dann passieren, wenn in der Index-Datei kein Datensatz der Länge 0 mehr auftaucht.


Das ist 'n sehr interessanter Ansatz! 
Zur Schreibgeschwindigkeit aber eine Frage: War die deines Erachtens nach schnell oder langsam, wenn Du mitten in der Daten-Datei etwas gelöscht bzw. neu beschrieben hast? 
In deinem Falle müssten ja nur NULL-Bytes überschrieben werden, statt dass man tatsächlich Daten einfügt, was die Schreibgeschwindigkeit positiv beeinflussen sollte, oder?

Ein Kontra für eine solche Form der Datenspeicherung wäre allerdings folgender:
Text-Werte mit sehr unterschiedlicher Länge würde ich entweder kürzen oder aufblähen. Beides wäre dabei nicht vorteilhaft. Würde es da nicht mehr Sinn machen, wenn ich in der Indexdatei einmal die Index-ID speichere und dann die Anazhl an Bytes die in der Daten-Datei übersprungen werden müssen, um den Datensatz zu erreichen und zusätzlich die Länge des Datensatzes speichere?

Wenn ich dann einen längeren Datensatz lösche, könnte ich diesen mit ggf. mehreren neuen Datensätzen überschreiben. Das was übrig bleibt, müsste man dann nur regelmäßig "defragmentieren" - erinnert mich irgendwie an Windows.

Zu deiner Index-Datei:
Ich geh davon aus, die ist der Größe nach geordnet. 
Ist die Schreiboperation beim Einfügen eines neuen Index-Datensatzes dann nicht extrem langsam, weil alle Bytes nach dem eingefügten Index nach hinten verschoben werden müssen? Wie umgehst Du das?



> Ob's 100% passt oder ein technisches Detail ist: Ich werfe mal das Stichwort "Memory Mapped Files" hier rein (hat aber weniger mit den Datenstrukturen zu tun, als vielmehr mit der Implementierung am Ende...)


Ich schau mir das mal morgen an, Marco. Der englische Wikipedia-Artikel dazu scheint ein ganz guter Einstieg zu sein.


----------



## Spacerat (7. Dez 2009)

Sekundentakt hat gesagt.:


> Zur Schreibgeschwindigkeit aber eine Frage: War die deines Erachtens nach schnell oder langsam, wenn Du mitten in der Daten-Datei etwas gelöscht bzw. neu beschrieben hast?


Es ist nicht nötig, die Datensätze in der Daten-Datei zu überschreiben. Es genügt den Index in der Index-Datei ungültig zu machen. Der ungültige Index muss natürlich in der Index-Datei weiter aufbewahrt werden, damit die Position in der Daten-Datei nicht redundant wird. Beim nächsten Anfügen von Datensätzen weden dann diese Indexeinträge bevorzugt behandelt. Geschwindigkeitsmässig ist das kaum zu überbieten. Nichtstun geht halt am schnellsten .





Sekundentakt hat gesagt.:


> Ein Kontra für eine solche Form der Datenspeicherung wäre allerdings folgender:
> Text-Werte mit sehr unterschiedlicher Länge würde ich entweder kürzen oder aufblähen. Beides wäre dabei nicht vorteilhaft. Würde es da nicht mehr Sinn machen, wenn ich in der Indexdatei einmal die Index-ID speichere und dann die Anazhl an Bytes die in der Daten-Datei übersprungen werden müssen, um den Datensatz zu erreichen und zusätzlich die Länge des Datensatzes speichere?


...und sich die Länge der frei gewordenen Bytes im Falle der Löschung dieses Datensatzes ebenfalls merken, in der Hoffnung, dass irgendwann einmal ein neuer dort reinpasst? Ich zweifle, das dass gut geht.





Sekundentakt hat gesagt.:


> Wenn ich dann einen längeren Datensatz lösche, könnte ich diesen mit ggf. mehreren neuen Datensätzen überschreiben. Das was übrig bleibt, müsste man dann nur regelmäßig "defragmentieren" - erinnert mich irgendwie an Windows.


Andererseits... könnte klappern. Es ist ohnehin ratsam, hin und wieder mal die gesammte Datenstruktur aufzuräumen.





Sekundentakt hat gesagt.:


> Zu deiner Index-Datei:
> Ich geh davon aus, die ist der Größe nach geordnet.
> Ist die Schreiboperation beim Einfügen eines neuen Index-Datensatzes dann nicht extrem langsam, weil alle Bytes nach dem eingefügten Index nach hinten verschoben werden müssen? Wie umgehst Du das?


Nein. Die Datensätze verbleiben stets an ihren Positionen in der Daten-Datei. Egal welchen Rang das Indexfeld in der Index-Datei hat, die Position (welche ja mit gespeichert wird) bleibt stets dieselbe. Das bedeutet, der Eintrag mit dem kleinsten Index kann in der Index-Datei ganz vorne stehen, obwohl der Datensatz dazu erst ganz am Ende der Daten-Datei auftaucht.





Sekundentakt hat gesagt.:


> Man kann alles speichern...


Das hab' ich mir in dem Bezug mit Zahlen auch gesagt. Aber nein... Es war genau umgekehrt. Der Speicherverbauch des Primzahl-Baumes war um einiges kleiner, als die gespeicherte form auf der Platte, weil von allen Blättern stets die gesamte Strecke bis zum Wurzelknoten als Referenz mitgespeichert wurde. Deswegen war es letzendlich kürzer, die Zahlen als reine Bytefolge in der Datei abzulegen.


----------



## Sekundentakt (7. Dez 2009)

Ich bin etwas verwirrt.



> Es ist nicht nötig, die Datensätze in der Daten-Datei zu überschreiben.


Diese Datensätze werden doch aber nicht mehr benötigt? Okay, man muss sie nicht sofort löschen, aber man muss doch irgendwann einmal aufräumen? 



> Nein. Die Datensätze verbleiben stets an ihren Positionen in der Daten-Datei. Egal welchen Rang das Indexfeld in der Index-Datei hat, die Position (welche ja mit gespeichert wird) bleibt stets dieselbe. Das bedeutet, der Eintrag mit dem kleinsten Index kann in der Index-Datei ganz vorne stehen, obwohl der Datensatz dazu erst ganz am Ende der Daten-Datei auftaucht.


Da hast Du mich missverstanden. Wo die Daten in der Daten-Datei liegen ist egal - dafür habe ich ja den Index.
Mir ging es in meiner Frage um die Index-Datei:
Die Index-Daten sind der Größe nach sortiert.
Mal angenommen ich füge jetzt an das Ende der Datendatei den kleinsten Wert der Datendatei ein, dann müsste der entsprechende Index in der Indexdatei an erster Stelle stehen.
Das würde aber bedeuten, alle vorhanden Index-Einträge um die Anzahl an Bytes des neuen Index-Eintrages nach hinten zu schieben. Mir ging es jetzt darum, wie ich DIESEN Vorgang umgehe / beschleunige. 



> Beim nächsten Anfügen von Datensätzen weden dann diese Indexeinträge bevorzugt behandelt.


Mit andern Worten: Du fügst einen neuen Datensatz ein und nutzt einen alten Indexeintrag, den du lediglich mit neuen Werten bestückst? 

Gesetz dem Fall der ungültige Datensatz repräsentiert einen Wert von 10.
- du fügst nun einen neuen Datensatz mit Wert 100 ein und nutzt dafür den alten Index
- der alte Index zeigt nun auf den neuen Datensatz in der Datendatei
- es zeigt jetzt nichts mehr auf den "gelöschten"/ungültigen Datensatz - wie willst Du da aufräumen?
- der alte Index muss ggf. trotzdem gelöscht und neu in die Index-Datei geschrieben werden, wenn er der Größe nach korrekt eingeordnet werden soll​Ich halte das für etwas problematisch . Oder reden wir hier aneinander vorbei?



> und sich die Länge der frei gewordenen Bytes im Falle der Löschung dieses Datensatzes ebenfalls merken, in der Hoffnung, dass irgendwann einmal ein neuer dort reinpasst? Ich zweifle, das dass gut geht.


... wenn ich einen Index habe, der mir sagt AB x Bytes geht der Datensatz los und er hat eine Länge von y Bytes, dann wäre das Ganze kein Problem - denke ich. Zumindest wenn die Datensätze eine normierte Länge hätten. Ich könnte im Falle einer Löschung des Datensatzes nämlich den Index ungültig machen. Wenn neue Daten reinkommen, überschreibe ich dann den alten Datensatz und muss nur noch den ungültigen Index entsprechend wieder für gültig erklären und seine Position in der Indexdatei neu festlegen, da der Index ja jetzt ggf. auf einen Datensatz zeigt, der Größer/Kleiner/Gleich dem alten Datensatz ist.
Mit einer einheitlichen Datensatzlänge wäre dieses Verfahren glaube ich recht praktisch.
Es unterscheidet sich dabei nur geringfügig von der Lösung, die ich gerade noch kritisiert habe, ist dafür aber auch etwas langsamer, glaube ich. Die Frage wäre doch interessant: "Ist überschreiben langsamer als neu schreiben, wenn die Anzahl der Zeichen identisch ist?" :rtfm:
Bei nichtnormierten Datensatzlängen würde ich davon aber auch die Finger lassen .



> Deswegen war es letzendlich kürzer, die Zahlen als reine Bytefolge in der Datei abzulegen.


Konnte man denn eine bestimmte Primzahl auf diese Weise auch schneller finden, als über eine Baumstruktur?


----------



## Spacerat (7. Dez 2009)

Ich werd's mal versuchen, ohne zu zitieren... Ein Indexeintrag besteht aus folgenden drei Komponenten:
1. Index-ID (ein Datenfeld eines Datensatzes aus der Daten-Datei)
2. Datensatzposition (in Bytes) in der Daten-Datei.
3. aktuelle Länge des Datensatzes (darf nicht länger als die Maximallänge eines Datensatzes sein.)

Das Hinzufügen eines Datensatzes geschieht wie folgt:
1.   Index-Datei nach ungültigen Einträgen absuchen.
1.a Es wurde kein ungültiger Eintrag gefunden: Datensatzposition ist die Länge der Daten-Datei. Datensatz-Datei um 1x Maximale Datensatzlänge erweitern und Datensatz an Datensatzposition schreiben. Neuen Indexeinrag mit Index-Datenfeld, Datensatzposition und Datensatzlänge erstellen.
1.b Es wurde ein ungültiger Eintrag gefunden: Datensatzposition ist gespeicherte Position des Indexeintrags. Daten-Datei muss nicht erweitert werden, da nun ein zuvor gelöschter Datensatz überschrieben wird. Index-Datenfeld und Länge des Datensatzes in gefundenen Indexeintrag schreiben, die Position ändert sich nicht.

Das Löschen eines Datensatzes geschieht wie folgt:
1. Den Indexeintrag des Datensatzes durch setzen der Datensatzlänge 0 und invalidieren der Index-ID ungültig machen. Wieder ändert sich die Position nicht. Siehe dazu, Hinzufügen eines Datensatzes.

Das Auffinden von Daten geschieht ausschliesslich über die Index-Datei(en), wovon es pro Daten-Datei durchaus auch mehrere für verschiedene Suchfelder geben kann. Deswegen ist es auch nicht nötig, Datensätze direkt in der Daten-Datei zu löschen.
Während man mit den Daten arbeitet, kann man die Indexdatei im Speicher behalten. Am besten eignet sich dazu ein TreeSet (obwohl man meistens eher 'ne SortedList bräuchte), welches die Indexeinträge nach der Index-ID sortiert. Wohlgemerkt, die gesammten Einträge, denn ID, Position und Länge gehören fest als Einheit zusammen. Hält man das so ein, ist es auch völlig egal, in welcher Reihenfolge die Einträge in der Datei abgelegt werden, der passende Datensatz zur ID wird immer noch über die Position gefunden.
Damit das ganze funktioniert, müssen stets alle ungültigen Indexeinträge aufbewart werden, damit die Position des Datensatzes zwecks überschreiben mit neuen Daten nicht verloren geht. Dazu kann man sich auch eine weitere Datei (ErasedIndex-Datei) anlegen.





Sekundentakt hat gesagt.:


> Konnte man denn eine bestimmte Primzahl auf diese Weise auch schneller finden, als über eine Baumstruktur?


Nö... Normalerweise würde man solche Zahlen in einem HashSet (also auch eine Baumstruktur) speichern. Ich wollte aber mehr Zahlen als MAX_INTEGER speichern... was recht unüberlegt war, mit nur 2GB Hauptspeicher  ... Egal... Anfängergeschichte...


----------



## Sekundentakt (7. Dez 2009)

> Während man mit den Daten arbeitet, kann man die Indexdatei im Speicher behalten.


Die Frage ist, ob dieses Vorgehen auch dann noch Sinn ergibt, wenn ich einen Index habe, der die Größe meines freien Hauptspeichers übersteigt. 

Deinen Beitrag habe ich so komplett nachvollziehen können. Aber ich glaube, dass ich unter einem Index etwas anderes verstehe, als Du. Ich versuche mal meine Definition eines Indexes zu beschreiben:

Eine Index-Datei enthält einen Index für jeden Datensatz einer Daten-Datei.
Der Index ist sortiert, allerdings nicht nach der Index-ID.
Jeder Index zeigt auf genau einen Datensatz.
Alle Indexe sind nach der Größe des Datensatzes sortiert (z.B. alphabetisch), auf den sie zeigen.

Dadurch ist es für mich möglich die Index-Datei via RandomAccess zu durchlaufen.

Ein Index würde für mich auch etwas anders aufgebaut sein, als es bei Dir der Fall ist, nämlich:
1. Index-ID (ID des Indexes selbst)
2. Datensatz ID (ID des Datensatzes auf den gezeigt wird)
3. Datensatzposition in Bytes in der Daten-Datei
4. aktuelle Länge des Datensatzes
5. Ein Kurz-Ausschnitt mit normierter Länge aus dem Datensatz.

Nach 5. wird der Index sortiert, wobei die Reihenfolge dieser Werte je nach Anforderung variieren kann.
Ich würde dann z.B. via RandomAccess in die Mitte der Indexdatei springen, schauen, ist der Wert dort größer/kleiner als mein Zielwert? 
Wenn er kleiner ist, springe ich in die Mitte der Kleiner-Hälfte und schaue dort nach: Ist mein gesuchter Datensatz größer/kleiner als der in diesem Index gespeicherte Datensatz?
Das mache ich so lange, bis ich habe was ich will oder feststellen muss, dass es nichts wird.
Klar, man kann hier jetzt tricksen, aber das wäre mein grobes vorgehen.

Hätte ich den Index nach der ID sortiert, würde mir das im Bezug auf die Suche letztendlich nichts nützen.

Das Problem, was ich bei meiner Version sehe, ist:
Wenn ich einen Datensatz update oder einen neuen einfüge, müsste ich auch die Index-Datei updaten. Bestenfalls kann ich meinen Index dann an das Ende der Datei einfügen. Schlimmstenfalls an den Anfang.
Da eine Datei nichts weiter als eine Reihe von Bytes ist, würde das bedeuten:
Füge ich in die Mitte der Datei einen neuen Index ein, weil er dort - der Größe nach sortiert - nunmal hingehört, muss ich alle nachstehenden Bytes um die Länge des Index-Eintrages nach hinten schieben. Ich glaube, dass das verdammt viel Aufwand ist.

Der einzige Ansatz, das Performance-Problem dabei zu umgehen, wäre meines Erachtens nach, dass es immer zwei Index-Dateien geben muss. Eine, die geupdatet wird (neu sortiert wird) und eine, in der gesucht wird. Das wäre aber massivst viel Overhead. 

---
Mal angenommen meine Datensätze in der Datendatei haben keine feste Länge (z.B. Wiki-Einträge) und ich mache hin und wieder Indexeinträge ungültig. Der ungültige Indexeintrag zeigt auf einen Datensatz der Länge 1.000. Mein neuer Datensatz ist aber nur 800 ODER aber 1.200 lang.
Dann müsste ich, um die Lücke zu füllen, alle nachfolgenden Datensätze nach hinten schieben, oder nicht? Das dauert doch unglaublich lange? Oder würdest Du dann sagen "Nee, die Kosten dafür sind zu aufwändig. In diese Lücke kommt ein Datensatz, der entweder exakt oder so gut wie passt"?



> Nö... Normalerweise würde man solche Zahlen in einem HashSet (also auch eine Baumstruktur) speichern.


Und auch diese Baumstruktur lässt sich nicht (durchsuchbar) in eine Datei speichern?


----------



## Spacerat (7. Dez 2009)

Ist dir mal aufgefallen, das meine Indexe viel kürzer sind (3 statt 5 Felder)? Möglicherweise liegt hier ein Missverständnis vor. Die Index-ID wie sie bei dir ist, würde bei mir möglicherweise der [c]hashCode()[/c] des Indexes sein und muss deswegen nicht extra definiert werden (wozu sollte man so eine ID auch brauchen?). Ich meine, wenn ich von der Index-ID spreche, das Suchfeld des Datensatzes über welchen dieser Index geht (Wäre in deinem Index Punkt 5). Die Datensatz-ID ist überflüssig, da die Position in der Datei dazu verwendet werden kann (die ist eindeutig genug).





Sekundentakt hat gesagt.:


> Das Problem, was ich bei meiner Version sehe, ist:
> Wenn ich einen Datensatz update oder einen neuen einfüge, müsste ich auch die Index-Datei updaten. Bestenfalls kann ich meinen Index dann an das Ende der Datei einfügen. Schlimmstenfalls an den Anfang.
> Da eine Datei nichts weiter als eine Reihe von Bytes ist, würde das bedeuten:
> Füge ich in die Mitte der Datei einen neuen Index ein, weil er dort - der Größe nach sortiert - nunmal hingehört, muss ich alle nachstehenden Bytes um die Länge des Index-Eintrages nach hinten schieben. Ich glaube, dass das verdammt viel Aufwand ist.
> ...


Eben deswegen eine feste Maximallänge


----------



## Sekundentakt (7. Dez 2009)

> Eben deswegen eine feste Maximallänge


Sorry, mein Beispiel was ich gebracht habe mit dem Wiki-Artikel passte hier gar nicht rein.
Dafür wäre ein Volltext-Index zuständig, der wiederum aus mehreren Teil-Indexen bestehen würde. 
Man könnte dann auch variable Datensatzlängen zulassen, müsste aber beim Einfügen/Löschen damit leben, dass ggf. Null-Bytes zurückbleiben. Die Datenbank muss also in regelmäßigen Abständen optimiert werden. Hierbei könnte ich mir vorstellen, dass ich in einem Stream der Datendatei alle Null-Bytes rausschneide und parallel dazu auch die Indexdatei auf diese weise update. Den Stream speichere ich dann alle X Bytes in eine temporäre Datei, erlöse so meinen Hauptspeicher und tausche dann zum Schluss die alte Index- und Datendatei gegen die Neue aus.
Während dieses Vorganges dürften aber keine Schreiboperationen im Index mehr ausgeführt werden, bzw. es müssten Vorsichtsmaßnahmen getroffen werden.

Jup, das mit dem Hash-Code macht Sinn . 

Trotzdem ist meine Frage immer noch offen geblieben: Wie würdest Du deinen Index performant updaten, wenn die Daten im Index der Größe nach sortiert sind?
Es könnte ja, wie angedeutet, jederzeit passieren, dass sich ein Datensatz ändert und daraufhin der entsprechende Index nach oben- oder unten rutscht.
Bisher kommt mir nur folgender Lösungsansatz in den Sinn:
- berechnen der Zielstelle im Index
- in den Hauptspeicher kopieren aller Bytes zwischen der Zielstelle und der aktuellen Position
- diesen Datenblock im Hauptspeicher sortieren
- den neuen Block mit dem alten Block austauschen

Hast Du da noch andere Erfahrungen?

Sagt Dir BSON etwas? Das ist die binäre Form von JSON (Home - MongoDB - 10gen Confluence).
Hinsichtlich der Schreib- und Suchgeschwindigkeit soll das TOP sein.


----------



## Spacerat (7. Dez 2009)

Hier mal die Implementation einer Indexklasse, wie ich sie mir vorstelle.
	
	
	
	





```
public final class Index<T extends Comparable<T>>
implements Comparable<Index<T>>
{
	private final long position;
	private T field;
	private int length;

	public Index(long position)
	{
		this.position = position;
	}

	@Override
	public int compareTo(Index<T> o)
	{
		if(field == o.field || field != null && field.equals(o.field)) {
			return (position > o.position)? 1 : (position < o.position)? -1 : 0;
		}
		if(o.field != null) {
			return field.compareTo(o.field);
		}
		return (length < o.length)? -1 : (length > o.length)? 1 : 0;
	}

	public boolean isValid()
	{
		return length > 0 && field != null;
	}

	public void invalidate()
	{
		field = null;
		length = 0;
	}

	public T getField()
	{
		return field;
	}

	public int getLength()
	{
		return length;
	}

	public void setField(T field)
	{
		if(field == null) {
			throw new NullPointerException("field may not be null");
		}
		this.field = field;
	}

	public void setLength(int length)
	{
		if(length <= 0) {
			throw new IllegalArgumentException("length has to be larger than 0");
		}
		this.length = length;
	}

	@Override
	public String toString()
	{
		return (field != null)? field.toString() : "invalid";
	}

	@Override
	public boolean equals(Object obj)
	{
		if(this == obj) {
			return true;
		}
		if(obj instanceof Index<?>) {
			Index<?> o = (Index<?>) obj;
			return length == o.length && position == o.position && o.field.equals(field);
		}
		return false;
	}

	@Override
	public int hashCode()
	{
		int hc = (field != null)? field.hashCode() * 31 : 0;
		hc += (int) position;
		hc *= 31;
		hc += length;
		return hc;
	}
}
```
Ein derartiger Index lässt sich ohne weiteres in einem TreeSet sortieren. Ein [c]field[/c] gehört immer fest zu einer [c]position[/c], solange [c]isValid()[/c] *true* ergibt. Ein invalider Index zeigt immer noch auf einen Datensatz welcher allerdings als gelöscht anzusehen ist. Mit ein paar implementierten Feinheiten könnte man diesen auch widerherstellen. Das Sortieren des Indexes heisst nicht, dass ein [c]field[/c] plötzlich eine andere Position in der Daten-Datei bekommt. Ein invalidierter Index muss in jedem Fall aufbewart werden, sonst entsteht in der Daten-Datei ein Leck, welches sich nicht mehr füllen lässt. OK mit einigen implementierten Feinheiten bekommt man auch das wieder hin.
Ich kann mir irgendwie nicht helfen, aber ich glaube ich widerhole mich... Mal eine Frage: Was denkst du passiert in der Daten-Datei, wenn ein Datensatz gelöscht wird? Was bedeutet das Löschen eines Datensatzes für die Folgenden? Sicher kommt die Antwort: Die rücken alle um einen Datensatz nach oben... Diese Antwort wäre Falsch.
Im übrigen: Natürlich können die Datensätze alle verschieden lang sein. Sie dürfen jedoch eine vorher festgelegte Maximallänge nicht überschreiten. Grade fällt mir ein, wo man mehr über dieses Verfahren lesen kann. [c]C64* - Relative Datenspeicherung[/c] (*japp... genau dat olle Ding von Commodore).
@Edit: Eine Kleinigkeit fällt mir noch ein. Und zwar kann man einen Datensatz so löschen, in dem man den Letzten in der Datei an diese Stelle verschiebt. Natürlich muss der Index, welcher auf diesen Datensatz zeigt auch getauscht werden.


----------



## Sekundentakt (7. Dez 2009)

Danke für den beispielhaften Quellcode und Deine Geuld!



> Ein derartiger Index lässt sich ohne weiteres in einem TreeSet sortieren.



Ich hätte vielleicht zu Beginn erwähnen sollen, dass ich Java erst seit kurzem erlerne. Daher die Frage: Wird für ein TreeSet die gesamte Datenmenge in den Hauptspeicher geladen, oder sequenziell hineingeladen und dann wieder in eine Datei geschrieben?

Wir reden immer noch aneinander vorbei . Du sprichst vom Löschen, ich aber vom Updaten und neu einfügen. Wie das Ganze in der Daten-Datei abläuft, das ist mir klar und ich kann deinen Ansätzen folgen. Da kann ich die Datensätze immer stupide hinten dranklatschen oder einen als gelöscht markierten Datensatz überschreiben. Der einzige Nachteil wäre, dass ich jeden Datensatz bis zur Maximallänge mit NULL-Bytes auffüllen müsste, was die Datei leider aufbläht. Aber anders geht’s nunmal nicht.

Mir ging es >>nur<< um die Index Datei. 
Wenn ich einen HashWert zu einem Datensatz als Sortierkriterium in einem Index habe und ich den Datensatz zu diesem Index verändere, dann ändert sich auch automatisch der Hash-Wert.
Wenn der Hash-Wert kleiner/größer wird, muss der Index verschoben werden, damit die Reihenfolge wieder stimmt. 
Das bedeutet dann doch aber, dass der gesamte Index-Block vom Zielort bis zum derzeitigen Standort in der Datei, neu geschrieben werden muss. 

Ein Beispiel: 
Ich nutze eine Hashfunktion, die mir für 10 Datensätze einen Hash mit den Werten von 1-10 wiedergibt. Wird in der praxis nie passieren, ist jetzt aber auch nicht wichtig.
Ich erstelle nun die Indexe und habe die Hashwerte als Sortierkriterium.
Der mit dem Hashwert 1 steht am Anfang der Index-Datei, der mit dem Hashwert 10 am Ende der Index-Datei.
Jetzt wird Datensatz 10 in der Datendatei geupdatet – in der Datendatei bleibt der Datensatz wo er zuvor auch gewesen ist. Der Hashwert ergibt nun 5,5. Das bedeutet, dass der Index mit dem alten Hashwert 10, jetzt zwischen die Indexe mit den Hashwerten 5 und 6 positioniert werden muss. Das bedeutet, dass die Indexe 6-9 um eine volle Indexlänge verschoben werden müssen, damit ich zwischen 5 und 6 die 5,5 einfügen kann. 
In der Praxis kann ich aber – meines Wissens nach – nicht wirklich verschieben. In der Praxis kann ich nur überschreiben. Das heißt: Ich muss den gesamten Indexblock von 6-9 neu erstellen und den alten überschreiben. Ich hoffe man konnte mir jetzt noch folgen.
Das ist mein Gedankengang – liege ich hier falsch?



> @Edit: Eine Kleinigkeit fällt mir noch ein. Und zwar kann man einen Datensatz so löschen, in dem man den Letzten in der Datei an diese Stelle verschiebt. Natürlich muss der Index, welcher auf diesen Datensatz zeigt auch getauscht werden.


Klasse Ansatz. Danke für die Referenz, mal schauen, ob ich Auszüge finde. :rtfm:


----------



## Spacerat (7. Dez 2009)

Die Index-Datei befindet sich normalerweise im Speicher. Genauer gesagt in einer Collection. Es gibt aber auch Ansätze, in denen auch der Index während der Bearbeitung in der Datei verweilt. Dann muss aber auch eine Maximallänge für Indexeinträge vorgegeben werden, weil man benötigt ja einen Anhaltspunkt für die korrekte Positionierung in der Datei.
Der Hashcode ist für das Sortieren des Index nicht notwendig. [c]position[/c] (eindeutig) und [c]länge[/c] (nicht eindeutig) wurden nur in den Vergleichsroutinen [c]compareTo()[/c] und [c]equals()[/c] mit verwendet, um [c]field[/c]s mit gleichem Inhalt zu ermöglichen (Und schon fällt mir auf, das man nach aussen hin noch gar keine Möglichkeit hat ausschliesslich Länge und Feldinhalt zu vergleichen.). Wenn man nämlich versucht, zwei mal den gleichen Inhalt in ein Set zu speichern, erlebt man sein blaues Wunder.
Für Einfügen-Sortieren eignet sich also wg. das TreeSet (Elemente werden sortiert eingefügt). Werden aber [c]field[/c] und / oder [c]length[/c] öfters verändert, empfiehlt sich doch eher eine List oder ein HashSet. Bevor man dann allerdings den Index wieder auf Platte schreibt muss er noch mal sortiert werden. In einem HashSet sucht es sich im übrigen bei kleineren Datenmengen genauso gut wie in einem TreeSet.


----------



## Sekundentakt (7. Dez 2009)

> Es gibt aber auch Ansätze, in denen auch der Index während der Bearbeitung in der Datei verweilt.


Ich schätze meinen im Moment als einen solchen Ansatz ein. 
Die Memory-Mapped-File-Ansätze scheinen dabei ne sehr hohe Performance zu besitzen. Zusammen mit RandoomAccess wäre das wahrscheinlich eine performante Methode Daten zu bearbeiten.

In deiner Klasse arbeitest Du mit nem Maximal-Wert für length, den du über o.length setzt.
Wenn Du deine Index-Datei dann durchsuchst: Sind dann Nullbytes da, um den Rest aufzufüllen, oder wie löst Du das? Dadurch wird ja, wie schon gesagt, die Datei vergrößert, ohne das da tatsächlich Inhalt ist. Oder macht das nicht allzuviel aus? Ich hab' leider auf die Schnelle nicht gefunden, wo ein o.length - Maximalwert deklariert wird.

Falls ein Vergleich von Länge und Position in Zukunft häufiger vorkommt, könntest Du dich ja mit dem Gedanken tragen, das Ganze ebenfalls zu hashen und direkt abzuspeichern.


----------



## Spacerat (8. Dez 2009)

Sekundentakt hat gesagt.:


> In deiner Klasse arbeitest Du mit nem Maximal-Wert für length, den du über o.length setzt.
> Wenn Du deine Index-Datei dann durchsuchst: Sind dann Nullbytes da, um den Rest aufzufüllen, oder wie löst Du das? Dadurch wird ja, wie schon gesagt, die Datei vergrößert, ohne das da tatsächlich Inhalt ist. Oder macht das nicht allzuviel aus? Ich hab' leider auf die Schnelle nicht gefunden, wo ein o.length - Maximalwert deklariert wird.


[c]o.length[/c] wird nur in den Vergleichsmethoden [c]equals()[/c] und [c]compareTo()[/c] verwendet. Mit der Maximallänge hat das nichts zu tun, diese Abfrage gehört normalerweise auch nicht in die Indexklasse. Im übrigen, ist [c]length[/c] nicht die Länge des Indexfeldes [c]field[/c] sondern die Länge des gesamten Datensatzes in der Daten-Datei. Gehashed wird auch schon beides. Das einzig unveränderliche an der Indexklasse ist die Position des Datensatzes (gültig oder nicht) in der Daten-Datei. Damit wäre das einzige was dieser Klasse noch fehlt, eine Methode zum Vergleichen von Inhalten unabhängig von der Position:[JAVA=90]
	public boolean matches(Index<T> other)
	{
		boolean rc = other.length == length;
		rc &= field == other.field || field != null && field.equals(other.field);
		return rc;
	}[/code]Zu den Null-Bytes: Ich würde diese Bytes nicht unbedingt als Null-Bytes, sondern eher als Füll-Bytes bezeichnen, da es völlig wurst ist, welchen Wert die haben. Die können nämlich auch noch Daten von vorherigen Datensätzen die länger waren enthalten. Um die muss sich niemand mehr kümmern.


----------



## Sekundentakt (8. Dez 2009)

Füllbyte klingt in diesem Sinne wirklich besser.



> Um die muss sich niemand mehr kümmern.


Wie grausig muss es sein, wenn man (bei MySQL) als Datentyp VarChar mit 255 Chars angibt, und der längste Wert nie größer als 20 ist.
Okay, die Deklaration wäre Humbuck gewesen,aber wenn man sich mal vor Augen führt, dass die restlichen 235 Zeichen TROTZDEM geschrieben werden und Platz verbrauchen :shock:.

Btw. ein Konzept zum Speichersparen wäre doch mal interessant, bei dem ein Datensatz bei einer Überschreitung des Maximalwertes einfach in zwei Hälften zerteilt wird. Ich denke, dass das Speicher unter bestimmten Bedingungen sparen könnte.
Man müsste im Index lediglich auf diesen Umstand verweisen, z.B. in dem man die Datensatzlänge verdoppelt. So kannst Du nämlich den Maximalwert relativ niedrig ansetzen und komprimierst dadurch deine Datendatei etwas. 

Für was für Größenordnungen verwendest Du denn deine Index-Klasse bisher?


----------



## Spacerat (8. Dez 2009)

Sekundentakt hat gesagt.:


> Füllbyte klingt in diesem Sinne wirklich besser.
> 
> Wie grausig muss es sein, wenn man (bei MySQL) als Datentyp VarChar mit 255 Chars angibt, und der längste Wert nie größer als 20 ist.
> Okay, die Deklaration wäre Humbuck gewesen,aber wenn man sich mal vor Augen führt, dass die restlichen 235 Zeichen TROTZDEM geschrieben werden und Platz verbrauchen :shock:.


Ja neee... Nix Shock ... Sorgfalt beim Anlegen von MySQL-Datenbanken...





Sekundentakt hat gesagt.:


> Btw. ein Konzept zum Speichersparen wäre doch mal interessant, bei dem ein Datensatz bei einer Überschreitung des Maximalwertes einfach in zwei Hälften zerteilt wird. Ich denke, dass das Speicher unter bestimmten Bedingungen sparen könnte.
> Man müsste im Index lediglich auf diesen Umstand verweisen, z.B. in dem man die Datensatzlänge verdoppelt. So kannst Du nämlich den Maximalwert relativ niedrig ansetzen und komprimierst dadurch deine Datendatei etwas.


Wie war das Oben? MemoryMappedFile? In diesem legt man z.B. "Kacheln" in der Grösse von 32 Byte an und nummeriert diese durch (VirtualMemory arbeitet so, wenn auch in anderen Grössenordnungen). Im Index speichert man nun keine Längen mehr, sondern die Nummern der "Kacheln" die von diesem Datensatz belegt werden. Diese Implementation ist aber weitaus aufwendiger.





Sekundentakt hat gesagt.:


> Für was für Größenordnungen verwendest Du denn deine Index-Klasse bisher?


Grössen von sagen wir ungefähr 0 . Die Klasse diente hier nur als Beispiel. Vllt. kommen wir ja noch dazu den Rest dazu zu proggen.


----------



## Sekundentakt (8. Dez 2009)

> Wie war das Oben? MemoryMappedFile? In diesem legt man z.B. "Kacheln" in der Grösse von 32 Byte an und nummeriert diese durch (VirtualMemory arbeitet so, wenn auch in anderen Grössenordnungen). Im Index speichert man nun keine Längen mehr, sondern die Nummern der "Kacheln" die von diesem Datensatz belegt werden. Diese Implementation ist aber weitaus aufwendiger.


Können diese Kacheln (ich würde Felder sagen) auch größer/kleiner als 32 Bytes sein? Kann ich das auch irgendwie plattenorientiert machen?



> Grössen von sagen wir ungefähr 0 . Die Klasse diente hier nur als Beispiel. Vllt. kommen wir ja noch dazu den Rest dazu zu proggen.


Klar, let's start to create a new open source database management system 

Hast Du deinen Quellcode von der plattenorientierten B-Baum-Implementierung noch irgendwo zu liegen?


----------



## Spacerat (8. Dez 2009)

Sekundentakt hat gesagt.:


> Können diese Kacheln (ich würde Felder sagen) auch größer/kleiner als 32 Bytes sein? Kann ich das auch irgendwie plattenorientiert machen?


...Sogar noch viel grösser. Aber wir sind uns hoffentlich einig darüber, dass es Feldgrössen kleiner eines Zeigers in Bytes auf eines dieser Felder nicht bringen. WG., Virtueller Speicher arbeitet mit diesem Verfahren. Ich hab' mir das (schon länger her) mal bei der VMM-Software vom Amiga angesehen. Und ja, es geht auch plattenorientiert. Z.B. SWAP-Partition bei Linux.





Sekundentakt hat gesagt.:


> Hast Du deinen Quellcode von der plattenorientierten B-Baum-Implementierung noch irgendwo zu liegen?


Nee, leider nicht. Der fiel der Frustration des Misserfolgs zum Opfer. Aber iwie bereue ich diese Komplettlöschung gerade. Man hat, ausser Theorien, gar nichts mehr auf was man aufbauen könnte.


----------



## Sekundentakt (8. Dez 2009)

> Nee, leider nicht. Der fiel der Frustration des Misserfolgs zum Opfer. Aber iwie bereue ich diese Komplettlöschung gerade. Man hat, ausser Theorien, gar nichts mehr auf was man aufbauen könnte.


Ich würde Quellcode niemals wegschmeißen, es sei denn er ist tatsächlich absoluter Bullshit, was hier ja nicht zutrifft .

Ich bin sowieso skeptisch, ob Bäume tatsächlich die performanteste Lösung für Suche sein müssen - schließlich muss es auch anders gehen - auch performant. Wenn ich eine neue Indexzeile in die Indexdatei einfüge, muss die gesamte Datei - meines Wissensstandes nach - ab der Einfügeposition neu geschrieben werden. Das skaliert aber mit zunehmender Größe immer schlechter und letzten Endes kann ein Baum diesem Problem auch nicht ausweichen. 
Es sei denn ich speicher im Index einen Index.

Also einmal:
- Index für den Datensatz (Hashcode)
- Position des Datensatzes in Datendatei in Bytes
- Länge des Datensatzes in Bytes
- Position des nächstgrößeren Indexes in der Index-Datei in Bytes
- Position des nächstkleineren Index in der Datei in Bytes

Das wäre ein Linked-List-Ansatz (glaube ich).
Dann bräuchte ich bei einem Datensatz-Update nur die Position des nächstgrößeren/-kleineren Indexes updaten bzw. könnte einen neuen Index einfach an das Ende der Index-Datei einfügen.
Nachteil wäre allerdings, dass dieser Index m.E. so wie ich ihn gerade definiere, nur sequenziell durchsucht werden kann.



> Aber wir sind uns hoffentlich einig darüber, dass es Feldgrössen kleiner eines Zeigers in Bytes auf eines dieser Felder nicht bringen


Die Feldgröße muss schon so gestaltet sein, dass ich in die Kachel/das Feld einen normalgroßen Datensatz einfügen kann und die Kachel größer ist, als der Zeiger im eigentlichen Index - ansonsten habe ich damit nichts gewonnen. :bae:



> Und ja, es geht auch plattenorientiert. Z.B. SWAP-Partition bei Linux.


Linux habe ich - bisher - noch nicht verwendet. Dementsprechend habe ich von solchen Partitionen noch nichts gehört. Für mich würde sich hier ne Liste von Anfängerfragen auftun: Erledigt Linux die Platten-Speicher-Arbeit für mich, oder muss das mein Programm. Und wenn es mein Programm nicht muss, welche Auswirkung hat welche Partitionierung auf ein Durchsuchen der Datei mit meinem Programm. Aber das ist - glaube ich - ein anderes Thema, oder was meinst Du?


----------



## Spacerat (8. Dez 2009)

Sekundentakt hat gesagt.:


> Das wäre ein Linked-List-Ansatz (glaube ich).
> Dann bräuchte ich bei einem Datensatz-Update nur die Position des nächstgrößeren/-kleineren Indexes updaten bzw. könnte einen neuen Index einfach an das Ende der Index-Datei einfügen.
> Nachteil wäre allerdings, dass dieser Index m.E. so wie ich ihn gerade definiere, nur sequenziell durchsucht werden kann.


Dem stimme ich zu... genauer gesagt eine doppelt verkettete Liste. Und ja, das geht nur sequentiell. Aber man kann dem jeweils letztem Element einen Link auf das erste geben. Man muss dann nicht immer von Anfang an die Liste durchsuchen, um meinetwegen an das 3.-letzte Element zu kommen. Man muss sich nur das zuletzt gewählte Element merken und kann von dort aus die Suche fortsetzen. Da diese Suche nun zirkulierend abläuft, muss dass aktuelle Element solange behalten werden (Startelement), bis das gesuchte Element gefunden wird oder [c]Startelement == gerade durchuchtes Element[/c] ergibt.





Sekundentakt hat gesagt.:


> ... Aber das ist - glaube ich - ein anderes Thema, oder was meinst Du?


Äh, ja. Aber apropos anderes Thema: Ich hab' mir gerade überlegt, was wohl so ein Dateisystem (FAT32, NTFS, Ext2 usw.) im grossen und ganzen ist. Eine Datenbank, basierend auf MemoryMappedFiles? Die Verzeichnisse sind die Indices und da hätten wir dann auch 'ne Baumstruktur. Hmmm. Vllt. doch mal das alte 1541-Kernel rauskramen und versuchen nach Java zu portieren? Schade hab' grad' was zu tun...


----------



## Sekundentakt (8. Dez 2009)

> Äh, ja. Aber apropos anderes Thema: Ich hab' mir gerade überlegt, was wohl so ein Dateisystem (FAT32, NTFS, Ext2 usw.) im grossen und ganzen ist. Eine Datenbank, basierend auf MemoryMappedFiles? Die Verzeichnisse sind die Indices und da hätten wir dann auch 'ne Baumstruktur. Hmmm. Vllt. doch mal das alte 1541-Kernel rauskramen und versuchen nach Java zu portieren? Schade hab' grad' was zu tun...


Der Bahnhof ist gerade auf Gleis 3 abgefahren und hat fünf Gäste Verspätung. :autsch:

Was ist 1541-Kernel? 
Ich denke ein Dateisystem kann kein Datenbanksystem im klassischen Sinne sein. Ein Dateisystem ist einfach eine sehr platten-hardware orientierte Datenorganisation. Mehr aber nicht. 
Ein Dateisystem ist dafür verantwortlich, dir zu sagen, wo Du diesen oder jenen Schnipsel der Datei (des Dokumentes) findest, nicht aber dafür verantwortlich, zu wissen, was darin steht.
Ein Datenbanksystem verwaltet dagegen auch den Inhalt.
Es gibt hier Überschneidungen. Vielleicht kann man sich darauf einigen zu sagen, dass ein Dateisystem eine Art Dokumenten-orientierte-Datenbank ist, aber nicht jede Datenbank ein Dateisystem.
Man könnte auch spezialisieren: Eine Datenbank, die ein Dateisystem zu Grunde liegen hat (siehe Google),  ist effektiver, als eine Datenbank, die auf ein Dateisystem für universellere Zwecke aufsetzt.


----------



## Spacerat (8. Dez 2009)

Sekundentakt hat gesagt.:


> Der Bahnhof ist gerade auf Gleis 3 abgefahren und hat fünf Gäste Verspätung. :autsch:


Der war gut...:lol:





Sekundentakt hat gesagt.:


> Was ist 1541-Kernel?


1541: Ein Uralt-Diskettenlaufwerk für den C64. Wurde als intelligentes Laufwerk bezeichnet, da es das Controlling selbst übernahm. Dazu benötige es natürlich ein 'Betriebssystem' genannt Kernel.





Sekundentakt hat gesagt.:


> Ich denke ein Dateisystem kann kein Datenbanksystem im klassischen Sinne sein. Ein Dateisystem ist einfach eine sehr platten-hardware orientierte Datenorganisation. Mehr aber nicht.
> Ein Dateisystem ist dafür verantwortlich, dir zu sagen, wo Du diesen oder jenen Schnipsel der Datei (des Dokumentes) findest, nicht aber dafür verantwortlich, zu wissen, was darin steht.
> Ein Datenbanksystem verwaltet dagegen auch den Inhalt.
> Es gibt hier Überschneidungen. Vielleicht kann man sich darauf einigen zu sagen, dass ein Dateisystem eine Art Dokumenten-orientierte-Datenbank ist, aber nicht jede Datenbank ein Dateisystem.
> Man könnte auch spezialisieren: Eine Datenbank, die ein Dateisystem zu Grunde liegen hat (siehe Google),  ist effektiver, als eine Datenbank, die auf ein Dateisystem für universellere Zwecke aufsetzt.


Das sehe ich inzwischen ganz anders. Eine Datenbank kennt den Inhalt der darin befindlichen Felder genauso wenig wie ein Dateisystem, bis man bestimmte Inhalte sucht. Und das funzt auch bei beiden. Man denke im übrigen nur mal an CD-Rom-Emulatoren. So ein ISO-Image ist doch nichts anderes als eine Datenbank. Es geht bei beiden doch schlicht um die Organisation der Daten.


----------



## Sekundentakt (9. Dez 2009)

> Das sehe ich inzwischen ganz anders. Eine Datenbank kennt den Inhalt der darin befindlichen Felder genauso wenig wie ein Dateisystem, bis man bestimmte Inhalte sucht. Und das funzt auch bei beiden. Man denke im übrigen nur mal an CD-Rom-Emulatoren. So ein ISO-Image ist doch nichts anderes als eine Datenbank. Es geht bei beiden doch schlicht um die Organisation der Daten.


All diese Dinge haben aber etwas mit der Dateiorganisation bzw. Datenablage auf Hardware zutun. Ich denke, ein Filesystem sagt dem Plattenleser, wo er wann weiterlesen muss und entscheidet, wie die Daten auf Platte/CD-ROM angeordnet werden, wobei es bestimmten Standards folgt.

Ich schau mir das heute Nachmittag noch mal genauer an .


----------

