B-Baum Implementation

[MrTiger]

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_d ... BTree.java

http://code.google.com/p/my-alogorithm- ... .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?

[GilbertDur]

Ich denke, die folgenden Beispiele sind ganz gut:

http://www.codeproject.com/Articles/189 ... itten-in-C

http://www.vcskicks.com/binary-search-tree.php

http://chinmaylokesh.wordpress.com/2011 ... -the-tree/

[MrTiger]

Vielen Dank, allerdings ist ein binary search tree nicht das gleiche wie ein B-Tree.

[GilbertDur]

Mein Fehler, dann eben so:

http://www.smokycogs.com/blog/an-implem ... n-c-sharp/

[MrTiger]

Das ist immer noch ein binary tree.

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

[nufan]

Wie siehts damit aus?
http://google-opensource.blogspot.nl/20 ... -time.html
Code: https://code.google.com/p/cpp-btree/

EDIT:
Achja, es soll ja in Java oder C# sein...
http://code.google.com/p/java-algorithm ... BTree.java

[GilbertDur]

Ich weiß, das ist jetzt ne ganze Library, aber Anregungen kann man sich holen. Zumindest sehen mir die Methoden auf den ersten Blick nicht zu kompliziert aus:

https://github.com/rdcastro/btree-dotne ... ster/BTree

[MrTiger]

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?

[MrTiger]

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.

[Xin]

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?

Interessante Frage... normalerweise habe ich ein recht brauchbares Bauchgefühl. In Anbetracht der Tatsache, dass ich mich nicht daran erinnern kann, einen Index für ein Filesystem geschrieben zu haben, vermutlich ich, dass das keine sehr alltägliche Aufgabe ist, die mit einer solchen Frage wie "Magst Du lieber 2 oder 3 Kugeln Vanilleeis?" viele qualifizierte Antworten findet.
(Wobei es klingelt was... ich glaube das war mal eine Aufgabe im Studium, aber ich kann mich nicht entsinnen, einen Index da geschrieben zu haben... Altersdemenz )

Wenn mich wirklich die Leistungsunterschiede interessieren, ich also ein optimales Ergebnis haben will und das nichtmals annähernd abschätzen kann, was ich nehmen soll, nehme ich alles. Dann mache einen Testparcours, der möglichst gut meinen Anforderungen entspricht und jage reihenweise Implementationen dadurch.
Anschließend schaue ich, welche sich gut schlagen und warum. Ab da habe ich ein Bauchgefühl.

Und was ist genau eine höhere order? Z.B. 100?

Ich denke, das ist eine Frage, die Du je nach Datum anders beantwortet bekommst.

Ich habe Arbeitsspeicher in 64kb Chips (nicht Speicherriegeln, die kamen später) gekauft. Mit einer zusätzlichen Speicherkarte, gegen die eine große Grafikkarte heute eher überschaubar wirkt, habe ich dann meinen 1MB Rechner auf unglaubliche 3MB aufgerüstet. Damals hätte man diese Fragen sicherlich anders beantwortet.

Auch hier kann man nur sagen: Probiere es aus! Was kann Deine Hardware, wie groß ist Dein Problem? Sammelst Du ein paar Dutzend Millionen von Files oder nur paar Dutzend?
Wenn Du es ausprobierst, wirst Du Erfahrungen sammeln, und ich vermute, genau darum geht es doch, oder?