guardando Btrees en un archivo de disco y léelo

Question

Quiero guardar un Btree (no estoy seguro de uno binario) en un archivo de disco. y luego léelo a la memoria. algunos cruces de nivel pueden ser una buena forma para un Btree binario. pero si no es binario. Construyo el Btree desde el nodo hoja hasta el nodo raíz en la memoria. Creo que tengo que definir algunas estructuras en el archivo de disco y dar salida a los nodos de árbol. usando alguna etiqueta adicional para identificar un nodo en el archivo? cómo atravesar puede ser el problema clave aquí. No pude encontrar una buena manera de guardar los nodos y los punteros. y luego léelo. reconstruir el árbol en la memoria. alguna buena idea ?. muchas gracias.

Answer 1

Si realmente quiere hacer algo similar, sólo se puede asignar a cada nodo un identificador y guardar los nodos en ese formato:

[valor de nodo-id izquierda-nodo-id derecho del nodo-id]

y luego visite el árbol con una búsqueda amplia.

Cuando desee reconstruir el árbol, cree un id de mapa-> nodo y luego lea hacia atrás el archivo: entonces, cuando lea un registro, cree el nodo, regístrelo en el mapa y asigne el nodo derecho que busca los nodos del mapa.

Answer 2

Para cada nodo define alguna estructura de datos que mantendrá para ti la misma información que tiene el nodo y agrega a esa estructura un campo adicional que marcará para ti la compensación en el archivo para el próximo hijo. Y crea el campo superior de esa estructura en su tamaño real, ya que no sabes qué tipo de árbol estás buscando ahora. Ahora saltando sobre el archivo podrá reconstruir su árbol. Estoy seguro de que mi solución no es definitiva, pero espero que sea el mejor punto para ti.

Answer 3

Es posible que desee comprobar Protocol Buffers. Son compactos, binarios, extensibles, fáciles de leer y escribir, y están disponibles en C++, Java y Python (así como implementaciones de terceros en otros idiomas).

Puede definir un mensaje de búfer de protocolo para un nodo BTree, con desplazamientos de archivo para nodos secundarios, y simplemente serializarlo en el disco de la manera obvia.

Answer 4

La técnica habitual para B-Trees es garantizar que el tamaño de un nodo sea igual al tamaño de bloque del disco y mmap el archivo de disco. No especifica en qué lenguaje de programación está trabajando, por lo que puede ser tan simple como un molde en C, o algo más complicado como crear objetos de peso mosca para envolver un java.nio.IntBuffer. De cualquier manera, gran parte de la ventaja del B-tree es que no tienes que cargarlo todo de una vez, sino que puedes saltarte con bastante eficiencia.