Alboles b*

Árbol B*
El Árbol B* es un caso particular de Árbol B, al que se le adiciona la restricción de que todos los nodos se mantienen2/3 llenos, o sea, la cantidad de llaves en cada nodo no puede ser menor que (2/3)p. Esta condición favorece que se aprovechen losaccesos a disco, pues cada nodo está obligado a permanecer más lleno que los del árbol B.
Otra particularidad del Árbol B*, que lodistingue del Árbol B, es que el nodo raíz puede tener hasta (4/3)p llaves. Esta salvedad surge producto de que si se restringe aeste nodo a tener a lo sumo p-1 llaves, al insertar una nueva llave, deberíamos proceder a dividir el nodo en dos nodos, que nocumplirían con la condición de tener al menos (2/3)p llaves.
Esto se comprenderá mejor en lo adelante, cuando se expliquen lasoperaciones básicas en este tipo de árboles.
De manera más formal, un Árbol B*, de orden p, cumple que:
1.
donde q Ki-1 para i =q.
2. Cada nodo, excepto la raíz, tiene, cuando más, p apuntadores de árbol. La raíz puede contener hasta (4/3)p + 1apuntadores.
3. Cada nodo, excepto la raíz y los nodos hoja, tienen por lo menos (2/3)p +1 apuntadores de árbol. El nodo raíz tiene, comomínimo, dos punteros a nodos del árbol, a menos que sea el único nodo del árbol.
4. Un nodo con q apuntadores de árbol, q