Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
B-Baum Indexstruktur erstellen
73 views
Skip to first unread message
Helvetic...@gmx.ch
Mar 22, 2013, 7:37:39 PM3/22/13
to
Hallo,
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?
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?
Peter Fleischer
Mar 23, 2013, 3:24:34 AM3/23/13
to
Hi,
ich w�rde den "Index" als hierarchische Struktur mit Hilfe der
XElement-Klasse erstellen und verwalten. Ein Objekt vom Typ XElement l�sst
sich problemlos serialisieren und als XML-Strom ablegen und wieder laden.
--
Peter Fleischer
ich w�rde den "Index" als hierarchische Struktur mit Hilfe der
XElement-Klasse erstellen und verwalten. Ein Objekt vom Typ XElement l�sst
sich problemlos serialisieren und als XML-Strom ablegen und wieder laden.
--
Peter Fleischer
Helvetic...@gmx.ch
Mar 24, 2013, 1:56:16 PM3/24/13
to
Am Samstag, 23. März 2013 08:24:34 UTC+1 schrieb Peter Fleischer:
> Hi,
>
> ich w�rde den "Index" als hierarchische Struktur mit Hilfe der
>
> XElement-Klasse erstellen und verwalten. Ein Objekt vom Typ XElement l�sst
Ich verstehe da deinen Ansatz nicht ganz. Könntest du da vielleicht ein Beispiel machen? Ich verstehe z.B. nicht was die Knoten als key speichern sollen.
> Hi,
>
> ich w�rde den "Index" als hierarchische Struktur mit Hilfe der
>
> XElement-Klasse erstellen und verwalten. Ein Objekt vom Typ XElement l�sst
>
> sich problemlos serialisieren und als XML-Strom ablegen und wieder laden.
>
>
>
> --
>
> Peter Fleischer
Hi Peter
> sich problemlos serialisieren und als XML-Strom ablegen und wieder laden.
>
>
>
> --
>
> Peter Fleischer
Ich verstehe da deinen Ansatz nicht ganz. Könntest du da vielleicht ein Beispiel machen? Ich verstehe z.B. nicht was die Knoten als key speichern sollen.
Peter Fleischer
Mar 24, 2013, 5:12:39 PM3/24/13
to
Hi,
Du hast logische Knoten, wobei jeder ein Verzeichnis oder eine Datei
beschreibt. Daf�r kannst Du Objekte vom Typ einer Klasse nutzen, deren
Eigenschaften das Verzeichnis und die Datei beschreiben. Bei der Festlegung
der Eigenschaften hast Du alle Freiheiten. Wichtig ist lediglich, dass sich
die Klasse serialisieren l�sst. Diese Objekte kannst Du in einer flachen
Listen verwalten.
F�r die Verwaltung der Struktur nutzt Du Objekte vom Typ XElement. Es bleibt
nur noch, die Struktur mit den Objekten, die die Verzeichnisse und Dateien
beschreiben, zu verkn�pfen. Je nach Ziel kannst Du das entweder mit Verweis
aus den Objekten auf eine XElement oder umgekehrt machen. In der Oberfl�che
kannst Du dann f�r jeden darzustellenden Knoten (z.B. in einem TreeView)
Information aus den Objekten als Zeichenkette und z.B. Bild darstellen.
--
Peter Fleischer
Du hast logische Knoten, wobei jeder ein Verzeichnis oder eine Datei
beschreibt. Daf�r kannst Du Objekte vom Typ einer Klasse nutzen, deren
Eigenschaften das Verzeichnis und die Datei beschreiben. Bei der Festlegung
der Eigenschaften hast Du alle Freiheiten. Wichtig ist lediglich, dass sich
die Klasse serialisieren l�sst. Diese Objekte kannst Du in einer flachen
Listen verwalten.
F�r die Verwaltung der Struktur nutzt Du Objekte vom Typ XElement. Es bleibt
nur noch, die Struktur mit den Objekten, die die Verzeichnisse und Dateien
beschreiben, zu verkn�pfen. Je nach Ziel kannst Du das entweder mit Verweis
aus den Objekten auf eine XElement oder umgekehrt machen. In der Oberfl�che
kannst Du dann f�r jeden darzustellenden Knoten (z.B. in einem TreeView)
Information aus den Objekten als Zeichenkette und z.B. Bild darstellen.
--
Peter Fleischer
Helvetic...@gmx.ch
Mar 27, 2013, 7:52:47 PM3/27/13
to
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-alogorithm-implementation/source/browse/trunk/src/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.
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-alogorithm-implementation/source/browse/trunk/src/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.
Peter Fleischer
Mar 28, 2013, 4:04:11 AM3/28/13
to
Hi,
mir ist unklar, was Du erreichen willst.
Du hast Objekte (Dateien in einer zip-Datei), die hierarchisch strukturiert
sind. Diese Struktur willst Du in einer Knotenstruktur darstellen (s. Absatz
3 Deines Ausgangspostings).
Mit einem B-Tree kannst Du das nicht machen, da Du nicht sicherstellen
kannst, dass unterhalb eines Knotens eine Maximalzahl untergeordneter Knoten
nicht überschritten wird.
Ein Dictionary ist eine flache (einstufige) Liste mit Schlüssel für jedes
Objekt. Der Schlüssel wird intern mit einem B-Tree verwaltet. Wenn Du mit
einem Dictionary Hierarchien verwalten willst, dann musst Du in jedem Objekt
den Hierarchiepfad verwalten. Die Programmlogik für Veränderungen
(Verschieben, Hinzufügen, Löschen) wird damit recht komplex.
Die einfachste Möglichkeit, hierarchisch organisierte Objekte mit beliebiger
Breite zu verwalten, ist die Nutzung von Objekten vom Typ XElement.
Nachteilig ist lediglich, dass alle untergeordneten Knoten eines Knoten im
RAM gehalten werden. Bei großen Datenmengen kann man da an Grenzen stoßen.
Deshalb muss man auf extern abgelegte XML-Strukturen ausweichen, auf die mit
XPath zugegriffen wird.
--
Peter Fleischer
mir ist unklar, was Du erreichen willst.
Du hast Objekte (Dateien in einer zip-Datei), die hierarchisch strukturiert
sind. Diese Struktur willst Du in einer Knotenstruktur darstellen (s. Absatz
3 Deines Ausgangspostings).
Mit einem B-Tree kannst Du das nicht machen, da Du nicht sicherstellen
kannst, dass unterhalb eines Knotens eine Maximalzahl untergeordneter Knoten
nicht überschritten wird.
Ein Dictionary ist eine flache (einstufige) Liste mit Schlüssel für jedes
Objekt. Der Schlüssel wird intern mit einem B-Tree verwaltet. Wenn Du mit
einem Dictionary Hierarchien verwalten willst, dann musst Du in jedem Objekt
den Hierarchiepfad verwalten. Die Programmlogik für Veränderungen
(Verschieben, Hinzufügen, Löschen) wird damit recht komplex.
Die einfachste Möglichkeit, hierarchisch organisierte Objekte mit beliebiger
Breite zu verwalten, ist die Nutzung von Objekten vom Typ XElement.
Nachteilig ist lediglich, dass alle untergeordneten Knoten eines Knoten im
RAM gehalten werden. Bei großen Datenmengen kann man da an Grenzen stoßen.
Deshalb muss man auf extern abgelegte XML-Strukturen ausweichen, auf die mit
XPath zugegriffen wird.
--
Peter Fleischer
Helvetic...@gmx.ch
Mar 28, 2013, 6:31:33 PM3/28/13
to
Ich habe mich für einen B-tree entschieden. Ist sowieso gut sowas mal zu machen.
Ich brauche v.a. Code oder Pesudocode für die delete methode inklusive Rotatonen etc. des B-Baums. Den Rest sollte ich hinbekommen.
Ich brauche v.a. Code oder Pesudocode für die delete methode inklusive Rotatonen etc. des B-Baums. Den Rest sollte ich hinbekommen.
Peter Fleischer
Mar 29, 2013, 12:01:16 AM3/29/13
to
Hi,
in den von Dir geposteten Links steht eigentlich alles drin. Wichtig sind
die Parameter, die zur Reorganisation einer Indexebene f�hren.
Wie schon geschrieben hat aber ein B-Tree nichts mit Deiner urspr�nglichen
Problemstellung zu tun. Ein B-Tree ist lediglich f�r die Organisation des
Index f�r eine flache Liste zust�ndig.
--
Peter Fleischer
in den von Dir geposteten Links steht eigentlich alles drin. Wichtig sind
die Parameter, die zur Reorganisation einer Indexebene f�hren.
Wie schon geschrieben hat aber ein B-Tree nichts mit Deiner urspr�nglichen
Problemstellung zu tun. Ein B-Tree ist lediglich f�r die Organisation des
Index f�r eine flache Liste zust�ndig.
--
Peter Fleischer
Helvetic...@gmx.ch
Mar 29, 2013, 5:47:44 AM3/29/13
to
Ja, da hast du recht, in den Links steht alles drin, aber eben nicht der delete bzw. remove Algorithmus und den finde ich recht kompliziert wegen den verschiedenen Fällen von rebalancing.
Peter Fleischer
Mar 29, 2013, 1:14:12 PM3/29/13
to
Hi,
ja genau das rebalancing ist das Wichtigste, da damit die Anzahl der Aufrufe
f�r die Suche bestimmt wird. Dazu musst Du erst einmal Festlegungen zur
minimalen und maximalen Breit einer Indexebene festlegen. Dann kannst Du
beim Hinzuf�gen oder L�schen entscheiden, ob die Indexebenen umgebaut werden
m�ssen.
--
Peter Fleischer
ja genau das rebalancing ist das Wichtigste, da damit die Anzahl der Aufrufe
f�r die Suche bestimmt wird. Dazu musst Du erst einmal Festlegungen zur
minimalen und maximalen Breit einer Indexebene festlegen. Dann kannst Du
beim Hinzuf�gen oder L�schen entscheiden, ob die Indexebenen umgebaut werden
m�ssen.
--
Peter Fleischer
Helvetic...@gmx.ch
Apr 6, 2013, 7:47:29 AM4/6/13
to
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?
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?
Peter Fleischer
Apr 7, 2013, 1:47:07 PM4/7/13
to
Hi,
die Breite einer Indexebene sollte entsprechend den Zugriffszeiten auf einen
Speicherbereich gewählt werden, der mit einen Zugriff in den RAM geladen
wird. Üblicherweise ist das ein Sektor auf der Festplatte. Der Zugriff auf
einen Indexeintrag in dem Sektor kann dann mit einem CPU-Befehl recht
schnell ausgeführt werden.
--
Peter Fleischer
die Breite einer Indexebene sollte entsprechend den Zugriffszeiten auf einen
Speicherbereich gewählt werden, der mit einen Zugriff in den RAM geladen
wird. Üblicherweise ist das ein Sektor auf der Festplatte. Der Zugriff auf
einen Indexeintrag in dem Sektor kann dann mit einem CPU-Befehl recht
schnell ausgeführt werden.
--
Peter Fleischer
Helvetic...@gmx.ch
Apr 14, 2013, 5:54:36 AM4/14/13
to
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?
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?
Peter Fleischer
Apr 20, 2013, 4:17:27 AM4/20/13
to
Hi,
eine h�here Order bewirkt einen gr��eren Index-Block. Die Gr��e sollte so
gew�hlt werden, dass ein Optimum zwischen Zeit f�r das Lesen und Scannen
eines Blocks und der Zeit f�r die Aufrufe mehrerer Bl�cke und den bei
mehreren Aufrufen k�rzeren Scan-Zeiten gefunden wird.
--
Peter Fleischer
eine h�here Order bewirkt einen gr��eren Index-Block. Die Gr��e sollte so
gew�hlt werden, dass ein Optimum zwischen Zeit f�r das Lesen und Scannen
eines Blocks und der Zeit f�r die Aufrufe mehrerer Bl�cke und den bei
mehreren Aufrufen k�rzeren Scan-Zeiten gefunden wird.
--
Peter Fleischer
0 new messages