B-Baum Implementation

[Helveticus]

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/it...p14/BTree.java

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

[Christian Marquardt]

http://megacz.com/software/btree-jav...ree/BTree.html

und wenn das obige das ist, was du dir vorstellst, warum benutzt du es nicht und fügst das löschen hinzu?

[Helveticus]

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

Das löschen bzw. delete ist eben nicht einfach, da es zu Rotationen führen kann etc.

[fanderlf]

Hm also ich habe jetzt nach 5 Minuten google schon einige Antworten aus der .Net Ecke gefunden. Unter anderem auch das hier:

https://github.com/rdcastro/btree-dotnet

Die Qualität kann ich nicht beurteilen weil ich nicht sehr tief in der Materie drin stecke, aber es gibt immerhin ein paar Unit Tests dazu. Das ist meistens kein schlechtes Zeichen.

[Christian Marquardt]

Ich brauche v.a. Code oder Pesudocode für die delete methode inklusive Rotatonen

Die obige Javaklasse hat den Code für das remove. Einfach mal reinschauen

[Helveticus]

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?

[Helveticus]

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.