Ich hab mir jetzt selber auch noch mal den Spaß gemacht und drei verschiedene Varianten gegeneinander getestet:
1. Rot-Schwarz-Baum aus der
FCL-STL
2. alzaimars
Skiplist (habe die maximale Tiefe allerdings von 8 auf 20 erhöht)
3. mein eigener B+-Baum
Ergebnis eines Testlaufs (alle Zeiten in ms):
B+-Baum:
B+ 1000000 Inserts: 472
B+ 1000000 Locates: 303
B+ 500000 Removes: 285
B+ 500000 Reinserts: 311
Skiplist:
SL 1000000 Inserts: 721
SL 1000000 Locates: 223
SL 500000 Removes: 322
SL 500000 Reinserts: 399
Rot-Schwarz-Baum:
RB 1000000 Inserts: 1337
RB 1000000 Locates: 859
RB 500000 Removes: 1243
RB 500000 Reinserts: 634
Die Werte schwanken natürlich etwas von einem Durchlauf auf den anderen, aber so ungefähr passt das.
Die Skiplist hat mich echt überrascht. Vor allem, wenn man bedenkt, dass die
Unit nur 300 Zeilen lang ist, während der B+-Baum es auf über 1100 Zeilen bringt (wobei die Skiplist allerdings auch weniger Features hat). Wenn man an die Skiplist noch die gleiche Speicherverwaltung dranbasteln würde, von der der B+-Baum aktuell profitiert, dann könnte man vermutlich die Insert-Zeiten und den Speicherverbrauch auch noch senken – denn letzterer ist mit über 300 MB recht happig im Vergleich zu ca. 100 MB beim B+-Baum. Der Rot-Schwarz-Baum bringt es ebenfalls auf über 300 MB und gibt den Speicher zudem nicht vollständig wieder frei, außerdem ist er, wie man sieht, bei der Geschwindigkeit weit abgeschlagen.
Trotz des guten Abschneidens der Skiplist kann man aber als Fazit sagen, dass B+-Bäume durchaus gut als
RAM-interne Datenstruktur geeignet sind.
Bei der Skiplist muss man natürlich außerdem noch berücksichtigen, dass sie propabilistisch arbeitet – bei so großen Anzahlen von Elementen kann sie damit natürlich alle ihre Vorteile ausspielen. Je kleiner die Anzahl, desto größer wäre aber die Wahrscheinlichkeit, dass ihre reale Laufzeit sich in Richtung der Worst-Case-Laufzeit verschiebt.