¿Qué es una página de árbol B

Question

Creo que sé lo que es un árbol B pero, ¿qué es una página de árbol B?

Answer 1

B-trees son una estructura de datos común para colecciones muy grandes, como las encontradas en las bases de datos. A menudo son demasiado grandes para guardarlos en la memoria a la vez, por lo que se almacenan en un archivo en el disco, y solo las porciones necesarias para la operación actual se leen en la memoria.

Una pieza de datos que se almacena en el disco (y se lee en la memoria) como una unidad se denomina página. Es típico que un árbol B almacene el número de registros en un solo nodo que hace que el tamaño del nodo sea igual al tamaño natural de la página del sistema de archivos. De esta forma, los accesos al disco pueden optimizarse.

Por ejemplo, si el sistema de archivos opera naturalmente en bloques de datos de 16 kb, y si el tamaño de los registros en el árbol B es de 500 b (incluyendo los enlaces al siguiente nivel de nodos), entonces 32 registros podrían almacenarse en el nodo, haciendo que el tamaño del nodo sea igual al tamaño de la página y permitiendo optimizar los accesos al disco.

Answer 2

B-tree es un árbol con n-arity, por lo que la página es exactamente 'n' celdas para acomodar elementos del nodo actual y la referencia hacia abajo. Para árbol B + puede ser como meta-nodos (que solo conserva las referencias) y los nodos hoja para almacenar datos.