Estructuras de datos más grandes que la memoria y cómo se manejan normalmente

Question

Digamos que tengo una estructura de datos basada en archivos, como un árbol B+.Tengo entendido que se espera que los datos se almacenen en el disco, pero el índice generalmente se carga en la memoria.¿Qué pasa si tienes un archivo tan grande que ni siquiera su índice cabe en la memoria?¿Cómo se suele manejar eso?En segundo lugar, dado que el índice es un árbol, no un conjunto lineal de datos, ¿cómo se suele distribuir en el disco?

Básicamente tengo curiosidad por saber cómo se hace en proyectos del mundo real (como Berkeley DB).Obviamente me interesan las grandes líneas.Espero tener una idea para tener algo de contexto cuando profundice en la sección B-Tree de mi libro de bases de datos (o refresque mi memoria de CS XYZ de hace años)

Answer 1

Los árboles B están destinados a sistemas basados ​​en páginas, donde un nodo determinado encaja en una página.Para encontrar una entrada en un árbol B, sólo es necesario cargar una página a la vez, para que pueda hacerlo.

Incluso actualizarlos no requiere que haya una gran cantidad de páginas en la memoria al mismo tiempo; me imagino que la operación más difícil es eliminar cuando se están reorganizando los nodos, pero si se implementa con cuidado, incluso eso podría hacerse con relativamente pocas páginas en memoria.

Answer 2

Es posible que desee echar un vistazo a SQLite . El código base es mucho menor que Berkeley DB, es de dominio público, que está muy claramente organizada y comentó, y el fuera de la fuente de documentación es excelente. Me enseñó mucho sobre btree en el mundo real

Answer 3

Para responder a la primera pregunta, una estructura de datos que es demasiado grande para caber en la memoria por lo general se divide en "páginas", por lo general todas las páginas son del mismo tamaño y cada página contiene parte de la estructura de datos, utilizar los datos que carga y descarga páginas.

Otra opción común (que no se utiliza comúnmente en RDBMS, pero es común con cosas como archivos XML y los medios de comunicación) es el streaming, donde se procesan los datos con el fin de cargar la siguiente sección y desechando la anterior.

Y eso también responde a su segunda pregunta, si se utiliza la paginación de la estructura de archivos es una secuencia de páginas del mismo tamaño, si se utiliza el streaming de los datos deben ser dispuestas en el orden que va a utilizarlo (en el caso de un árbol que es probable que va a ser DFS o BFS fin, dependiendo de su aplicación).