B-Tree-Komponente gesucht

[dizzy]

B-Tree ist eine irreführende Bezeichnung. B-Bäume sind etwas gaaanz anderes, als das was du gefunden hast. B <> binary!
B-Bäume sind Bäume die in Seiten organisiert sind, so dass ein Knoten nicht nur einen Wert, sonden ganze Listen von Werten enthalten, und sich die Kind-Knoten zwischen diese Werte gruppieren. Vorteil von B-Bäumen: Teilweise auf Langzeitdatenträger auslagerbar, und dadurch ein guter Kompromiss zwischen Speicheraufwand und Geschwindigkeit.

Was du jetzt gefunden hast ist ein sog. AVL-Baum. Das ist ein binärer Baum, bei dem zusätzlich darauf geachtet wird, dass benachbarte Blätter eines Blattes maximal 1 Niveau höher/tiefer liegen. Tritt der Fall auf dass dieses Verhältnis kaputt geht, wird im schlimmsten Fall der gesamte Baum neu organisiert (Links-/Rechtsrotation). Vorteil hierbei: In einem ausgeglichenen AVL-Baum ist die Suchgeschwindigkeit immer O(n)=n*log2(n). Man hat halt nur beim Einfügen und Entfernen von Knoten mehr oder weniger Umorganisationsaufwand.

Hätte ich jetzt einen Link zu einer B-Baum Komponente gepostet, hättest du mich wohl komisch angeschaut . (Hab aber keinen...)
B-Bäume sind im Übrigen saumäßig ekelhat zu coden. Die größten Schwierigkeiten bereitet das Löschen von Werten, da man zum Teil iterativ und zum Teil rekursiv im schlimmsten Fall den gesamten Baum komplett neu organisieren muss. Das ist der Tradeoff für die Auslagerbarkeit .

Gruss,
Fabian