B-Baum Indexstruktur erstellen

[MrTiger]

Hi

Ich habe eine kleine Frage. Und zwar möchte ich in C# eine B-Baum Indexstruktur auf Files erstellen (also z.B. eine Liste von Filenamen). Diese Indexstruktur soll dann z.B. zum effizienten Suchen von Filenamen verwendet werden.

Wie würde man so etwas in C# realisieren? Habe da leider gerade gar keine Idee. Habe nämlich noch fast keine Erfahrung in C#. Ich habe daran gedacht, die Indexstruktur in ein separates .db files zu speichern, aber wen man das so machen würde, wie würde man dises File kreeiren, verwalten etc.?

Wie B-Bäume funktioneiren weiss ich, allerdings nur in der Theorie.

[HJST1979]

Hallo

um dir hier einen Tipp zu geben wäre es auch sinnvoll zu wissen ob du WPF nutzen willst oder winform.

Gruß Hans-Jörg

[lbm1305]

Hallo

um dir hier einen Tipp zu geben wäre es auch sinnvoll zu wissen ob du WPF nutzen willst oder winform.

Gruß Hans-Jörg

Warum sollte das von Belangen sein?

[Klotzkopp]

Wie würde man so etwas in C# realisieren?

Man würde eine Klasse für einen einzelnen Knoten modellieren, sowie die Operationen, die auf diesen Knoten arbeiten (Einfügen, Balancieren usw.)

Ich habe daran gedacht, die Indexstruktur in ein separates .db files zu speichern, aber wen man das so machen würde, wie würde man dises File kreeiren, verwalten etc.?

Die Serialisierung und Deserialisierung der Datenstruktur ist ein weiterer Schritt. Mach das nacheinander, nicht gleichzeitig.

[MrTiger]

Ich danke euch vielmals.

Ich muss das jetzt vielleicht etwas spezifizieren. Es geht um ein virtual file system und ich möchte dazu eine Indexstruktur erstellen. D.h. die Dateien im file system sollen indiziert werden.

Ich sehe da jetzt zwei Möglichkeiten:

1. Einen B-Baum verwenden. Da ist dann halt das Problem, dass ich solche B-Bäume eben nur auf dem Papier kenne und nur auf dem Papier mit ihnen gearbeitet habe. Implementiert habe ich noch nie einen, daher bin ich mir über die Klassenstruktur und die Implementationsdetails unsicher.

Gibt es für B-Bäume keine library? Oder gibt es vielleicht einen example code in C# welches einen B-Baum zeigt? V.a. das einfügen eines neuen Elementes in einen B-Baum stelle ich mir noch schwer zu implementieren vor wegen rebalancing etc.

Was würden die inneren Knoten und die Blätter des B-Baums genau speichern? Also würden dann die inneren Knoten einfach die directory Namen speichern und diese auf den entsprechenden Ort mappen und die Blätter würden die Filenamen halten?

2. Eine SortedList oder einen Dictionary verwenden. Das wäre ja dann einfach und das einfügen, suchen etc. bereits vorhanden. Funktioniert das aber für einen Index auf einem file system? Es ist ja möglich, dass zwei Files mit dem gleichen Namen aber in unterschiedlichen directories existieren und das könnte man ja dann nicht in einer SortedList oder Dictionary speichern, da ja da keys nur einmal vorkommen dürfen. Oder würde man einfach als Indexelement direkt den ganzen Pfad speichern? Dann wüde man aber die Hierarchie verlieren.

3. Der Index soll noch persistent gemacht werden, d.h. wenn das Programm beendet wird soll der Index weiterbestehen, d.h. muss in eine Datei geschrieben werden. Wie macht man das? Könnte man z.B. das Objekt einfach serialisieren und in eine Datei schreiben und bei Gebrauch des Indexes einfach wieder deserialisieren?

um dir hier einen Tipp zu geben wäre es auch sinnvoll zu wissen ob du WPF nutzen willst oder winform.

WPF.

Man würde eine Klasse für einen einzelnen Knoten modellieren, sowie die Operationen, die auf diesen Knoten arbeiten (Einfügen, Balancieren usw.)

D.h. eine Klasse node welches ein Array von nodes hält, welches die Kindknoten repräsentiert. Dann vielleicht eine Klasse Indexer, welches das root objekt hält und zudem die Operationen. Ist das so richtig?

[Klotzkopp]

Was würden die inneren Knoten und die Blätter des B-Baums genau speichern? Also würden dann die inneren Knoten einfach die directory Namen speichern und diese auf den entsprechenden Ort mappen und die Blätter würden die Filenamen halten?

