Seufz.
Der Speicherbedarf ist linear. Ich hätte zwar mit 147 MB gerechnet (weil 7 + (77-7)*2 = 147) aber egal. Vielleicht nimmst Du mich auch nicht ernst und hast dir die Zahlen zurechtgerechnet (und dabei einen Fehler gemacht?).
Die Zahlen stammen so 1:1 aus dem Systemmonitor.
Wäre vielleicht auch was für die CodeLib, wenn ich den Code jetzt noch etwas aufräume...
Ketzerische Frage: Welchen Wert, außer dem Lehrinhalt, hätte eine B+-Baum-Implementierung, die nicht mit einem externen Speicher arbeitet (oder kann deine Version das jetzt)? B-Bäume wurde ja gerade dafür erfunden. Eine schnelle sortierte Liste bekommt man mit einer Skiplist oder einem Binärbaum hin (Die müssten sogar schneller sein). Eine im Suchen sehr schnelle unsortierte Liste mit einem Dictionary, oder irre ich mich?
Ich meinte eigentlich die Speicherverwaltung. Denn das kann man ja sicher mal wieder gebrauchen. Den Baum werde ich aber möglicherweise auch als Open Source veröffentlichen.
B+-Bäume machen auch im Arbeitsspeicher Sinn, weil sie deutlich cachefreundlicher sind als etwa Rot-Schwarz-Bäume. Falls dich Zahlen interessieren, unser Übungsleiter hatte da mal die Performance von Rot-Schwarz-Bäumen (aus der STL) und B+-Bäumen verschiedener Größen verglichen:
http://panthema.net/2007/stx-btree/speedtest/ (lustigerweise bin ich erst über einen unabhängigen Link auf StackOverflow wieder darauf gestoßen, dann fiel mir wieder ein, dass das in einer Vorlesung auch mal erwähnt wurde...)
Eine Hashmap nützt mir nichts, weil ich wirklich eine sortierte Liste brauche.
Eine Skiplist habe ich nicht ausprobiert, aber soweit ich weiß nähert diese sich auch letztlich propabilistisch an die Struktur eines Baumes an. Ob das jetzt nun schneller ist oder nicht, müsste man testen. Allerdings ist zu bedenken, dass eine Skiplist auch wieder eine verkettete Liste ist, das bedeutet tendenziell schlechte Cache-Effizienz und wieder Fragmentierungs-Probleme. Ich hätte so oder so beides neu implementieren müssen, und mit den Bäumen kannte ich mich besser aus
.