Arboles B+

• Almacenan registros de datos e sus nodos hoja, (se agrupan en paginas)
• En los nodos interiores y nodo raíz se construye un indice multinivel
• Son la técnica mas utilizada para la organización de archivos indexados
• Todas las claves están en las hojas
• Cualquier camino desde la raiz hasta la clave tiene la misma longitud
• El los nodos inferiores no se almacenan direcciones de registro solo claves
• Cada pagina excepto la raiz contiene entre N y 2N elementos
• Cada pagina excepto la raiz tiene entre N+1 y 2N+1 descendientes
• La raiz tiene por lo menos 2 descendientes
• Las hojas se encuentran todas al mismo nivel
• Son arboles ene arios

Operaciones

• Busqueda de X elemento

• Insercion de X elemento

• Eliminacion de X elemento

BUSQUEDA EN UN ARBOL B+

Para buscar un registro en un árbol B+ a partir de su clave, primero hay que recorrer todo el árbol del índice, comparando los valores de clave de cada nodo y tomando el descendiente adecuado, tal y como se realiza en la operación de búsqueda de un registro en un árbol B. Ahora, la diferencia fundamental consiste en que al estar todos los registros en los bloques de datos, es necesario que la búsqueda llegue siempre a un nodo hoja, que es donde se encuentra la dirección del bloque donde puede estar el registro almacenado. Una vez localizado el bloque, se llevará a memoria, donde se realiza la búsqueda del registro.

INSERCION EN UN ARBOL B+

Para insertar un nuevo registro en un árbol B+, hay que localizar, a partir de su clave, el bloque en el que debe almacenarse, de modo similar a una operación de búsqueda, recorriendo el árbol desde el página raíz hasta la página hoja adecuada. Una vez encontrada la página indica, si aún no se ha ocupado su máximo número de registros, se inserta el elemento de forma ordenada en la página hoja.

Si el bloque está completo, se produce “desbordamiento”, se resolverse "rompiendo" la página y repartiendo equitativamente los registros entre dos nuevas páginas hojas.

Por lo tanto, una vez obtenido la página, las estrategias son:

 Si hay espacio en la página:

 Se almacena el registro en la página de forma ordenada. 

Se reescribe nuevamente la página en disco.

 Si no hay espacio en la página:

Se crea una nueva página en la estructura y se reparten los datos de la página entre ambas, insertando el dato en la posición adecuada.

Se actualiza el índice: al tener una página más de registros, hay que insertar, en el árbol B+ el índice, una clave separadora que diferencie los datos de estas dos páginas consecutivas; por convenio ésta se obtiene a partir de la primera clave del segundo bloque.