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 eficientemente con C usando un archivo binario con una secuencia (matriz) de estructuras, con cada estructura representando un nodo. Por lo tanto, uno puede conectar los nodos individuales con un enfoque que será similar a crear listas vinculadas utilizando matrices. Pero entonces el problema que apuntalaría sería la eliminación de un nodo, ya que borrar solo unos pocos bytes en el medio en un archivo enorme no es posible.

Una forma de eliminar podría ser realizar un seguimiento de los nodos 'vacíos' hasta que se alcance un límite de corte 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 en C: http://cvs.savannah.gnu.org/viewvc/wb/wb/c/ - parece ofrecer bases de datos tipo árbol B basados ​​en disco - a pesar de echar un vistazo a "eliminar .c "parecía implicar que si eliminas un nodo, todo lo que está abajo se eliminaría; si ese es el comportamiento correcto, entonces parece que podría ser útil".

Además, los B-trees se utilizan a menudo en sistemas de archivos. ¿No podría echar un vistazo a algún código del sistema de archivos?

Mi propia inclinación es la de un sistema de archivos: si tiene un B-tree de tamaño fijo, cada vez que "elimina" un nodo en lugar de intentar eliminar la referencia, simplemente establezca el valor en lo que signifique nada en tu código Luego, ejecute un hilo de limpieza que verifique si alguien tiene el archivo abierto para leer y si todo está silencioso bloquea el archivo y se ordena.

Answer 2

También puede usar Berkley DB. Funciona bien con programas C e implementa árbol B +.

Answer 3

Para implementar B-Trees en un archivo, puede utilizar el desplazamiento de archivo en lugar de punteros. Además, puede implementar un "administrador de memoria de archivos" para que pueda volver a utilizar los elementos eliminados en el archivo.

Para recuperar completamente los bloques eliminados en un archivo B-Tree, tendrá que volver a crear el B-Tree en un nuevo archivo. Recuerde también que la mayoría de los sistemas operativos no tienen métodos para truncar archivos. Un método portátil para truncar un archivo es escribir un nuevo archivo y destruir el anterior.

Otra sugerencia es dividir el archivo en partición B-Tree y partición de datos (elemento). Una partición B-Tree contendrá las páginas. Las páginas de hoja contendrán desplazamientos a los elementos de datos. La partición de datos será una sección en el archivo que contiene elementos de datos. Puede terminar creando más de una de cada partición y las particiones pueden estar intercaladas.

Pasé mucho tiempo jugando con un B-Tree basado en archivos, hasta que me di por vencido y decidí dejar que un programa de base de datos (o servidor) manejara los datos por mí.