Die Knoten speichern deine Datenelemente. Wenn das Verzeichnisse und Dateien sind, dann Verzeichnisse und Dateien. Dabei kann jeder Knoten, egal ob innerer oder Blatt, mehrere Datenelemente speichern. Was wo zu liegen kommt, hängt von den Schlüsseln ab. Das solltest du aber wissen, wenn du B-Bäume kennst.

Ich glaube, du solltest mal 2 bis 3 Schritte zurück machen und genau festhalten, was du eigentlich willst. Die Beschreibung "Dateisystem indizieren" ist viel zu ungenau. Was genau willst du erreichen? Was sind deine Suchkriterien, was deine Suchergebnisse?

[MrTiger]

Es geht um ein virtual file system (ein rudimentäres) wobei eine virtual disk einem .zip file entspricht. D.h. in dem .zip file sind dann die ganzen Verzeichniss und Ordner hierarchisch gespeichert. Für jede virtual disk möchte ich nun einen Index erstellen. Es sollen damit dann Verzeichniss und Files gesucht werden und wenn man natürlich ein neues File vom host file system in die virtual disk importiert muss der Index aktualisiert werden. Ebenso beim löschen eines Files oder Verzeichnisses aus der virtual disk.

Wenn ich nun in den Knoten die Verzeichnisse und Files speichern würde, wäre das ja redundant zum .zip file, d.h. ich brauche doch in den Knoten zwar die Namen der Verzeichnisse und Files, aber dann auch irgendeinen Link in das .zip File. Oder sehe ich das falsch?

[flashpixx]

Es geht um ein virtual file system (ein rudimentäres) wobei eine virtual disk einem .zip file entspricht.

Magst Du vielleicht das Problem mal im Detail schildern, denn vielleicht kann man da bei etwas mehr Kenntnisse sich besser zu äußern. Wenn es speziell um Datenstrukturen geht, dann lege ich Algorithmen (Pearson Studium - IT): Amazon.de: Robert Sedgewick: Bücher ans Herz.

Wenn Du eh schon ein Zip hast, dann kannst Du eigentlich direkt die Daten des Zips entpacken, d.h. Du kannst Dich frei in dem Zip bewegen, in meinen Augen brauchst Du da keinen B-Baum um die Daten zu speichern, denn die Daten des Zips sind ja schon entsprechend angelegt. Du musst dann lediglich immer das aktuelle Directory lesen und darstellen. Was mich interessieren würde wäre, wofür soll das ganze sein, mit welchen Datenmengen ist so im Mittel zu rechnen, warum nimmst Du ein Zip und nicht direkt ein Verzeichnis, etc.

[lbm1305]

Gibt es für B-Bäume keine library? Oder gibt es vielleicht einen example code in C# welches einen B-Baum zeigt? V.a. das einfügen eines neuen Elementes in einen B-Baum stelle ich mir noch schwer zu implementieren vor wegen rebalancing etc.

C# test.net » BPlusTree

[MrTiger]

Magst Du vielleicht das Problem mal im Detail schildern, denn vielleicht kann man da bei etwas mehr Kenntnisse sich besser zu äußern.

Es geht um ein virtual file system, wobei eine virtual disk ein .zip file umfasst. In einer virtual disk, d.h. in dem .zip file, können dann vom Host Dateien importiert werden oder auch neue Dateien erzeugt werden etc. Das .zip File ist in sich hierarchisch organisiert, mit Verzeichnissen, Unterverzeichnissen, Dateien etc., so wie das host file system.

Nun möchte ich für jede virtaul disk, d.h. für jedes .zip file einen Index erstellen. Da kommen entweder ein B-Baum oder eine sortedList oder Dictionary in Frage.

Bei einem B-Baum würde ich den Index wie folgt sehen. Die inneren Knoten speichern Verzeichnissnamen bzw. Links zu Verzeichnissen und die Blätter Filenamen bzw. Links zu Files. Ich stelle mir das so vor: Wenn man eine Datei mit folgendem Pfad im .zip file hat C:\folder1\file1 dann hat man einen root Knoten mit label "C", der auf das C Verzeichnis zeigt, dann hat man einen Kindknoten mit Label "folder1" und dieser hat einen Kindknoten mit Label "file1".

Oder sehe ich das falsch? Eine SortedList bzw. Dictionary ist ja nicht hierarschisch und dann würde das obige Verfahren nicht gehen. Richtig?

Weiterhin brauche ich von den Indexes ja irgendeinen Link in das .zip File, d.h. in die virtual Disk. D.h. das obige Beispiel C:\folder1\file1 ist ja im .zip file hierarchisch vorhanden. Die Indexeintrage "C", "folger1" und "file1" sollten ja dann an die entsprechenden Stellen im .zip file zeigen.

Wie kann ich das realisieren?

