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