ARBOLES B+

Arboles b+

Una variante de los árboles B que permite realizar de forma eficiente tanto el acceso directo mediante clave como el procesamiento en secuencia ordenada de los registros, es la estructura de árbol B+.
 Los árboles B+ almacenan los registros de datos sólo en sus nodos hoja (agrupados en páginas o bloques), y en los nodos interiores y nodo raíz se construye un índice multinivel mediante un árbol B, para esos bloques de datos.

Los árboles-B+ se han convertido en la técnica mas utilizada para la organización de archivos indizados. La principal característica de estos arboles es que todas las claves se encuentran en las hojas y por lo tanto cualquier camino desde la raíz hasta alguna de las claves tienen la misma longitud.

Propiedades

Un árbol B+ de orden n es una estructura formada por un conjunto de bloques de registros ordenados por clave, que se almacenan a nivel de hoja (llamado conjunto secuencia), y un índice sobre un árbol B de orden n para los bloques de registros (llamado conjunto índice). 

Las restricciones de ocupación que determine el orden n del árbol sólo afectarán al conjunto índice pero no a los bloques de registros, a los cuales se les exigirá una ocupación mínima (y una máxima) pero no estará relacionada con el orden del árbol.

Por tanto, las propiedades que estudiamos para los árboles B pueden aplicarse a los árboles B+; la diferencia entre ambos está en el nivel de las hojas. Además, los árboles B+ no almacenan en sus nodos interiores direcciones de registros, sino sólo claves. Los registros se obtienen a nivel de las hojas, donde se encuentran almacenados ordenados dentro de cada bloque. Es decir, los nodos hoja del conjunto índice direcciona los nodos terminales que contienen los datos. 

Los árboles B+ constituyen otra mejora sobre los árboles B, pues conservan la propiedad de acceso aleatorio rápido y permiten además un recorrido secuencial rápido. En un árbol B+ todas las claves se encuentran en hojas, duplicándose en la raíz y nodos interiores aquellas que resulten necesarias para definir los caminos de búsqueda. Para facilitar el recorrido secuencial rápido las hojas se pueden vincular, obteniéndose ,de esta forma, una trayectoria secuencial para recorrer las claves del árbol.


Su principal característica es que todas las claves se encuentran en las hojas. Los árboles B+ ocupan algo más de espacio que los árboles B, pues existe duplicidad en algunas claves. En los árboles B+ las claves de las páginas raíz e interiores se utilizan únicamente como índices

2. BUSQUEDA EN UN ÁRBOL B+

En este caso,la búsqueda no debe detenerse cuando se encuentre la clave en la página raíz o en una página interior,si no que debe proseguir en la página apuntada por la rama derecha de dicha clave. 

3. INSERCIÓN EN UN ÁRBOL B+

Su diferencia con el proceso de inserción en árboles B consiste en que cuando se inserta una nueva clave en una página llena,ésta se divide también en otras dos,pero ahora la primera contendrá con m/2 claves y la segunda 1+m/2, y lo que subirá a la página antecesora será una copia de la clave central. 

4. BORRADO EN UN ÁRBOL B+

La operación de borrado debe considerar:

• Si al eliminar la clave(siempre en una hoja)el número de claves es mayor o igual a m/2 el proceso ha terminado. Las claves de las páginas raíz o internas no se modifican aunque sean una copia de la eliminada,pues siguen constituyendo un separador válido entre las claves de las páginas descendientes.
• Si al eliminar la clave el número de ellas en la página es menor que m/2 será necesaria una fusión y redistribución de las mismas tanto en las páginas hojas como en el índice.