C/C++: Wie man Daten in einer Datei in B-Baum speichert

Es scheint mir, dass eine Möglichkeit zum Speichern von Daten in einem B-Baum als Datei effizient mit C unter Verwendung einer Binärdatei mit einer Sequenz (Array) von Strukturen, wobei jede Struktur einen Knoten darstellt. Man kann somit die einzelnen Knoten mit einem Ansatz verbinden, der dem Erstellen von verknüpften Listen unter Verwendung von Arrays ähnlich ist. Aber das Problem, das sich aufstützt, wäre das Löschen eines Knotens, da das Löschen von nur wenigen Bytes in der Mitte einer riesigen Datei nicht möglich ist.C/C++: Wie man Daten in einer Datei in B-Baum speichert

Eine Möglichkeit zum Löschen könnte darin bestehen, "leere" Knoten zu verfolgen, bis eine Schwellenwertgrenze erreicht ist, und dann eine weitere Datei zu erstellen, die die leeren Knoten verwerfen soll. Aber das ist mühsam.

Gibt es einen besseren Ansatz aus Sicht der Einfachheit/Effizienz zum Löschen oder gar Darstellen eines B-Baums in einer Datei?

TIA, -Sviiya

Quelle

2010-02-02 user203405

Nur um klar zu sein, fragen Sie über B-Bäume oder Binärbäume. –

B-Bäume. Aber ich denke, für den Zweck, als Dateien zu speichern, wäre das Problem das gleiche? – user203405

BTW, C und C++ sind zwei verschiedene Sprachen. Wenn Sie Code schreiben, der für beide funktioniert, fügen Sie das C++ - Tag hinzu. –

ich eine sehr schnelle Suche gemacht und ausgegraben dieses: http://people.csail.mit.edu/jaffer/WB C Quelle: http://cvs.savannah.gnu.org/viewvc/wb/wb/c/ - es scheint, Datenbanken Disk-basierte B-Tree-Stil bieten - auch wenn Sie einen Blick auf „Aufnahme löschen .c "es schien zu implizieren, wenn man einen Knoten löscht, wird alles aus ihm herausgenommen - wenn das das richtige Verhalten ist, dann hört es sich nach etwas an, das helfen könnte?

Auch - B-Bäume werden oft in Dateisystemen verwendet - könnten Sie sich keinen Dateisystemcode ansehen?

Meine eigene Neigung ist die eines Dateisystems - wenn Sie einen B-Baum von fester Größe haben, wenn Sie einen Knoten "löschen", anstatt zu versuchen, den Verweis zu entfernen, setzen Sie einfach den Wert auf nichts in deinem Code. Führen Sie dann einen Bereinigungsthread aus, der überprüft, ob jemand die Datei zum Lesen geöffnet hat und ob alle Dateien die Datei blockieren und aufräumen.

Quelle

2010-02-02 19:32:36

Danke für die Referenz, Neunfinger. :) Muss sicherlich gelesen werden. Da die Löschung häufig sein kann, sollte die Berechnung effizient sein. Ich würde erwarten, dass einige dieser Operationen möglicherweise verzögert werden, aber ich müsste den Code lesen, um zu sehen, ob es eine bessere Option gibt. Ich beabsichtige auch, es später für ein Dateisystem zu verwenden, aber dann wäre die Implementierung anders, da die Größe konstant wäre. Das Design muss das berücksichtigen. – user203405

Hmm ich stimme zu. Dieser Code behauptet zu tun, was Sie brauchen, und ein flüchtiger Blick auf viewcvs legt nahe, dass es möglich ist - ohne sich hinzusetzen und Ihr Problem neu aufzubauen, obwohl es schwer zu sagen ist ... Ich denke, Dateisysteme "löschen" einfach Elemente, die sie löschen möchten Null-Element, aber ich könnte das falsch haben. Wie auch immer, wenn dies nicht beantwortet wird, bitte öffnen Sie die Frage erneut! –

Die Fragen beantwortet, was ich suchte, und ich habe bereits über Dateiabkürzung und damit das Problem des Löschens von Daten aus der Mitte wurde umgangen. Vielen Dank. :) – user203405

Sie können Berkley DB auch verwenden. Es funktioniert gut mit C-Programmen und implementiert B + Baum.

Quelle

2010-02-02 20:15:32 Jack

Ja, aber ich möchte meinen eigenen Code schreiben, um das echte Gefühl zu bekommen. :) – user203405

Zustimmen. Allein zu schreiben ist in Ordnung, um das echte Gefühl zu bekommen. BBD ist sehr anspruchsvolle Datenbank und bietet viele Funktionen, die normalen Code nicht würde. Im Falle eines tatsächlichen Produkteinsatzes würde ich BDB wählen. Das Rad neu zu erfinden wäre hier schwierig. – Jack

Zum Implementieren von B-Trees in einer Datei können Sie den Dateioffset anstelle von Zeigern verwenden. Außerdem können Sie einen "Dateispeicher-Manager" implementieren, sodass Sie gelöschte Elemente in der Datei erneut verwenden können.

Um die gelöschten Blöcke in einer B-Tree-Datei vollständig wiederherzustellen, müssen Sie den B-Tree in einer neuen Datei neu erstellen. Beachten Sie auch, dass die meisten Betriebssysteme keine Methoden zum Abschneiden von Dateien haben. Eine portable Methode zum Abschneiden einer Datei besteht darin, eine neue Datei zu schreiben und die alte zu zerstören.

Ein anderer Vorschlag ist, die Datei in B-Tree Partition und Daten (Element) Partition zu partitionieren. Eine B-Tree-Partition enthält die Seiten. Die Blattseiten enthalten Offsets für die Datenelemente. Die Datenpartition ist ein Abschnitt in der Datei, die Datenelemente enthält. Sie können am Ende mehr als eine Partition erstellen, und die Partitionen können verschachtelt sein.

Ich verbrachte viel Zeit damit, mit einem dateibasierten B-Tree zu spielen, bis ich aufgab und beschloss, ein Datenbankprogramm (oder Server) mit den Daten für mich arbeiten zu lassen.

Quelle

2010-02-03 00:36:14

Klingt interessant. Diese Übung von mir ist, etwas Exposition zu niedriger Kodierung zu bekommen. Ich bin hauptsächlich an Linux-basierten Systemen interessiert und unterstützt Dateikürzungen. :) – user203405

Die meisten Betriebssysteme * haben * Funktionen zum Abschneiden von Dateien. Unter Linux, BSDs, Windows können Sie die Dateilänge beliebig einstellen. –

C/C++: Wie man Daten in einer Datei in B-Baum speichert

Antwort

Verwandte Themen