Auf der Suche nach einer festplattenbasierten B+-Baumimplementierung in C++ oder C [closed]

Lesezeit: 6 Minuten

Benutzer-Avatar
Laurynas Biveinis

Ich suche nach einer leichten Open-Source-Paging-B+-Baumimplementierung, die eine Festplattendatei zum Speichern des Baums verwendet.

Bisher habe ich nur gefunden speicherbasierte Implementierungenoder etwas das hat eine Abhängigkeit von QT (?!) Und lässt sich nicht einmal kompilieren.

Modernes C++ wird bevorzugt, aber C tut es auch.

Ich ziehe es vor, eine vollständig integrierbare DBMS-Lösung zu vermeiden, weil: 1) für meine Bedürfnisse ein Bare-Bone-Index ausreicht, der die einfachstmögliche Organisation von Festplattendateien verwenden kann, keine Notwendigkeit für Parallelität, Atomarität und alles andere. 2) Ich verwende dies, um meinen eigenen Index zu prototypisieren, und werde höchstwahrscheinlich einige der Algorithmen und das Speicherlayout ändern. Das möchte ich mit möglichst wenig Aufwand erreichen. Es wird kein Produktionscode sein.

  • Haben Sie eine Implementierung gefunden. Weil ich die gleichen Bedürfnisse habe wie du. Außerdem kann ich vorhandene DBMS-Lösungen aufgrund von Abhängigkeiten nicht verwenden.

    – Jannat Arora

    16. Februar 2013 um 20:48 Uhr

  • @JannatArora, am Ende habe ich meinen eigenen (unvollständigen; nur Einfügungen und Abfragen) B + -Baum oben geschrieben libspatialindex.github.com Disk-I/O-Routinen

    – Laurynas Biveinis

    17. Februar 2013 um 9:16 Uhr

Benutzer-Avatar
Vijay Mathew

http://people.csail.mit.edu/jaffer/WB.

Sie können auch die Wiederverwendung der B-Tree-Implementierungen aus einer integrierbaren Open-Source-Datenbank in Betracht ziehen. (BDB, SQLite etc)

  • @kastauyra Nehmen Sie einfach die B-Tree-Implementierung, nicht das gesamte DBMS

    – Vijay Mathew

    12. November 2009 um 9:03 Uhr

  • Möglich, aber als ich mich das letzte Mal damit befasst habe, ist es ziemlich chaotisch, den Index aus dem gesamten DBMS herauszureißen, einfach zu viele Abhängigkeiten.

    – Laurynas Biveinis

    12. November 2009 um 9:08 Uhr

  • Welche B-Tree-Implementierungen können also leicht aus diesen Datenbanken entnommen werden? Ich habe aktiv gesucht und gefunden keiner.

    – Joe Seelenbringer

    13. Dezember 2009 um 19:40 Uhr

  • @Joe Soul-bringer Sehen Sie sich für SQLite die Schnittstelle in btree.h und ihre Implementierung in btree.c an.

    – Vijay Mathew

    14. Dezember 2009 um 5:11 Uhr

  • @JoeSoul-bringer Haben Sie B + -Baumimplementierungen für die oben genannten Anforderungen gefunden?

    – Jannat Arora

    16. Februar 2013 um 21:50 Uhr

Meine eigene Implementierung ist unter http://www.die-schoens.de/prg Lizenz ist Apache. Es ist festplattenbasiert, bildet auf gemeinsam genutzten Speicher ab, wo es auch Sperren durchführen kann (dh Mehrbenutzer), Dateiformat schützt vor Abstürzen usw. All dies kann einfach abgeschaltet werden (Kompilieren oder Laufzeit, wenn Sie möchten). Bare Bone wäre also fast ANSI-C, im Grunde genommen im eigenen Speicher zwischenspeichern und überhaupt nicht sperren. Testprogramm ist enthalten. Derzeit befasst es sich nur mit Feldern mit fester Größe, aber ich arbeite daran …

Ich unterstütze den Vorschlag für Berkeley DB. Ich habe es verwendet, bevor es von Oracle gekauft wurde. Es ist keine vollständige relationale Datenbank, sondern speichert nur Schlüssel-Wert-Paare. Wir sind darauf umgestiegen, nachdem wir unsere eigene Paging-B-Tree-Implementierung geschrieben hatten. Es war eine gute Lernerfahrung, aber wir fügten weitere Funktionen hinzu, bis es nur noch eine (schlecht) implementierte Version von BDB war.

Wenn Sie es selbst tun möchten, finden Sie hier einen Überblick über das, was wir getan haben. Wir haben mmap verwendet, um Seiten in den Speicher abzubilden. Die Struktur jeder Seite war indexbasiert, sodass Sie mit der Seitenstartadresse auf jedes Element auf der Seite zugreifen konnten. Dann haben wir Seiten nach Bedarf gemappt und nicht gemappt. Wir indizierten Textdateien mit mehreren GB, als 1 GB Hauptspeicher als viel angesehen wurde.

