Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
B-Baum Implementation
311 views
Skip to first unread message
Helvetic...@gmx.ch
Mar 27, 2013, 8:00:56 PM3/27/13
to
Hallo
Ich suche Code welcher einen B-tree oder B+-tree implementiert. Am besten in C# aber auch Java wäre 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?
Ich suche Code welcher einen B-tree oder B+-tree implementiert. Am besten in C# aber auch Java wäre 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?
Robert Hartmann
Mar 31, 2013, 5:54:30 PM3/31/13
to
Hallo,
Am 28.03.2013 01:00, schrieb Helvetic...@gmx.ch:
> Hallo
>
> Ich suche Code welcher einen B-tree oder B+-tree implementiert.
http://www.seanster.com/BplusTree/BplusTree.html
Code-Beispiele sind dort auch verlinkt.
Gru� Robert
Am 28.03.2013 01:00, schrieb Helvetic...@gmx.ch:
> Hallo
>
> Ich suche Code welcher einen B-tree oder B+-tree implementiert.
Code-Beispiele sind dort auch verlinkt.
Gru� Robert
Helvetic...@gmx.ch
Apr 6, 2013, 7:48:56 AM4/6/13
to
Vielen Dank Robert.
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?
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?
Robert Hartmann
Apr 6, 2013, 3:26:43 PM4/6/13
to
Am 06.04.2013 13:48, schrieb Helvetic...@gmx.ch:
> Vielen Dank Robert.
:-) bitte sehr.
> 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?
Hast du irgendwelche Grenzen für das virtuelle Dateisystem?
Falls es sich zusätzlich noch um ein sequenziell verteiltes Dateisystem
handelt, wäre es ggf interessant die Ordnung auf die Anzahl der
beteiligten Datenspeicher zusetzen?
Beste Grüße,
Robert
> Vielen Dank Robert.
:-) bitte sehr.
> 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?
Falls es sich zusätzlich noch um ein sequenziell verteiltes Dateisystem
handelt, wäre es ggf interessant die Ordnung auf die Anzahl der
beteiligten Datenspeicher zusetzen?
Beste Grüße,
Robert
Jörg
Apr 7, 2013, 6:32:53 AM4/7/13
to
ich den Baum möglichst voll machen. Bei häufigen Änderungen würde ich
den Baum auch mehr entarten lassen.
Da muss man je nach Anwendung einen Kompromiss finden. Genau so sieht es
ja aus, wenn man ein ext4 erzeugt: Es gibt viele Optionen und alle
machen in gewissen Situationen Sinn.
Jörg
Marcel Müller
Apr 8, 2013, 11:10:57 AM4/8/13
to
Hallo,
On 28.03.2013 01:00, Helvetic...@gmx.ch wrote:
> Ich suche Code welcher einen B-tree oder B+-tree implementiert. Am besten in C# aber auch Java w�re ok. Ich habe bei Google einige Implementationen gefunden, z.B.
von Google selbst gibt es eine m.E. recht gute Implementierung unter
Apache-Lizenz. Ist allerdings in C++. Aber den Algorithmus kann man
trotzdem klauen (wenn man C++ mit templates lesen kann).
http://code.google.com/p/cpp-btree/
Er ist erstaunlich �hnlich zu dem was ich mal implementiert habe. Aber
da hat ganz sicher keiner von beiden abgeschrieben. Das ist einfach
Konvergenz.
Dass Google den Code nach C# oder Java portiert hat, halte ich f�r
unwahrscheinlich. Das ist nicht deren prim�res Portfolio.
> 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.
Wenn Du Libraries im Quellcode hast, kannst Du dir meist den gew�nschten
Teil heraussch�len. Du musst halt mit der Lizenz aufpassen. Aber wenn Du
es sowieso in einer anderen Sprache und "in deinen eigenen Worten"
schreibst, dann ist das sowieso meist hinf�llig. Die Idee des B-Tree
Algorithmus unterliegt keinem Schutz.
Marcel
On 28.03.2013 01:00, Helvetic...@gmx.ch wrote:
> Ich suche Code welcher einen B-tree oder B+-tree implementiert. Am besten in C# aber auch Java w�re ok. Ich habe bei Google einige Implementationen gefunden, z.B.
von Google selbst gibt es eine m.E. recht gute Implementierung unter
Apache-Lizenz. Ist allerdings in C++. Aber den Algorithmus kann man
trotzdem klauen (wenn man C++ mit templates lesen kann).
http://code.google.com/p/cpp-btree/
Er ist erstaunlich �hnlich zu dem was ich mal implementiert habe. Aber
da hat ganz sicher keiner von beiden abgeschrieben. Das ist einfach
Konvergenz.
Dass Google den Code nach C# oder Java portiert hat, halte ich f�r
unwahrscheinlich. Das ist nicht deren prim�res Portfolio.
> 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.
Wenn Du Libraries im Quellcode hast, kannst Du dir meist den gew�nschten
Teil heraussch�len. Du musst halt mit der Lizenz aufpassen. Aber wenn Du
es sowieso in einer anderen Sprache und "in deinen eigenen Worten"
schreibst, dann ist das sowieso meist hinf�llig. Die Idee des B-Tree
Algorithmus unterliegt keinem Schutz.
Marcel
Helvetic...@gmx.ch
Apr 14, 2013, 6:04:11 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?
By the way, die order eines B-Baums beschreibt die minimale Anzahl keys in einem Knoten.
>Hast du irgendwelche Grenzen für das virtuelle Dateisystem?
Nein
>Falls es sich zusätzlich noch um ein sequenziell verteiltes Dateisystem
>handelt, wäre es ggf interessant die Ordnung auf die Anzahl der
>beteiligten Datenspeicher zusetzen?
Es ist kein sequenziell verteiltes Dateisystem.
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.
>Hast du irgendwelche Grenzen für das virtuelle Dateisystem?
>Falls es sich zusätzlich noch um ein sequenziell verteiltes Dateisystem
>handelt, wäre es ggf interessant die Ordnung auf die Anzahl der
>beteiligten Datenspeicher zusetzen?
Marcel Müller
Apr 18, 2013, 11:22:39 AM4/18/13
to
Hallo,
On 14.04.2013 12:04, Helvetic...@gmx.ch wrote:
> 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.
Das ist so. Aber bedenke dass hier so oder so ein exponentielles
Wachstum vorliegt. Ein B-Baum mit Node-Gr��e 32 kann mit vier
Node-Zugriffen bereits 1082400 Eintr�ge abdecken. Ein Baum mit der
Node-Gr��e 100 br�uchte f�r die selbe Menge ebenfalls 4 Ebenen - wenn
auch gerade so. Kurzum, der Nutzen gr��erer Nodes h�lt sich in Grenzen.
> 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.
Hier setzt Du stillschweigend voraus, dass alle Files in einem einzigen
B-Baum liegen. Lange nicht jedes Dateisystem tut so etwas. Die Redundanz
durch die h�ufig gemeinsamen Pfadnamen w�re doch etwas gro�.
�blicherweise haben die Ordner eine eigene sortierte Struktur. Bei
Dateisystemen, die diese Bezeichnung auch verdienen, sind B-B�ume oder
B+-B�ume hier die Regel. Damit ergibt sich in Summe eher so eine Art
Patricia-Trie, in dem jeder Knoten ein Verzeichnis ist, das selbst
wieder als B-Baum organisiert ist.
> Und was ist genau eine h�here order? Z.B. 100?
Ich nehme an, Du beziehst Dich auf den englischen Wikipedia-Artikel zu
B-B�umen. Damit ist wohl die Gr��e der Nodes gemeint.
> By the way, die order eines B-Baums beschreibt die minimale Anzahl keys in einem Knoten.
Eher die maximale. Die minimale definiert sich �ber den F�llstand. Ohne
weitere Ma�nahmen ist das die H�lfte der Gr��e. Bei B*-B�umen durch
aufwendigeres Rebalancing 2/3.
F�r eine Dateisystemanwendung w�rde ich die Strukturen eher an der Gr��e
der Cluster ausrichten. Nimmt man weniger, ist das einfach nur Unsinn,
weil der verbleibende Platz niemandem nutzt, nimmt man mehr, k�nnte es
vorkommen, dass man um eine Node zu lesen mehrere IOs braucht, weil sie
nicht mehr am St�ck auf dem Datentr�ger stehen. Dann h�tte man auch
gleich mehrere Nodes nehmen k�nnen. Da gibt es nat�rlich je nach
Anwendungsfall einen Break-Even.
Wenn man, wie heute �blich, gen�gend RAM hat, ist die wohl wichtigste
Beschleunigung, m�glichst alle wichtigen Verwaltungsinformationen im
Speicher zu halten. Welche Sortierung dabei zum Einsatz kommt, ist dann
eher zweitrangig. RAM ist eigentlich immer schneller als IO. Wenn man
nat�rlich auf gute Skalierbarkeit aus ist, dann kann man nicht einfach
eine unendliche Menge RAM voraussetzen und sollte zu den klassischen
L�sungen tendieren, wie sie auch Datenbanken nutzen. Eine dynamische
Node-Gr��e ist hier hilfreich.
Marcel
On 14.04.2013 12:04, Helvetic...@gmx.ch wrote:
> 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.
Das ist so. Aber bedenke dass hier so oder so ein exponentielles
Wachstum vorliegt. Ein B-Baum mit Node-Gr��e 32 kann mit vier
Node-Zugriffen bereits 1082400 Eintr�ge abdecken. Ein Baum mit der
Node-Gr��e 100 br�uchte f�r die selbe Menge ebenfalls 4 Ebenen - wenn
auch gerade so. Kurzum, der Nutzen gr��erer Nodes h�lt sich in Grenzen.
> 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.
Hier setzt Du stillschweigend voraus, dass alle Files in einem einzigen
B-Baum liegen. Lange nicht jedes Dateisystem tut so etwas. Die Redundanz
durch die h�ufig gemeinsamen Pfadnamen w�re doch etwas gro�.
�blicherweise haben die Ordner eine eigene sortierte Struktur. Bei
Dateisystemen, die diese Bezeichnung auch verdienen, sind B-B�ume oder
B+-B�ume hier die Regel. Damit ergibt sich in Summe eher so eine Art
Patricia-Trie, in dem jeder Knoten ein Verzeichnis ist, das selbst
wieder als B-Baum organisiert ist.
> Und was ist genau eine h�here order? Z.B. 100?
Ich nehme an, Du beziehst Dich auf den englischen Wikipedia-Artikel zu
B-B�umen. Damit ist wohl die Gr��e der Nodes gemeint.
> By the way, die order eines B-Baums beschreibt die minimale Anzahl keys in einem Knoten.
weitere Ma�nahmen ist das die H�lfte der Gr��e. Bei B*-B�umen durch
aufwendigeres Rebalancing 2/3.
F�r eine Dateisystemanwendung w�rde ich die Strukturen eher an der Gr��e
der Cluster ausrichten. Nimmt man weniger, ist das einfach nur Unsinn,
weil der verbleibende Platz niemandem nutzt, nimmt man mehr, k�nnte es
vorkommen, dass man um eine Node zu lesen mehrere IOs braucht, weil sie
nicht mehr am St�ck auf dem Datentr�ger stehen. Dann h�tte man auch
gleich mehrere Nodes nehmen k�nnen. Da gibt es nat�rlich je nach
Anwendungsfall einen Break-Even.
Wenn man, wie heute �blich, gen�gend RAM hat, ist die wohl wichtigste
Beschleunigung, m�glichst alle wichtigen Verwaltungsinformationen im
Speicher zu halten. Welche Sortierung dabei zum Einsatz kommt, ist dann
eher zweitrangig. RAM ist eigentlich immer schneller als IO. Wenn man
nat�rlich auf gute Skalierbarkeit aus ist, dann kann man nicht einfach
eine unendliche Menge RAM voraussetzen und sollte zu den klassischen
L�sungen tendieren, wie sie auch Datenbanken nutzen. Eine dynamische
Node-Gr��e ist hier hilfreich.
Marcel
Jörg
Apr 23, 2013, 3:51:01 AM4/23/13
to
On 04/18/2013 05:22 PM, Marcel Müller wrote:
> Hallo,
>
> On 14.04.2013 12:04, Helvetic...@gmx.ch wrote:
>
> Hier setzt Du stillschweigend voraus, dass alle Files in einem einzigen
> B-Baum liegen. Lange nicht jedes Dateisystem tut so etwas. Die Redundanz
> durch die häufig gemeinsamen Pfadnamen wäre doch etwas groß.
> Hallo,
>
> On 14.04.2013 12:04, Helvetic...@gmx.ch wrote:
>
> Hier setzt Du stillschweigend voraus, dass alle Files in einem einzigen
> B-Baum liegen. Lange nicht jedes Dateisystem tut so etwas. Die Redundanz
> Üblicherweise haben die Ordner eine eigene sortierte Struktur. Bei
> Dateisystemen, die diese Bezeichnung auch verdienen, sind B-Bäume oder
> B+-Bäume hier die Regel. Damit ergibt sich in Summe eher so eine Art
> Patricia-Trie, in dem jeder Knoten ein Verzeichnis ist, das selbst
> wieder als B-Baum organisiert ist.
>
Ich dachte den B-Baum kann man bei mkfs.ext4 zwar konfigurieren
> wieder als B-Baum organisiert ist.
>
(„mkfs.ext4 ... -O dir_index ...”), er wäre aber nicht Standard. Für
Dateisysteme mit kleinen Ordnern (d.h. jeweils wenigen Dateien) ist das
Sortieren nur unnötiger Overhead, welcher bei jeder Änderung anfällt.
Auch die Suche wird komplizierter. Es reicht oft, wenn die
Unterverzeichnisse sortiert am Anfang des Verzeichnisses stehen. So
kommt man dann schnell durch den Baum. Bei kleinen Verzeichnissen ist es
wichtig, das ganze Verzeichnis mit wenigen Blockzugriffen lesen zu
können, die Struktur sollte also klein sein.
Gibt es eine Übersicht über die Verfahren und Optionen verschiedener
Dateisysteme?
>
> Marcel
Jörg
0 new messages