C# B-Baum Indexstruktur erstellen

[The Gunner]

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.

 

[Holt]

Dann nimm lieber mal das Dictionary (System.Collections.Generic), das ist fertig vorhanden und auch sehr schnell wenn es um Suchen geht.

Wenn Du trotzdem einen B-Baum willst, dann lies mal hier.

 

[The Gunner]

Ich danke dir.

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 gebrauchen. 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 Dictionary verwenden wie du es vorgeschlagen hast oder eine SortedList. 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?

 

[Holt]

Auch in einem B-Baum kannst Du nur ein Object für jeden Schlüssel ablegen, genau wie im Dictionary oder in einem echte Directory. Da kannst Du ja auch nicht zweimal Texta.txt rein kopieren, ohne das beim zweiten Kopieren das erst File überschrieben (ergo gelöscht) wird. Dafür gibt es aber Unterverzeichnisse und da kann man dann noch mal eine Datei mit dem gleichen Namen anlegen. Du solltest also ggf. sowas machen:
Dictionary <string, object> MyFiles;

Dann musst Du eben schauen, ob das Object nun vom Typ für ein File oder wieder vom gleichen Typ wie oben ist und ggf. dort weitersuchen. Wenn Du eine flache Strukutr willst, dann hängst Du den Pfad an den Dateinamen im Schlüssel. Du kannst aber auch sowas machen:
Dictionary <string, List<string>> MyFiles;
Dann nimmst Du als Schlüssel den Filenamen und speicherst darunter in einer Liste die Directories wo sich eine Datei mit dem Namen befindet. Das wäre eine guten Datenstruktur wenn man danach sucht, wo überall Kopieren der Dateien rumliegen.

Für das Schreiben würde ich eine eigenen Routine schreiben die nur die Daten schreibt statt alles zu serialisieren, denn sonst wird die Daten sehr viel größer als nötig und wenn Du genau weißt, was Du schreibt bist Du dann auch flexibler und kannst Du die unterliegende Datenstruktur leichter ändern um sie den Bedürfnissen anzupassen, denn die Datenstruktur muss immer zur Anwendung passen.

 

[The Gunner]

Ein B-Baum ist ja hierarchisch. Ich würde mir das wie folgt vorstellen. Also die inneren Knoten speichern ja 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 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.

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. Der Die Indexeintrage "C", "folger1" und "file1" sollten ja dann an die entsprechenden Stellen im .zip file zeigen.

Wie kann ich das realisieren?

Du solltest also ggf. sowas machen:
Dictionary <string, object> MyFiles;

Dann musst Du eben schauen, ob das Object nun vom Typ für ein File oder wieder vom gleichen Typ wie oben ist und ggf. dort weitersuchen.

Ich verstehe nicht ganz was du da meinst.

Für das Schreiben würde ich eine eigenen Routine schreiben die nur die Daten schreibt statt alles zu serialisieren, denn sonst wird die Daten sehr viel größer als nötig und wenn Du genau weißt, was Du schreibt bist Du dann auch flexibler und kannst Du die unterliegende Datenstruktur leichter ändern um sie den Bedürfnissen anzupassen, denn die Datenstruktur muss immer zur Anwendung passen.

Ok, das ist eine gute Idee. D.h. also dass ich einfach den Inhalt jedes Knoten in einer Liste speichere? Wie kann man das dann aber in ein File schreiben? Bin da noch nicht so bewandert. Also vielleicht einfach jedes Element der Liste auf eine neue Zeile in einem .txt File schreiben?

Ist das dann aber nicht langsamer als Serialisierung?

 

[Krik]

Mir ist nicht ganz klar, worin dein Problem besteht. Einen Baum (welcher Art auch immer) ist doch nicht schwer zu implementieren.
Im Prinzip brauchst du doch nur die Knotenpunkte zu programmieren. So einer muss wissen, welcher sein Oberknoten ist, und welche seine Unterknoten sind. Das ist eigentlich sehr ähnlich zu einer doppelt verketteten Liste, nur mit dem Unterschied dass ein Element mehrere Nachfolger hat.

Also vielleicht einfach jedes Element der Liste auf eine neue Zeile in einem .txt File schreiben?
Ist das dann aber nicht langsamer als Serialisierung?

Die Serialisierung macht auch nichts anderes als jeden Attributinhalt in eine Datei zu speichern. Kann man auch sehr schön sehen, wenn man ein Objekt mit Arrays und Listen in eine XML-Datei serialisiert.

