Los arboles B+

Arboles B+

Los arboles B+ son una variante de los arboles B, se diferencian en que los arboles B+ toda la informacion se encuentra almacenada en las hojas . En la raiz y en las paginas internas se encuentran almacenado indices o claves para llegar a un dato.

Principales caracteristicas de los arboles B+ de orden m son:

-La raiz almacena como minimo un dato y como maximo m-1 datos.

-La pagina raiz tiene como minimo dos decendientes.

-Las paginas intermedias tienen como minimo (m-1)/2(Parte entera ) datos.

-Las paginas intermedias tienen como maximo m-1 datos.

-Todas las paginas hojas tienen la misma altura

-La informacion se encuentra ordenada.

-Toda la informacion se encuentra almacenada en las paginas hoja, por lo que en las paginas internas se puede duplicar la claves.

Ejemplo de un arbol B+ de orden 5:

Inserccion en un arbol B+:

La inserccion en un arbol B+ es similar a la del arbol B se diferencia en el momento que una pagina deja de cumplir la condicion del numero de datos almacenados. Para realizarla se debe subir una copia de la clave mediana de los datos del nodo a la pagina padre, solo se duplica la informacion cuando la clave que sube es de una pagina hoja.

Los pasos a seguir para una insercion son los siguientes:

1.Se ubica en la pagina raiz.

2.Se evalua si es una pagina hoja

2.1.Si la respuesta es afirmativa, se evalua si no sobrepasa los limites de datos.

2.1.1.Si la respuesta es afirmativa, entonces se procede a insertar el nuevo valor en lugar del correspondiente.

2.1.2.Si la respuesta es negativa, se divide la pagina en dos, se sube una copia de la mediana a la pagina padre, si la

pagina padre se encuentra llena se debe de partir igual y asi el mismo proceso hasta donde sea necesario, si este proceso llega hasta la raiz la altura del arbol aumenta en uno.

2.2. si no es hoja, se compara el elemento a insertar con con cada uno de los valores almacenados para encontrar la pagina decendiente donde proseguir la busqueda. Se regresa al paso 1.

Ejemplo de insercion:

-Insertar las siguientes claves a un arbol de orden 5: 10-27-29-17-25-21-15-31-13-51-20-24-48-19-60-35-66

Eliminacion:

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 una clave, la cantidad de llaves queda mayor o igual que [m/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.

2. Si al eliminar una clave, la cantidad de llaves

...