ÁRBOLES B^*

1. INTRODUCCIÓN.

En 1973,Knuth propone nuevas reglas para realizar el mantenimiento de los B-árboles de forma que no se realiza una división de un nodo en dos ya que eso hace que los nodos resultantes tengan la mitad de claves,sino que se realizan divisiones de dos nodos completos a tres de forma que los nodos resultantes tienen dos tercios del total.Por consiguiente,este tipo de árboles son muy similares a los anteriores pero teniendo en cuenta:

1. Cada nodo tiene un máximo de m descendientes.
2. Cada nodo excepto el raíz tiene al menos (2m-1)/3 hijos.
3. La raíz tiene al menos dos descendientes (a menos de que sea hoja).
4. Una hoja contiene al menos E[(2m-1)/3] claves.
5. Todas las hojas aparecen en el mismo nivel.
6. Un nodo que no sea hoja con k descendientes contiene k-1 llaves.
7. Un nodo hoja contiene por lo menos E[(2m-1)/3] llaves, y no más de m-1.

Existe un problema añadido a este tipo de árboles pues cuando la división de nodos se propaga hasta la raíz dividirla según hemos visto implicaría que junto a uno de sus hermanos que estuvieran completos se crearán tres nuevos nodos llenos en dos terceras partes.Esto no es posible pues la raíz no tiene hermanos.La solución al problema puede ser permitir que la raíz tenga un número superior de claves de forma que si se divide se puedan producir 3 nodos cumpliendo las características de los árboles B^*.

Los cambios críticos entre el anterior conjunto de propiedades y el conjunto que se define para un árbol B convencional están en las reglas 2 y 6: un árbol B^* tiene nodos que contienen un mínimo de (2m-1)/3 llaves. Por supuesto, esta nueva propiedad afecta los procedimientos de eliminación y redistribución.

Para realizar los procedimientos de árboles B^* también se debe abordar la cuestión de dividir la raíz, la cual, por definición, nunca tiene hermanos. Si no existen hermanos, no es posible la división de dos a tres. Knuth sugiere permitir que la raíz crezca hasta un tamaño mayor que los demás nodos, de tal forma que, cuando se divida, pueda producir dos nodos cada uno lleno casi a las dos terceras partes. Esta sugerencia tiene la ventaja de asegurar que todos los nodos por debajo del nivel de la raíz se adhieren a las características de los árboles B^*. Sin embargo, tiene la desventaja de requerir que los procedimientos sean capaces de manejar un nodo que sea de mayor tamaño que todos los demás. Otra solución es realizar la división de la raíz como una división convencional de uno a dos. Esta segunda solución evita cualquier lógica especial de manejo de nodos. Por otro lado, complica la eliminación, la redistribución y otros procedimientos que deben ser sensibles al número mínimo de llaves permitidas en un nodo. Tales procedimientos tendrían que ser capaces de reconocer que los nodos descendientes de la raíz legalmente pueden estar solo llenos.