Wenn Du sehr viele kleine Fragmente hast, ist der Overhead vielleicht relativ gesehen zu groß. Ich würde nicht immer und überall Klassen verwenden, die guten alten Arrays tun es in vielen Fällen auch: Und die haben fast kein Overhead.
Ich habe als Knotenspeicher nämlich ein Array verwendet. Bei mir sind die Seiten konstant 8k groß, bzw. entsprechen der 'System Page Size', sodaß ich eine Klasse habe, die exakt diese Pagegröße liest und schreibt. Im Umkehrschluss ergibt sich daraus -abzüglich einiger Bytes for Bookkeeping- ca. 8160 Bytes Nutzdaten pro B+-Knoten (bei 8k System Page größe). Je nach länge des Schlüssels passen dann eben mehr oder weniger Daten in das Array. rein.
Ich verwende für die Navigationsknoten Records und darin sind die Schlüssel und die Kinder in Arrays mit fester Größe gespeichert. Bei mir haben sich Knotengrade von 16 bis 32 als am schnellsten erwiesen. Wie ich schon schrieb, arbeitet mein Baum nur im
RAM, Paging auf die Festplatte usw. ist nicht im Spiel.
Ich weiss nicht, ob wir über exakt das gleiche Modell reden, fällt mir gerade ein: Ich habe B-Bäume umgesetzt, keine B+ Bäume. Trotzdem könnte das als Denkanstoß reichen, um den Speicherverbrauch zu optimieren.
Auch ich habe im Eingangspost ein bisschen vereinfacht. Was ich da habe, ist nicht ganz das, was man im Internet als B+-Baum findet. Erstens handelt es sich um einen (a,b)-Baum, was aber fast das gleiche zu sein scheint wie ein B+-Baum, nur ein bisschen allgemeiner (Knotengrade von a bis b, statt von b bis 2b). Zweitens habe ich mich stark daran orientiert, wie es in unserer Algorithmen-Vorlesung gezeigt wurde: „Unter dem Baum“ befindet sich sozusagen eine verkettete Liste. Bei den B+-Bäumen, die man im Internet findet, werden meistens die Daten in die untersten Navigationsknoten geschrieben und diese Knoten dann miteinander in einer Liste verbunden – also mehrere Datensätze pro Knoten. Bei mir ist es hingegen so, dass die unterste Navigationsschicht die Daten nicht selbst enthält, sondern auf spezielle Knoten (Blätter) zeigt, die die Daten enthalten – ein Blatt-Knoten pro
Datensatz. Und das scheint das Problem zu sein, denn dadurch entstehen in meinem Benchmark eine Million 48-Byte-Blöcke.
(Ich weiß nicht, ob das ein grundlegender Unterschied zwischen (a,b)-Bäumen und B+-Bäumen ist, oder ob unser Prof das einfach nur anders gemacht hat. Im Internet findet man zu (a,b)-Bäumen sehr wenig Informationen)
Ursprünglich stand das schon länger auf meiner To-Do-Liste, diesen untersten Layer loszuwerden, allerdings ist mir dann aufgefallen, dass das so einen entscheidenden Vorteil hat: Wenn man sich einen Zeiger (Iterator) auf einen Datensatz holt, bleibt der – solange der Datensatz nicht gelöscht wird, natürlich – für immer gültig, egal was sich am Baum verändert. Man kann beliebig Knoten einfügen oder löschen, der Zeiger zeigt trotzdem noch auf den richtigen Knoten. Das ist bei der speichereffizienteren Variante nicht gegeben: Es könnte sein, dass der zugehörige Knoten in der Zwischenzeit aufgespalten oder mit einem anderen Knoten zusammengelegt wurde, wodurch er nicht mehr an der richtigen Stelle im Speicher liegt.
Für meinen Anwendungsfall ist diese Persistenz sogar tatsächlich ein Vorteil. Deshalb wollte ich erst mal in Kauf nehmen, dass meine Lösung nicht die aller speichereffizienteste ist. Dass das allerdings zu so viel Fragmentierung führt, hätte ich nicht erwartet.
Ich werde jetzt wahrscheinlich versuchen, mir nur für diese Records einen eigenen kleinen Speichermanager zu schreiben.
@Bernhard Geyer: Ich hatte mal testweise alle Debug-Informationen rausgenommen, das hat aber nichts verändert.