Benutzer-Avatar
Anthony Lambert

C-Tree Plus von Faircom ist seit über 20 Jahren im Handel erhältlich. Arbeite nicht für sie etc… FairCom

Es gibt auch Berkley DB das von Oracle gekauft wurde, aber immer noch kostenlos von ihrer Website ist.

Ich bin mir ziemlich sicher, dass es nicht die Lösung ist, die Sie suchen, aber warum speichern Sie den Baum nicht selbst in einer Datei? Alles, was Sie brauchen, ist ein Ansatz für die Serialisierung und ein if/ofstream.

Grundsätzlich könnten Sie es so serialisieren: Gehen Sie zu root, schreiben Sie ‘0’ in Ihre Datei, einen Teiler wie ‘|’, die Anzahl der Elemente in root und dann alle root-Elemente. Wiederholen Sie dies mit „1“ für Ebene 1 und so weiter. Solange Sie die Ebene nicht ändern, behalten Sie den Ebenenindex bei, leere Blätter könnten wie 2|0 aussehen.

  • Ich möchte den Baum nicht in einem Speicher erstellen und ihn dann serialisieren. Ich möchte den Baum auf der Festplatte erstellen und zu einem bestimmten Zeitpunkt nur eine Teilmenge seiner Knoten im Speicher haben.

    – Laurynas Biveinis

    12. November 2009 um 8:48 Uhr

  • Sie suchen dann nach einem Paging eines B-Baums. Vielleicht kannst du das in deiner Frage verdeutlichen?

    – DaClown

    12. November 2009 um 10:13 Uhr

  • Es ist das erste Mal, dass ich höre, dass es als “Paging”-Baum betrachtet wird, aber bitte schön.

    – Laurynas Biveinis

    12. November 2009 um 10:50 Uhr

  • Es ist kein Paging-Baum. Was Sie haben, ist eine Datenstruktur, von der Sie eine Teilmenge im Speicher verarbeiten möchten, aber die gesamte Struktur auf der Festplatte gespeichert haben. Das Laden von Teilmengen von Daten, die größer sind als Ihr Arbeitsspeicher, wird als Paging bezeichnet.

    – DaClown

    12. November 2009 um 14:53 Uhr

Benutzer-Avatar
Jackson

Sie könnten sich Berkeley DB ansehen, das von Oracle unterstützt wird, aber es ist Open Source und kann gefunden werden hier.

  • Ich möchte den Baum nicht in einem Speicher erstellen und ihn dann serialisieren. Ich möchte den Baum auf der Festplatte erstellen und zu einem bestimmten Zeitpunkt nur eine Teilmenge seiner Knoten im Speicher haben.

    – Laurynas Biveinis

    12. November 2009 um 8:48 Uhr

  • Sie suchen dann nach einem Paging eines B-Baums. Vielleicht kannst du das in deiner Frage verdeutlichen?

    – DaClown

    12. November 2009 um 10:13 Uhr

  • Es ist das erste Mal, dass ich höre, dass es als “Paging”-Baum betrachtet wird, aber bitte schön.

    – Laurynas Biveinis

    12. November 2009 um 10:50 Uhr

  • Es ist kein Paging-Baum. Was Sie haben, ist eine Datenstruktur, von der Sie eine Teilmenge im Speicher verarbeiten möchten, aber die gesamte Struktur auf der Festplatte gespeichert haben. Das Laden von Teilmengen von Daten, die größer sind als Ihr Arbeitsspeicher, wird als Paging bezeichnet.

    – DaClown

    12. November 2009 um 14:53 Uhr

Benutzer-Avatar
Peter Ritter

RogueWave, das Softwareunternehmen, hat eine schöne Implementierung von BTreeOnDisk als Teil ihres Tools++-Produkts. Ich benutze es seit Ende der 90er Jahre. Das Schöne daran ist, dass Sie mehrere Bäume in einer Datei haben können. Sie benötigen jedoch eine kommerzielle Lizenz.

In ihrem Code beziehen sie sich auf ein Buch von einem Typen namens “Ammeraal” (siehe http://home.planet.nl/~ammeraal/algds.html , Ammeraal, L. (1996) Algorithmen und Datenstrukturen in C++). Er scheint eine Implementierung eines BTree auf der Festplatte zu haben, und der Quellcode scheint online zugänglich zu sein. Ich habe es aber nie benutzt.

Ich arbeite derzeit an Projekten, für die ich den Quellcode verteilen möchte, also muss ich einen Open-Source-Ersatz für die Rogue Wave-Klassen finden. Leider möchte ich mich nicht auf GPL-Lizenzen verlassen, sonst wäre eine Lösung einfach die Verwendung von ‘libdb’ oder Äquivalent. Ich brauche eine Lizenz vom Typ BSD und konnte lange Zeit nichts Passendes finden. Aber ich werde mir einige der Links in früheren Beiträgen ansehen.

1362960cookie-checkAuf der Suche nach einer festplattenbasierten B+-Baumimplementierung in C++ oder C [closed]

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy