B-Tree-Komponente gesucht

[Bernhard Geyer]

Kennt von euch jemand eine gute B-Tree-Komponente:

- Geeignet auch für große Datenmengen (5.000.000 Datensätze)
- Wenn möglich auch Unicode-Enabled
- Sourcen vorhanden

[Bitworm]

Den Virtualtree. Der ist schnell, kann Unicode, komfortabel und durch sein Konzept sehr leicht an eigene Bedürfnisse anpassbar.

[Bernhard Geyer]

Mike's TreeView ist kein B-Tree, sondern "nur" ein Tree-Komponente zur visualisierung.
Aber ich hab schon was gefunden, was schnell und halbwegs vernünftig Implementiert ist.

[PRehders]

Zitat:

Zitat von Bernhard Geyer

Aber ich hab schon was gefunden, was schnell und halbwegs vernünftig Implementiert ist.

Lässt du uns an deiner Erkenntnis teilhaben?

Vielen Dank :wink:

Peter

[Robert_G]

Welchen sinn macht ein B-Tree als Komponente? :gruebel:
Wäre er dann nicht so allgemein gehalten, dass dir Boxing/Unboxing und TypCasting sämtliche Geschwindigkeitsvorteile kaputtmachen?

[Bernhard Geyer]

Zitat:

Zitat von PRehders

Lässt du uns an deiner Erkenntnis teilhaben?

B-Tree

Zitat:

Zitat von Robert_G

Welchen sinn macht ein B-Tree als Komponente? Grübelnd...

Sehr schnelle Suche/Einfügen in einer sortierten Datenbasis.

Zitat:

Zitat von Robert_G

Wäre er dann nicht so allgemein gehalten, dass dir Boxing/Unboxing und TypCasting sämtliche Geschwindigkeitsvorteile kaputtmachen?

Bei guter Implementierung - Nein. Nicht umsonst verwenden z. B. DBMS wie MS-SQL B-Trees für ihren Primärschlüssel

[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 :D. (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 :stupid:.

Gruss,
Fabian

[negaH]

Zitat:

Vorteil von B-Bäumen: Teilweise auf Langzeitdatenträger auslagerbar, und dadurch ein guter Kompromiss zwischen Speicheraufwand und Geschwindigkeit.

Nicht nur das. Weil die Bäume ihre Childs in der gleichen Speicherseite verwalten sind die heutigen CPU's mit Cache ideal um sehr schnelle B-Tree's zu implementieren. Denn nicht nur die math. Komplexität der einzelnen Operationen entscheidet über die reale Performance sondern auch Mikrooperationen zum Zugriff und zur Maipulierung der Daten. Da B-Tree's im allgmeinen nicht über Zeiger-Arithmetik sondern mit indizierten Arrays[] arbeiten sind sie hier klar im Vorteil gegenüber den AVL-/RB-Tree's. Allerdings nutzt man B-Tree's tatsächlich vorwiegend für ReadOnly Datenmengen. Das Einfügen neuer "Nodes" in einen B-Tree kann unter Umständen das Umkopieren großer Datenmengen mit sich führen.

Ein anderer ganz wesentlicher Vorteil der B-Tree's ist deren Möglichkeit ge-packt/komprimiert zu werden. In B-Tree's ist es möglich das ganze Child-Baume mit identischer Struktur zusammengefasst werden können. Dies geht mit B-Tree's einfacher als mit den anderen Trees.

Gruß Hagen