Prueba. Los árboles B Son estructuras formadas por páginas

Los árboles B Son estructuras formadas por páginas, cada una de las cuales tiene N llaves y  N + 1 apuntadores. Cada uno de los N + 1 apuntadores pueden tener un valor null o una dirección de memoria donde se encuentra otra página. Una página es el componente primario de la estructura y gráficamente se podría visualizar así:

[pic 1]

La parte superior de la gráfica representa un arreglo de enteros, cada componente puede almacenar una clave. La parte inferior, representa un arreglo de apuntadores donde cada componente puede almacenar una dirección de memoria donde existe otra página de la estructura. El rectángulo de la izquierda es una variable de tipo entero que almacena el número de llaves que se almacenan en una página en un momento dado del proceso. Por ejemplo:

[pic 2]

Esta página tiene una capacidad de M =  6 llaves. Para el caso particular el número 4 indica que en esta página existen 4 llaves y 4 + 1 apuntadores con un valor diferente de null. En general si M es el número máximo de llaves de una página, M1 = M + 1 será el número máximo de apuntadores que se pueden almacenar en una página y por lo tanto se puede afirmar que si una página tiene M llaves tendrá M1 apuntadores que podrían estar direccionados en otras M1 páginas.

Se define como el orden de un árbol B coma el valor N = M/2. Un árbol B puede tener un orden N= 1 o N= 2 o N= 3,etc. Refiriéndose a la gráfica anterior, el orden de el árbol B compuesto por páginas de ese tamaño será de N=3 ya que N= 6/2. Por lo tanto, podemos afirmar que si N es el orden de un árbol entonces M=2*N y M1 = M + 1. Por ejemplo, para un árbol B de orden N=2, una página completa se puede ver así:

[pic 3]

N=2                 orden del árbol

M = N*2         número máximo de llaves

M1 = M+1         número máximo de apuntadores

Existe una restricción importante para cada página. Toda página, con excepción de la página raíz del árbol, debe contener mínimo N llaves. Con esto se quiere decir que para los valores:

N=3                 

M = N*2         

M1 = M+1

Una página, que no sea la raíz, con esta información es incorrecta:

[pic 4]

ya que viola la restricción anterior. Para la página anterior, debe existir mínimo N=3 llaves.

...