Btw, auch das Dictionary ist eine Hierarchie, auch wenn sie flach ist. (Wortklauberei, ich weiß.)
In der Form <string, object> entspricht sie einer klassischen Key-Value-Datenbank. Der Key wäre hier der Pfad (von Knoten zu Knoten, also zB C:\Pfad\nach\da.txt) und object die eigentlichen Daten. So ginge es auch.

 

[carom]

Btw, auch das Dictionary ist eine Hierarchie, auch wenn sie flach ist.

Wie meinst du das?

 

[Krik]

Es ist eine flache Hierarchie, d. h. alle Elemente sind gleichgestellt (= es gibt keine Ober- und Unterelemente).

 

[dcobra]

Und genau deswegen ist es keine Hierarchie Zumal der Begriff "flache Hierarchie" ja eigentlich der BWL entstammt und gewiss nicht bedeutet, dass es keine Ober- und Unterelemente gibt, im Gegenteil.

 

[carom]

Kenne den Begriff eigentlich auch eher aus der Wirtschaft, aber eigentlich wollte ich eher auf den technischen Aspekt hinaus. Bei einer Speicherstruktur ohne jegliche Ordnung und Abhängigkeit der Elemente untereinander, deren Position nur durch eine Streuwertfunktion bestimmt wird, hat man ja eigentlich gerade keine Hierarchie wie bei einem Baum, da ist der Begriff doch etwas irreführend. Es ist eher eine Art Liste oder Tabelle mit Buckets (Behältern), die sich gar nicht für einander interessieren.

 

[Krik]

Deswegen meinte ich ja auch, dass es eher Wortklauberei von mir ist.

 

[The Gunner]

Mir ist nicht ganz klar, worin dein Problem besteht. Einen Baum (welcher Art auch immer) ist doch nicht schwer zu implementieren.
Im Prinzip brauchst du doch nur die Knotenpunkte zu programmieren. So einer muss wissen, welcher sein Oberknoten ist, und welche seine Unterknoten sind. Das ist eigentlich sehr ähnlich zu einer doppelt verketteten Liste, nur mit dem Unterschied dass ein Element mehrere Nachfolger hat.

Da hast du recht, die Implementation würde ich vielleicht noch hinkriegen. Mein grösstes Problem ist aber, dass ich gerade nicht sehe was die Knoten für Werte halten sollen. Also wie benutzt man einen B-Baum für die Indexierung bei Dateien? Zuerst dachte ich dass jeder Knoten einen Teil des Pfades hält, also bei z.B. C:\foo\text1.txt hätte man einen root Knoten C, einen Kindnoten foo und dann nochmals einen Kindknoten text1.txt. Das ist dann aber wohl kein B-Baum.

Könntest du da vielleicht ein Beispiel für einen B-Baum machen?

Btw, auch das Dictionary ist eine Hierarchie, auch wenn sie flach ist. (Wortklauberei, ich weiß.)
In der Form <string, object> entspricht sie einer klassischen Key-Value-Datenbank. Der Key wäre hier der Pfad (von Knoten zu Knoten, also zB C:\Pfad\nach\da.txt) und object die eigentlichen Daten. So ginge es auch.

Das verstehe ich auch nicht ganz wie du da mit dem Dictionary den Index machen würdest.

Könntest du mir da vielleicht kurz detailierter erklären wie man einen Index mit einem B-Baum und einem Dictionary machen würde bzw. ein Beispiel machen?

 

[Krik]

Mein grösstes Problem ist aber, dass ich gerade nicht sehe was die Knoten für Werte halten sollen. Also wie benutzt man einen B-Baum für die Indexierung bei Dateien? Zuerst dachte ich dass jeder Knoten einen Teil des Pfades hält, also bei z.B. C:\foo\text1.txt hätte man einen root Knoten C, einen Kindnoten foo und dann nochmals einen Kindknoten text1.txt. Das ist dann aber wohl kein B-Baum.

Natürlich ist das ein Baum! Der Root-Knoten und der Kindknoten foo haben ja jeweils nicht nur einen Kindknoten. Je mehr Kindknoten du hinzufügst, desto mehr fächert sich der Baum auf.

Die Knoten selber haben eine Liste aller Kindknoten sowie ein Instanzattribut, dass auf den Elternknoten zeigt. Die einzige Ausnahme ist der Rootknoten, der hat keinen Elternknoten. Die Blätter, also das Ende eines Zweiges, haben (logischerweise) eine leere Liste von Kindknoten. Dafür sollten sie mindestens noch ein Instanzattribut mit dem Dateiinhalt haben.
Daraus ergibt sich: Ein Knoten speichert den Elternknoten, eine beliebige Anzahl von Kindknoten und einen Dateiinhalt. Zumindest dann, wenn du überall im Baum dieselbe Objektart verwenden willst.


