Descripcion De Proyectos

Inserción de arboles b+
El proceso de inserción en árboles-B+ es relativamente simple, similar al proceso de inserción en árboles-B. La dificultad se presenta cuando desea insertarse una clave en un nodo que se encuentra lleno. En este caso, el nodo afectado se divide en 2, distribuyéndose las claves de la siguiente forma: " las p/2 primeras claves en el nodo de la izquierda y las p/2 + 1restantes claves en el nodo de la derecha". Una copia de la clave del medio sube al nodo padre. En la figura 7 hay dos diagramas que ilustran como funciona este caso.

Puede suceder que el nodo padre se desborde nuevamente, entonces tendrá que repetirse el proceso anterior. Es importante notar que el desbordamiento en un nodo que no es hoja no produce duplicidad de claves. El proceso de propagaciónpuede llegar hasta la raíz, en cuyo caso la altura del árbol puede incrementarse en una unidad. En la figura 8 se presentan dos diagramas que muestran este caso.

Supóngase que se desea insertar las siguientes claves en un árbol-B+ de orden 5 que se encuentra vacío:
claves: 10-27-29-17-25-21-15-31-13-51-20-24-48-19-60-35-66
Los resultados parciales que ilustran el crecimiento del árbol sepresentan en los siguientes diagramas correspondientes a la figura 9

Fig. 9 Crecimiento del árbol B a medida que se insertan los valores señalados
Eliminación
La operación de eliminación en árboles-B+ es mas simple que en árboles-B. Esto ocurre porque las claves a eliminar siempre se encuentran en las paginas hojas. En general deben distinguirse los siguientes casos:
1. Si al eliminar unaclave, la cantidad de llaves queda mayor o igual que p/2 entonces termina la operación. Las claves de los nodos raíz o internos no se modifican por más que sean una copia de la clave eliminada en las hojas. (Se presenta un ejemplo de este caso en la figura 10).
2. Si al eliminar una clave, la cantidad de llaves queda menor que p/2 entonces debe realizarse una redistribución de claves, tanto enel índice como en las paginas hojas. (Hay dos ejemplos que ilustran como funciona este caso en las figuras 11 y 12 ).

Nota: Al eliminar la clave 27 de la página A, la cantidad de llaves queda menor que p/2 por lo que debe realizarse una redistribución de las claves. Se toma la clave que se encuentra más a la derecha en la rama izquierda de 25 (21 de la página B). Se coloca dicha clave en lapágina A y una copia de la misma, como índice, en la página C. (Se le llama página a un nodo)

Arboles b* Inserción
La inserción en un árbol B* se realiza del mismo modo que en el árbol B, siempre y cuando exista capacidad en el nodo para colocar la nueva llave. La diferencia está en el momento en que se va a insertar un elemento en un nodo que ya está lleno.
La manera de proceder en caso deinsertar un elemento en un nodo lleno, varía si dicho nodo es la raíz o si es un nodo hoja. Note que cuando se habla de una inserción en la raíz es o porque la raíz es el único nodo del árbol y el nuevo elemento debe ser insertado en ella o porque la inserción en una hoja, provocó la promoción de una llave para ser insertada en el padre y esta promoción se propagó hasta la raíz.
Cuando se va a insertaren la raíz del árbol y está llena, caso en que ocurre un crecimiento en la altura del árbol, se procede de la manera siguiente:
1. Insertar la llave como si realmente tuviese sitio libre.
2. Crear un nuevo nodo, que pasará a ser la raíz del árbol. Extraer el nodo que ocupa la posición del medio en el nodo en que se insertó e insertarlo en la nueva raíz.
3. Dividirequitativamente la página original en dos nuevas páginas Estas páginas serán los hijos derecho e izquierdo del nodo que promocionó a la página superior.
Es importante hacer notar que esto sucede solo en el momento en que la raíz, producto de la inserción, excede las (4/3)p llaves, lo cual garantiza que al dividirse en dos el nodo original, en cada nodo queden las (2/3)p llaves que necesita un nodo del árbol...