Wenn Du eh schon ein Zip hast, dann kannst Du eigentlich direkt die Daten des Zips entpacken, d.h. Du kannst Dich frei in dem Zip bewegen, in meinen Augen brauchst Du da keinen B-Baum um die Daten zu speichern, denn die Daten des Zips sind ja schon entsprechend angelegt. Du musst dann lediglich immer das aktuelle Directory lesen und darstellen. Was mich interessieren würde wäre, wofür soll das ganze sein, mit welchen Datenmengen ist so im Mittel zu rechnen, warum nimmst Du ein Zip und nicht direkt ein Verzeichnis, etc.

der B-Baum soll nicht dazu da sein um die Daten zu speichern, sondern als Verweis auf die Daten, also für effizientes Suchen z.B.

Die Datenmengen sind nicht so gross, d.h. die einzelnen virtual disks werden nicht allzu gross. Das ganze soll einfach als programming experience sein. Klar könnte man auch ein Verzeichnis nehmen, allerdings ist ja ein Zip z.B. schon kompromiert, d.h. man spart Speicherplatz.

Bearbeitet 22. März 2013 von MrTiger

[flashpixx]

Ich sehe da nicht die Notwendigkeit eines B-Baums, denn die meisten Zip-File Komponenten, haben entsprechenden Iteratoren um über die Daten zu laufen.

Bei einem entsprechenden Baum würde ich da viel zu viel Verwaltungsaufwand sehen.

[Klotzkopp]

Bei einem B-Baum würde ich den Index wie folgt sehen. Die inneren Knoten speichern Verzeichnissnamen bzw. Links zu Verzeichnissen und die Blätter Filenamen bzw. Links zu Files.

Das ist Unsinn.

Ich stelle mir das so vor: Wenn man eine Datei mit folgendem Pfad im .zip file hat C:\folder1\file1 dann hat man einen root Knoten mit label "C", der auf das C Verzeichnis zeigt, dann hat man einen Kindknoten mit Label "folder1" und dieser hat einen Kindknoten mit Label "file1".

Was du da beschreibst, ist ein Baum, aber sicher kein B-Baum. Bei einem B-Baum liegen alle Blätter in derselben Tiefe. Liegen alle deine Dateien gleich tief in der Verzeichnishierarchie? Vermutlich nicht.

Bist du sicher, dass du weißt, wie ein B-Baum funktioniert?

der B-Baum soll nicht dazu da sein um die Daten zu speichern, sondern als Verweis auf die Daten, also für effizientes Suchen z.B.

An dieser Stelle zum wiederholten Mal die Frage: Wonach willst du suchen? Du kannst nicht "nach Dateien suchen". Du kannst nach bestimmten Eigenschaften von Dateien suchen. Was sind deine Suchkriterien? Name? Größe? Erstelldatum? Der Wert des Suchkritieriums bestimmt die Position im Baum. Für jedes Suchkriterium brauchst du einen eigenen Baum.

Beschreib doch mal eine typische Suchanfrage, vielleicht kommt man dann der eigentlichen Problemstellung näher.

Die Indexeintrage "C", "folger1" und "file1" sollten ja dann an die entsprechenden Stellen im .zip file zeigen.

Hast du denn ein Zip-API, das mit einer Position in der Zip-Datei etwas anfangen kann?

[MrTiger]

Was du da beschreibst, ist ein Baum, aber sicher kein B-Baum. Bei einem B-Baum liegen alle Blätter in derselben Tiefe. Liegen alle deine Dateien gleich tief in der Verzeichnishierarchie? Vermutlich nicht.

Bist du sicher, dass du weißt, wie ein B-Baum funktioniert?

Du hast natürlich recht, da habe ich wohl etwas durcheinander gebracht.

Könntest du vielleicht ein kleines Beispiel machen für einen B-Baum Index auf files? Ich habe gerade keine Ahnung wie ich das machen soll bzw. was die Knoten für Werte halten sollen.

An dieser Stelle zum wiederholten Mal die Frage: Wonach willst du suchen? Du kannst nicht "nach Dateien suchen". Du kannst nach bestimmten Eigenschaften von Dateien suchen. Was sind deine Suchkriterien? Name? Größe? Erstelldatum? Der Wert des Suchkritieriums bestimmt die Position im Baum. Für jedes Suchkriterium brauchst du einen eigenen Baum.

Beschreib doch mal eine typische Suchanfrage, vielleicht kommt man dann der eigentlichen Problemstellung näher.

Es soll nur nach den Namen von Dateien gesucht werden, also z.B. "foo.txt" oder eventuell auch partielle Namen also nur "fo" oder "foo".

Eventuell soll auch noch nach Verzeichnisnamen gesucht werden. Ist sowas auch im gleichen Baum möglich oder bräuchte ich da einen separaten Baum für die Verzeichnisnamen?

