Btrees in eine Datei speichern und lesen Sie es

Question

Ich möchte ein Btree (nicht sicher, ob eine binäre Eins) in einer Datei speichern. und lesen Sie es dann in den Speicher. einige Level-Reihenfolge Traversal kann eine gute Möglichkeit für eine binäre Btree. aber wenn es kein binäres ist. Ich baue das Btree vom leafnode zum rootnode im Speicher. Ich glaube, dass ich einige Strukturen in der Festplattendatei definieren und die Baumknoten ausgeben muss. Verwenden Sie ein zusätzliches Tag, um einen Knoten in der Datei zu identifizieren? wie Traversal kann das Schlüsselproblem hier sein. Ich konnte keinen guten Weg finden, die Knoten und die Zeiger zu speichern. und dann lesen Sie es. Rekonstruiere den Baum im Speicher. irgendwelche guten Ideen ?. vielen Dank.

Answer 1

Wenn Sie wirklich etwas Ähnliches tun möchten, können Sie an jedem Knoten eine ID zuweisen gerade und die Knoten in diesem Format speichern:

[Knoten-ID-Wert links-node-id rechten Knoten-id]

und besuchen Sie dann den Baum mit einer Breitensuche.

Wenn Sie wollen, um den Baum zu rekonstruieren, eine Karte id-> Knoten erstellen und lesen dann rückwärts die Datei: so, wenn Sie einen Datensatz zu lesen, erstellen Sie den Knoten, registrieren sie die Karte, um die linke zuweisen und rechter Knoten holt die Knoten von der Karte.

Answer 2

Für jeden Knoten definiert eine Datenstruktur, die für Sie die gleichen Informationen der Knoten halten und auf diese Struktur zusätzlichen Feld hinzufügen, die für Sie die Offset in der Datei für die nächsten Sohn markieren. Und machen Sie das oberste Feld dieser Struktur ihre tatsächliche Größe, da Sie nicht wissen, welche Art von Baum Sie jetzt suchen. Jetzt kannst du deinen Baum rekonstruieren, indem du über die Datei springst. Ich bin mir sicher, dass meine Lösung nicht endgültig ist, aber ich hoffe, es könnte der gute Star Point für dich sein.

Answer 3

Sie möchten vielleicht Protocol Buffers überprüfen. Sie sind kompakt, binär, erweiterbar, leicht zu lesen und zu schreiben und in C++, Java und Python (sowie Implementierungen von Drittanbietern in anderen Sprachen) verfügbar.

Sie können eine Protokollpuffer Nachricht für einen BTree Knoten, mit Datei-Offsets für untergeordnete Knoten, definieren und einfach auf die Festplatte in der offensichtlichen Weise serialisiert.

Answer 4

Die übliche Technik für die B-Trees ist, um sicherzustellen, dass die Größe eines Knotens auf die Blockgröße der Scheibe gleich ist, und die mmap Plattendatei. Sie geben nicht an, in welcher Programmiersprache Sie arbeiten, also könnte es so einfach wie eine Umwandlung in C sein, oder etwas komplizierteres wie zum Beispiel das Erstellen von flyweight Objekten zum Einschließen eines java.nio.IntBuffer. So oder so, ein großer Vorteil des B-Baums besteht darin, dass Sie ihn nicht alle auf einmal laden müssen, sondern ziemlich effizient herumspringen können.