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
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.
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
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
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.
13629600cookie-checkAuf der Suche nach einer festplattenbasierten B+-Baumimplementierung in C++ oder C [closed]yes
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