Hast du denn ein Zip-API, das mit einer Position in der Zip-Datei etwas anfangen kann?

Ja, sowas in der Art ist in Form eines streams vorhanden.

[flashpixx]

Es soll nur nach den Namen von Dateien gesucht werden, also z.B. "foo.txt" oder eventuell auch partielle Namen also nur "fo" oder "foo".

Ich müsste mich schwer täuschen, aber die meisten APIs bieten das Suchen in einem Zip an. Weiterhin warum willst Du einen eigenen Suchalgorithmus mit Datenstruktur implementieren !? Falls die API das Suchen nicht anbietet, dann kannst Du einmal die Verzeichnis- & Dateiliste lesen in einen Container packen und dann darin suchen, ich nehme mal an .NET bietet entsprechende Container mit entsprechenden Sortier- & Suchfunktionen.

In C++ würde man z.B. einen std::vector, std::map o.ä. nehmen und dann kann ich direkt darin suchen und falls ich eine Teilstringsuche brauche, dann überlade ich das Compare meiner Itemklasse.

Wenn's dann bitte komplex sein soll, dann nimm einen Listencontainer und matche die Suche via regulärem Ausdruck, das ist lineare Laufzeit, denn ich muss jede Datei / Verzeichnis nur einmal anschauen und den Match des Ausdrucks prüfen.

Warum muss es so kompliziert sein !?

[MrTiger]

So ich habe mich jetzt entschieden einen B-Baum zu implementieren.

Ich habe nun Code gesucht, welcher einen B-Baum oder B+-Baum implementiert. Am besten in C# aber auch Java ist ok. Ich habe bei Google einige Implementationen gefunden, z.B.

http://wwwiti.cs.uni-magdeburg.de/iti_db/algoj/code/algoj/kap14/BTree.java

BTree.java - my-alogorithm-implementation - my-algorithm-implementation - Google Project Hosting

BTree.java

Sowas stelle ich mir etwa vor, also keine ganze extrem umfangreiche library, sondern einfach ein kurzes Stück Code, welches einen B-tree repräsentiert, also die Nodes, Operationen wie Einfügen, Löschen, Rebalancieren, Suchen etc. Bei den obigen code snippets fehlt eine delete Methode, das wäre noch wichtig.

Kann mir da vielleicht jemand weiterhelfen bzw. kennt so ein code snippet? Ich würde so ein code snippet gerne als Vorlage bzw. Anregung benutzen.

[Klotzkopp]

Es soll nur nach den Namen von Dateien gesucht werden, also z.B. "foo.txt" oder eventuell auch partielle Namen also nur "fo" oder "foo".

Solange der partielle Name immer noch den Anfang enthält, geht das so. Sobald du allgemein mit Platzhaltern suchen willst, wird das komplizierter. Stichwort Permuterm Index.

Da deine Dateinamen vermutlich nicht über die gesamte Verzeichnisstruktur eindeutig sind, sind deine Daten auch keine Dateien bzw. Verweise darauf, sondern Listen von Dateien.

Eventuell soll auch noch nach Verzeichnisnamen gesucht werden. Ist sowas auch im gleichen Baum möglich oder bräuchte ich da einen separaten Baum für die Verzeichnisnamen?

Du kannst das im selben Baum machen. Dann trägt eben jeder Eintrag zusätzlich die Information, ob es eine Datei oder ein Verzeichnis ist, und du musst ggf. die Suchergebnisse filtern.

Von wievielen Suchanfragen pro Sekunde auf wievielen Dateien reden wir denn hier so in etwa?

[MrTiger]

Ich brauche v.a. Code oder Pesudocode für die delete methode inklusive Rotatonen etc. des B-Baums. Den Rest sollte ich hinbekommen.

[MrTiger]

So ich konnte den B-Baum jetzt implementieren, sogar auch die Delete Methode.

Nun bin ich mir aber unschlüssig welche Ordnung ich für den Baum wählen soll. Die Ordnung gibt ja die minimale Anzahl keys in einem Knoten an.

Was für eine Ordnung würdet ihr da wählen wenn der B-Baum als Index für ein virtual file system gebraucht wird? Vielleicht 2 oder 3 oder doch höher?

[MrTiger]

Also wenn ich ja eine höhere Order für den B-Tree wähle, z.B. 100, dann reduziert sich ja die Tiefe und jeder Knoten hält eine grössere Anzahl keys.

Trifft es zu, dass bei vielen files im virtual file system die order eher höher gewählt werden sollte und bei wenigen files eher eine kleinere order? Es wird jeder filename indexiert.

Und was ist genau eine höhere order? Z.B. 100?

By the way, die order eines B-Baums beschreibt die minimale Anzahl keys in einem Knoten.