Arboles B

Arboles B*
Una variante del árbol B es el árbol B*, cuya peculiaridad consiste en que se aumenta el número mínimo de valores de clave que puede contener un nodo que no sea la raíz, de forma que enlugar de garantizar un 50% de utilización de espacio como en el árbol B, se aproveche como mínimo las dos terceras partes del mismo. Se puede definir a un árbol B* de orden m como sigue:
1. Cadanodo, excepto la raíz, tiene como máximo m hijos.
2. Cada nodo, excepto la raíz tiene como mínimo [2m-1]/3.
3. Todas las hojas están en el mismo nivel.
4. Un nodo con q hijos, contiene q-1 valores declave.
 5. La raiz puede tener como maximo (4/3)(m-1).
 Las operaciones que se pueden realizar en los arboles B* son las mismas de los arboles B(insercion, eliminacion,busqueda).
Insercion:
Lainserción en un árbol B* se realiza del mismo modo que en el árbol B, siempre y cuando el nodo tenga espacio para ser insertado. La diferencia está en el momento en que se va a insertar un elementoen un nodo que ya está lleno. Al igual que los arboles B la insercion se realiza en las hojas. 
 Cuando se va a insertar en la raiz y esta llena crece la altura del arbol y se procede asi:1.Insertar la clave como si realmente hubiera espacio.
2.Crear una nueva pagina que pasara a ser la raiz del arbol.
3.Dividir la pagina en dos partes equitativas y subir la mediana al nuevo nodo creado.4.Las dos paginas creadas pasaran a ser respectivamente el lado izquierdo y derecho de la nueva pagina.
 
-Cuando se va a insertar en un nodo hoja que esta lleno se procede asi: 
Se presentan doscasos:
 Se explican mas adelante con un ejemplo.
 
Ejemplo cuando se va a insertar en la raiz y esta llena.
Tenemos el siguiente arbol de orden 7

 
 Le vamos a insertar el 35, quedaria asi:
  
Ejemplo cuando se va a insertar en una pagina hoja que esta llena:
Veamos el ejemplo de un arbol de orden 7 cuando se le va a insertar a una pagina llena y que el hermano tiene posiciones...