Effizienz des Speichermanagers

[Namenloser]

Zitat von Patito:

Dein B+-Tree schlägt sich offensichtlich ganz gut. Der RBTree aus der FPC-STL ist aber wohl nicht gerade der beste.
Interessant wäre noch, wenn Du das ganze noch mit dem TAVLTree aus der FCL vergleichst.

Der scheint wirklich ziemlich schnell zu sein, zumindest wenn er erst mal einen Pool an TreeNodes angelegt hat, die er dann recyclen kann:

Code:

B+ 1000000 Inserts: 447
B+ 1000000 Locates: 280
B+ 500000 Removes: 201
B+ 500000 Reinserts: 241

SL 1000000 Inserts: 713
SL 1000000 Locates: 212
SL 500000 Removes: 324
SL 500000 Reinserts: 347

AVL 1000000 Inserts: 623
AVL 1000000 Locates: 259
AVL 500000 Removes: 73
AVL 500000 Reinserts: 91

RB 1000000 Inserts: 1345
RB 1000000 Locates: 849
RB 500000 Removes: 1050
RB 500000 Reinserts: 721

Falls die Zahlen etwas anders sind: Ich hab in meinem Benchmark-Code etwas Unsinn gefunden und ausgebessert... war halt schnell mit Copy & Paste-Programmierung zusammengestrickt . Allerdings wurden trotzdem alle unter den gleichen Umständen getestet.

Das Ergebnis finde ich interessant, weil man, wenn man bei Google nach Empfehlungen für balancierte Bäume sucht, eigentlich immer liest, dass AVL-Bäume bei häufigen Einfüge- und Löschoperationen wegen häufigem Rebalancing nicht so gut geeignet seien, insbesondere im Vergleich zu Rot-Schwarz-Bäumen.

Mich wundert es allerdings, dass die Removes hier schneller zu gehen scheinen als die Locates. Vielleicht sollte langsam mal ein repräsentativerer Test her...