Arboles B

Un árbol B de orden 'n' es aquel árbol de búsqueda que satisface las siguientes propiedades:

• Cada página contiene como máximo '2n' llaves.
• Cada página contiene como mínimo 'n' llaves, excepto la raíz que puede contener sólo una
• Cada página o es una página de hoja o tiene 'm+1' descendientes, siendo 'm' el número de llaves en esta página.
• Todas las páginas de hoja aparecen al mismo nivel.

Búsqueda
La búsqueda se realiza con los siguientes criterios:

• Si el argumento de búsqueda se encuentra entre dos llaves de la página, entonces la búsqueda sigue en la página apuntada por el puntero entre ellas.
• Si el argumento de búsqueda es mayor que la última llave de la página, entonces se sigue la búsqueda en la página apuntada por el último apuntador.
• Si el argumento de búsqueda es menor que la primera llave de la página, entonces se sigue la búsqueda en la página apuntada por el primer apuntador.
• Si en cualquier caso el apuntador a la página en la que hay que seguir la búsqueda es NIL entonces el argumento de búsqueda 'x' no está en el árbol y finaliza la búsqueda.

Inserción
Se realiza buscando el lugar donde debe insertarse de la misma manera en que se realiza la operación de búsqueda. Localizada dicha posición si la página correspondiente tiene 'm>2n' llaves se inserta en ella en la posición dada por el criterio de búsqueda, pero si la página está llena (m=2n) entonces el árbol debe reorganizarse.

• La página se divide en dos nuevas páginas.
• La llave que se encontraba en la mitad, se sube en un nivel colocándola en la página madre. A la hora de determinar la llave central se tiene en cuenta también la nueva llave que se pretende insertar.
• Las páginas que se encontraban a la izquierda se distribuyen en la página nueva apuntada por la izquierda de la llave mitad y las que se encontraban a la derecha se distribuyen en la página nueva apuntada por la derecha de la llave mitad.

Eliminación
Debes tener en cuanta la subocupación y la sobreocupación.