C/C++:Cómo almacenar datos en un archivo en el árbol B

Question

Me parece que una forma de almacenar datos en un árbol B como un archivo se puede hacer de manera eficiente con C usando un archivo binario con una secuencia (matriz) de estructuras, donde cada estructura representa un nodo.De este modo, se pueden conectar los nodos individuales con un enfoque similar a la creación de listas enlazadas utilizando matrices.Pero entonces el problema que surge sería la eliminación de un nodo, ya que no es posible borrar solo unos pocos bytes en el medio de un archivo enorme.

Una forma de eliminar podría ser realizar un seguimiento de los nodos "vacíos" hasta que se alcance un umbral y luego crear otro archivo que descarte los nodos vacíos.Pero esto es tedioso.

¿Existe un mejor enfoque desde el punto de vista de simplicidad/eficiencia para eliminar o incluso representar un árbol B en un archivo?

Tia, -sviiya

Answer 1

Hice una búsqueda muy rápida y desenterré esto: http://people.csail.mit.edu/jaffer/WB fuente C: http://cvs.savannah.gnu.org/viewvc/wb/wb/c/ - parece ofrecer bases de datos de estilo árbol B basadas en disco - aunque al echar un vistazo a "delete.c" parecía implicar que si eliminas un nodo, todo lo que hay debajo se eliminará - si ese es el comportamiento correcto, entonces suena ¿Te gusta algo que pueda ayudar?

Además, los árboles B se utilizan a menudo en sistemas de archivos. ¿No podrías echar un vistazo al código del sistema de archivos?

Mi propia inclinación es la de un sistema de archivos: si tiene un árbol B de tamaño fijo, siempre que "borre" un nodo en lugar de intentar eliminar la referencia, simplemente establezca el valor en lo que no signifique nada en su código.Luego, ejecute un hilo de limpieza que verifique si alguien tiene el archivo abierto para leerlo y, si todo está en silencio, bloquea el archivo y lo ordena.

Answer 2

Para la ejecución de los árboles B en un archivo, puede utilizar la compensación en lugar de punteros de archivos. Además, se puede implementar un "gestor de memoria de archivo", para que pueda volver a utilizar elementos del archivo borrado.

Con el fin de recuperar totalmente los bloques eliminados en un archivo de árbol B, que tendrá que volver a crear el árbol B en un nuevo archivo. Asimismo, recuerda la mayoría de los sistemas operativos no tienen métodos para truncar los archivos. Un método portátil para truncar un archivo es escribir un nuevo archivo y destruir el viejo.

Otra sugerencia es dividir el archivo en la partición de la partición y los datos de árbol B (punto). Una partición de árbol B contendrá las páginas. Las páginas de hoja contendrán las compensaciones a los elementos de datos. La partición de datos será una sección en el archivo que contiene los elementos de datos. Usted puede terminar la creación de más de uno de cada partición y las particiones pueden intercalarse.

pasé mucho tiempo jugando con un archivo basado B-Tree, hasta que me di por vencido y decidió dejar que un programa de base de datos (o servidor) manejar los datos para mí.

Answer 3

Puede utilizar Berkeley DB también. Funciona bien con los programas en C y aperos de árbol B +.