Laden...

B-Baum Indexstruktur erstellen

Erstellt von MrTiger vor 11 Jahren Letzter Beitrag vor 11 Jahren 4.618 Views
Thema geschlossen
Hinweis von herbivore vor 11 Jahren

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.

M
MrTiger Themenstarter:in
3 Beiträge seit 2013
vor 11 Jahren
B-Baum Indexstruktur erstellen

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.

49.485 Beiträge seit 2005
vor 11 Jahren

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

F
115 Beiträge seit 2012
vor 11 Jahren

Hi,

wie wär's damit:

SortedList (generische Klasse)

Gruß
f_igy

M
171 Beiträge seit 2012
vor 11 Jahren

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.

M
MrTiger Themenstarter:in
3 Beiträge seit 2013
vor 11 Jahren

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?

  1. 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.

  2. 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?

M
171 Beiträge seit 2012
vor 11 Jahren

Hier dürftest Du schon ziemlich konkrete Tipps zur Implementierng finden:
Binärbaum

M
402 Beiträge seit 2005
vor 11 Jahren

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

309 Beiträge seit 2008
vor 11 Jahren

@Mallett und M@TUK:

B-Baum != Binärbaum

Ein B-Baum kann mehr als 2 Unterknoten haben.

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));}}

49.485 Beiträge seit 2005
vor 11 Jahren

Hallo MrTiger,

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.

Gibt es für B-Bäume keine library? Google-Suche nach b-baum c# und dann z.B. erster Treffer.

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.

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

F
10.010 Beiträge seit 2004
vor 11 Jahren

Wenn ich Datenstrukturen wie Listen oder Bäume suche, schaue ich immer zuerst was C5 bietet.

M
MrTiger Themenstarter:in
3 Beiträge seit 2013
vor 11 Jahren

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?

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?

49.485 Beiträge seit 2005
vor 11 Jahren

Hallo MrTiger,

Oder sehe ich das falsch?

zumindest ist das nach meinem Verständnis kein B-Baum. Sondern einfach ein Baum, der die Verzeichnisstruktur direkt nachbildet.

Also vielleicht einfach jedes Element der Liste auf eine neue Zeile in einem .txt File schreiben?

Klar, kann man machen.

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.

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

Thema geschlossen