fuente - arbol n ario c++

Buscando una implementación de árbol B+basada en disco en C++ o C

Question

Estoy buscando una implementación de árbol ligero B + paginación de código abierto que use un archivo de disco para almacenar el árbol.

Hasta ahora he encontrado solo implementaciones basadas en memoria , o something que tiene dependencia en QT (?!) Y ni siquiera compila.

Se prefiere C ++ moderno, pero C también lo hará.

Prefiero evitar la solución DBMS integrable, porque: 1) para mis necesidades, es suficiente con un índice de huesos desnudos que pueda usar la organización de archivos en disco más simple, sin necesidad de concurrencia, atomicidad y todo lo demás. 2) Estoy usando esto para crear un prototipo de mi propio índice, y lo más probable es que cambie algunos de los algoritmos y el diseño de almacenamiento. Quiero hacer eso con un mínimo de esfuerzo. No va a ser código de producción.

Answer 1

Apoyo la sugerencia para Berkeley DB. Lo usé antes de que fuera comprado por Oracle. No es una base de datos relacional completa, solo almacena los pares clave-valor. Cambiamos a eso después de escribir nuestra propia implementación de B-Tree de paginación. Fue una buena experiencia de aprendizaje, pero seguimos agregando funciones hasta que se convirtió en una versión (mal) implementada de BDB.

Si quiere hacerlo usted mismo, aquí hay un resumen de lo que hicimos. Usamos mmap para mapear páginas en la memoria. La estructura de cada página estaba basada en un índice, por lo que con la dirección de inicio de página se podía acceder a cualquier elemento en la página. Luego asignamos y eliminamos la asignación de las páginas según sea necesario. Estábamos indexando archivos de texto de varios GB, cuando se consideraba mucho un GB de memoria principal.

Answer 2

El C-Tree Plus de Faircom ha estado disponible comercialmente por más de 20 años. No trabaje para ellos, etc ... FairCom

También está Berkley DB, que fue comprada por Oracle pero aún está libre de su sitio.

Answer 3

Estoy bastante seguro de que no es la solución que estás buscando, pero ¿por qué no almacenas el árbol en un archivo tú mismo? Todo lo que necesita es un enfoque para la serialización y un if / ofstream.

Básicamente, podría serializarlo así: vaya a la raíz, escriba ''0'' en su archivo, un divisor como ''|'', la cantidad de elementos en la raíz y luego todos los elementos raíz. Repita con ''1'' para el nivel 1 y así sucesivamente. Siempre y cuando no cambie el nivel, mantenga el índice de nivel, las hojas vacías podrían verse como 2 | 0.

Answer 4

Mi propia implementación está bajo http://www.die-schoens.de/prg licencia es Apache. Está basado en disco, se asigna a la memoria compartida donde también puede bloquear (es decir, multiusuario), el formato de archivo protege contra el bloqueo, etc. Todo lo anterior se puede desconectar fácilmente (compilar o ejecutar si lo desea). Así que el hueso desnudo sería casi ANSI-C, básicamente almacenado en memoria caché y no bloqueado en absoluto. El programa de prueba está incluido. Actualmente, solo se trata de campos de tamaño fijo, pero estoy trabajando en eso ...

Answer 5

Puede ver Berkeley DB, es compatible con Oracle, pero es de código abierto y se puede encontrar here .

Answer 6

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

También puede considerar volver a utilizar las implementaciones de B-Tree desde una base de datos incrustable de código abierto. ( BDB , SQLite , etc.)

Answer 7

RogueWave, la compañía de software, tiene una buena implementación de BTreeOnDisk como parte de su producto Tools ++. Lo he usado desde finales de los 90. Lo bueno de esto es que puedes tener múltiples árboles en un solo archivo. Pero necesitas una licencia comercial.

En su código hacen referencia a un libro de un tipo llamado ''Ammeraal'' (ver http://home.planet.nl/~ammeraal/algds.html , Ammeraal, L. (1996) Algoritmos y estructuras de datos en C ++ ) Parece tener una versión de un BTree en el disco, y el código fuente parece ser accesible en línea. Nunca lo he usado sin embargo.

Actualmente trabajo en proyectos para los cuales me gustaría distribuir el código fuente, así que necesito encontrar un reemplazo de fuente abierta para las clases de Rogue Wave. Lamentablemente, no quiero confiar en las licencias de tipo GPL, de lo contrario, una solución sería simplemente usar ''libdb'' o equivalente. Necesito una licencia de tipo BSD, y durante mucho tiempo no pude encontrar nada adecuado. Pero echaré un vistazo a algunos de los enlaces en publicaciones anteriores.