Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
B-Baum Indexstruktur erstellen

Moderationshinweis von herbivore (21.03.2013 - 18:25:25):

In diesem Thread geht laut Titel um B-Bäume. Einige Antworten beziehen sich jedoch fälschlicherweise auf binäre Bäume. Wie Scavanger weiter unten richtig sagt: B-Baum != Binärbaum. Das B in B-Baum steht (mutmaßlich) für balanciert, jedenfalls nicht für binär.

MrTiger
myCSharp.de - Member



Dabei seit:
Beiträge: 5

Themenstarter:

B-Baum Indexstruktur erstellen

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo MrTiger,

wenn du weiß, wie B-Bäume in der Theorie aufgebaut sind, was sind dann die konkreten Punkte, die dich an einer Umsetzung hindern? Was hast du schon probiert? Wo genau hängst du? Was genau ist dir unklar? Siehe dazu auch [Hinweis] Wie poste ich richtig? Punkt 4 und 5 (und vorsorglich auch Punkt 1.1.1 und 1.1).

herbivore
private Nachricht | Beiträge des Benutzers
f_igy
myCSharp.de - Member



Dabei seit:
Beiträge: 117

beantworten | zitieren | melden

Hi,

wie wär's damit:

SortedList (generische Klasse)

Gruß
f_igy
private Nachricht | Beiträge des Benutzers
Mallett
myCSharp.de - Member



Dabei seit:
Beiträge: 176

beantworten | zitieren | melden

Du brauchst doch nur eine Klasse Node, die zwei weitere Nodes hat. Dann die üblichen Funktionen zum Anhängen von Knoten (mit Sortierung beim Binärbaum). Dann vielleicht noch ein paar rekursive Methoden zum Abfragen der Tiefe eines Knotens, oder der Anzahl der Blätter vom aktuellen Knoten aus gesehn, was Du halt so brauchst.
private Nachricht | Beiträge des Benutzers
MrTiger
myCSharp.de - Member



Dabei seit:
Beiträge: 5

Themenstarter:

beantworten | zitieren | melden

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 gebrauchen so wie es Mallett vorgeschlagen hat. 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 verwenden wie f_igy vorgeschlagen hat oder einen Dictionary. 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?
private Nachricht | Beiträge des Benutzers
Mallett
myCSharp.de - Member



Dabei seit:
Beiträge: 176

beantworten | zitieren | melden

Hier dürftest Du schon ziemlich konkrete Tipps zur Implementierng finden:
Binärbaum
private Nachricht | Beiträge des Benutzers
[email protected]
myCSharp.de - Member



Dabei seit:
Beiträge: 407

beantworten | zitieren | melden

Hi...

ich frag mich grade wie du ein virtuelles Filesystem in dem es (nehm ich mal an) beliebig viele Unterverzeichnisse und Dateien geben kann/soll mit einem Binär-Baum realisieren willst.

Jeder Knoten in einem Binär-Baum hat ja maximal 2 Unterknoten.

lg
private Nachricht | Beiträge des Benutzers
Scavanger
myCSharp.de - Member

Avatar #avatar-3209.jpg


Dabei seit:
Beiträge: 323

beantworten | zitieren | melden

@Mallett und [email protected]:

B-Baum != Binärbaum

Ein B-Baum kann mehr als 2 Unterknoten haben.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Scavanger am .

using System;class H{static string z(char[]c){string r="";for(int x=0;x<(677%666);x++)r+=c[
x];return r;}static void Main(){int[]c={798,218,229,592,232,274,813,585,229,842,275};char[]
b=new char[11];for(int p=0;p<((59%12));p++)b[p]=(char)(c[p]%121);Console.WriteLine(z(b));}}
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo MrTiger,
Zitat
Implementiert habe ich noch nie einen
irgendwann ist immer das erste Mal. Es gibt ja im Netz genug Beschreibungen, aus denen man die Anforderungen an die einzelnen Operationen entnehmen kann.
Zitat
Gibt es für B-Bäume keine library?
Google-Suche nach b-baum c# und dann z.B. erster Treffer.
Zitat
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
Und warum meinst du, dass das in einem B-Baum geht? Bzw. wenn es in einem B-Baum geht, warum sollte es dann nicht in einer SortedList oder einem Dictionary gehen? Natürlich muss der Key in einem Dictionary (und auch in einer SortedList) eindeutig sein, aber das Value kann man ja beliebig wählen; es kann also auch eine Liste sein.
Zitat
Könnte man z.B. das Objekt einfach serialisieren und in eine Datei schreiben und bei Gebrauch des Indexes einfach wieder deserialisieren?
Klar, kann man machen. Allerdings sollte auch nicht so schwer sein, die Daten in einem lesbaren Format in eine Datei zu schreiben und später zurück zu lesen. Im einfachsten Fall speichert man alles als Liste, die man beim Einlesen mit den normalen Operationen, die auch sonst benutzt werden, in die Datenstruktur (egal, für welche du dich entscheidest) einfügt.

herbivore
private Nachricht | Beiträge des Benutzers
FZelle
myCSharp.de - Experte



Dabei seit:
Beiträge: 10083

beantworten | zitieren | melden

Wenn ich Datenstrukturen wie Listen oder Bäume suche, schaue ich immer zuerst was C5 bietet.
private Nachricht | Beiträge des Benutzers
MrTiger
myCSharp.de - Member



Dabei seit:
Beiträge: 5

Themenstarter:

beantworten | zitieren | melden

Zitat
Und warum meinst du, dass das in einem B-Baum geht? Bzw. wenn es in einem B-Baum geht, warum sollte es dann nicht in einer SortedList oder einem Dictionary gehen? Natürlich muss der Key in einem Dictionary (und auch in einer SortedList) eindeutig sein, aber das Value kann man ja beliebig wählen; es kann also auch eine Liste sein.

Weil ein B-Baum hierarchisch ist. 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?
Zitat
Klar, kann man machen. Allerdings sollte auch nicht so schwer sein, die Daten in einem lesbaren Format in eine Datei zu schreiben und später zurück zu lesen. Im einfachsten Fall speichert man alles als Liste, die man beim Einlesen mit den normalen Operationen, die auch sonst benutzt werden, in die Datenstruktur (egal, für welche du dich entscheidest) einfügt.

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?

Das braucht ja wohl wahrscheinlich weniger Speicherplatz als Objekte serialisieren, ist das dann aber nicht viel langsamer?
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo MrTiger,
Zitat
Oder sehe ich das falsch?
zumindest ist das nach meinem Verständnis kein B-Baum. Sondern einfach ein Baum, der die Verzeichnisstruktur direkt nachbildet.
Zitat
Also vielleicht einfach jedes Element der Liste auf eine neue Zeile in einem .txt File schreiben?
Klar, kann man machen.
Zitat
Das braucht ja wohl wahrscheinlich weniger Speicherplatz als Objekte serialisieren, ist das dann aber nicht viel langsamer?
Mach dir um die Performance mal keine Sorgen.
Zitat
Wie kann man das dann aber in ein File schreiben? Bin da noch nicht so bewandert.
Naja, in diesem Bereich zumindest etwas bewandert zu sein, setzen wir hier allerdings voraus, siehe [Hinweis] Wie poste ich richtig? Punkt 1.1.1. Auch die Nachfragen zu den Datenstrukturen machen den Eindruck, als würde es dir nützen, (nochmal) ein gutes C# Buch durchzuarbeiten.


herbivore
private Nachricht | Beiträge des Benutzers