Das mit dem Dictionary ist schnell erklärt:
Jeder Eintrag besteht aus einem Key (= Identifier, ID) und einem Value (= der eigentliche Inhalt). Der Key kann zB in der Form "C:\foo\bar.txt" vorliegen. Wenn du eine bestimmte Datei suchst, dann fragst du einfach nacheinander alle Keys ab und schaust, ob "bar.txt" enthalten ist.

 

[The Gunner]

Natürlich ist das ein Baum! Der Root-Knoten und der Kindknoten foo haben ja jeweils nicht nur einen Kindknoten. Je mehr Kindknoten du hinzufügst, desto mehr fächert sich der Baum auf.

Die Knoten selber haben eine Liste aller Kindknoten sowie ein Instanzattribut, dass auf den Elternknoten zeigt. Die einzige Ausnahme ist der Rootknoten, der hat keinen Elternknoten. Die Blätter, also das Ende eines Zweiges, haben (logischerweise) eine leere Liste von Kindknoten. Dafür sollten sie mindestens noch ein Instanzattribut mit dem Dateiinhalt haben.
Daraus ergibt sich: Ein Knoten speichert den Elternknoten, eine beliebige Anzahl von Kindknoten und einen Dateiinhalt. Zumindest dann, wenn du überall im Baum dieselbe Objektart verwenden willst.

Ja, aber was wird denn in den Knoten gespeichert? Man braucht ja für jede Sucheigenschaft einen separaten Baum, also wenn man die Dateien nach dem Namen indizieren will einen Baum, für die Suche nach dem Erstelldatum einen neuen Baum etc.

Ich möchte zuerst einfach mal einen Index nach dem Namen erstellen. Dann müssen die Knoten doch einfach die Dateinamen halten, also z.B. "foo.txt", "bla.txt" und nicht den gesamten Pfad. Jeder Knoten hat dann als value noch zusätzlich einen Link zu dem entsprechenden File.

Oder sehe ich das falsch?

 

[Krik]

Du kannst in den Knoten speichern, was du willst (Datum, Besitzer, Zugriffsrechte, etc.). Und danach kannst du doch auch suchen lassen, indem ein Algorithmus den Baum entlang wandert.

 

[The Gunner]

Ok, aber der Baum muss auch nach einem gewissen Kriterium aufgebaut bzw. rebalanciert werden nach einer Lösch- oder Einfügeoperation. D.h. man kann den Baum z.B. nach den Filenamen aufbauen, aber nicht nach mehreren Attributen gleichzeitig. D.h. für jedes Attribut braucht man einen eigenen Baum.

 

[benneq]

Wenn du den Baum zur schnellen Suche benutzen willst, so brauchst du natürlich für jedes Attribut einen eigenen Baum.

Dabei ist zu beachten:
- Ändert(!!) sich ein Attribut, muss der jeweilige Baum neu sortiert werden. Alle anderen Bäume nicht.
- Wird ein neues Element hinzugefügt (oder gelöscht) müssen alle Bäume neu sortiert werden.

Prinzipiell legt man in den Bäumen nur eine Referenz auf den kompletten Datensatz ab. Sodass man bei der Aktualisierung eines Attributs nur den einen Baum neu sortieren muss und den Datensatz, aber eben nicht(!!) alle Bäume.

 

[The Gunner]

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

http://code.google.com/p/my-alogori...c/net/rubyeye/algorithms/ch12/BTree.java?r=13

http://algs4.cs.princeton.edu/62btrees/BTree.java.html

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.

 

[Krik]

Ich habe den Eindruck, dass du keine Ahnung vom Programmieren hast - sonst würdest du nicht nach einer delete-Methode fragen, sondern sie selbst implementieren. Das ist nämlich wirklich nicht schwierig.
Überhaupt hätte man ohne Probleme alles selbst implementieren können, ohne hier nachzufragen. Das hätte sogar ordentlich Zeit gespart.

Mein Tipp ist, dass du dir erst (nochmal) die Grundlagen der Programmierung in C# anschaust. Insbesondere ein Kapitel über Algorithmen und Datenstrukturen sind hier empfehlenswert.

 

[The Gunner]

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