Left Up Algorithmen

Btree

Hier versuche ich einen B*-Baum mit RAMS zu bauen. Betriebssystemmaßig steckt eine speicherabbgebildete Datei dahinter.

Zum Algorithmus

Der Witz an B-Bäumen ist, daß sie an der Wurzel wachsen, und nicht an den Blättern. Dadurch wird die Balancierung erreicht.
B-tree
Balancierter Baum, in dem jeder Knoten zwischen t-1 und 2t-1 Kinder hat.
B+-Tree
Ein B-Baum, in dem die Schüssel in den Knoten gespeichert werden, die eigentlichen Sätze in den Blättern.
B*-tree
B-Baum, bei dem die Knoten nur zu 2/3 voll gehalten werden
Bei Donald E. Knuth: B-Trees werden in Band III, "Sorting And Searching" von The Art Of Computer Programming in Sektion 6.2.4, "Multiway Trees" naeher besprochen. (Hinweis von A.Kübler)

Bemerkungen

Testprogramm

btree
siehe Aufruffehlermeldung

Ach ja ...

Weitere Links zu Implementierungen

BTree-Implementation in C++
aber nicht parallelisiert
gxvtree
beschreibt eine B-Baum-Implementierung aber ConncurrentBtreeOperations beim Insert wird auch der ganze Baum geloggt.
(LizenzLGPL fuer commercial usw. )
The Design of the Infinity Data Base Engine B-Tree
in java, beschreibt oberflächlich verschiedene Locking-Strategien
Laut cl.cam.ac.uk hat die SPECjBB-Benchmark auch eine Btree-Implementierung

Informatik- und Netzwerkverein Ravensburg e.V Rudolf Weber