ARBOLES B+

1.    QUE SON 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+ (propuesta por Knuth [Knu97b]). 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 más utilizada para la organización de archivos indizados

.  CARACTERÍSTICAS DE ARBOLES B+

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.

 Otras características:

-La raíz almacena como mínimo un dato y como máximo m-1 datos.

-La página raíz tiene como mínimo dos descendientes.

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

-Las páginas intermedias tienen como máximo m-1 datos.

-Todas las paginas hojas tienen la misma altura

-La información se encuentra ordenada.

 PROPIEDADES DE ARBOLES B+

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, 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 direccionan los nodos terminales que contienen los datos.

Es de notar que los arboles-B+ ocupan un poco más de espacio que los arboles-B, y esto ocurre al existir duplicidad en algunas claves. Sin embargo, esto es aceptable si el archivo se modifica frecuentemente, puesto que se evita la operación de reorganización del árbol que es tan costosa en los arboles-B.

 INSERCIÓN EN UN ÁRBOL B+

Los pasos a seguir para una inserción son los siguientes:

• Se ubica en la página raíz.
•  Se evalúa si es una página hoja
• Si la respuesta es afirmativa, se evalúa si no sobrepasa los límites de datos.
• Si la respuesta es afirmativa, entonces se procede a insertar el nuevo valor en lugar del correspondiente.
• Si la respuesta es negativa, se divide la página en dos, se sube una copia de  la mediana a la página padre, si la página padre se encuentra llena se debe de partir igual y así el mismo proceso hasta donde sea necesario, si   este proceso llega hasta la raíz la altura del árbol aumenta en uno.

• Si no es hoja, se compara el elemento a insertar con cada uno de los valores almacenados para encontrar la página descendiente donde proseguir la búsqueda. Se regresa al paso 1.

 ELIMINACIÓN:

La operación de eliminación en árboles-B+ es más simple que en árboles-B. Esto ocurre porque las claves a eliminar siempre se encuentran en las páginas hojas. En general deben distinguirse los siguientes casos:

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.

Si al eliminar una clave, la cantidad de llaves queda menor que [m/2] entonces debe realizarse una redistribución de claves, tanto en el índice como en las páginas hojas.

BÚSQUEDA:

La operación de búsqueda en árboles-B+ es similar a la operación de búsqueda en árboles-B.

El proceso es simple, sin embargo puede suceder que al buscar una determinada clave la misma se encuentre en un nodo raíz o interior, en dicho caso no debe detenerse el proceso, sino que debe continuarse la búsqueda con el nodo apuntado por la rama derecha de dicha clave. • Por ejemplo, al buscar la clave 55 en el árbol-B+ de la figura 6 se advierte que esta se encuentra en el nodo raíz. En este caso, debe continuarse el proceso de búsqueda en el nodo apuntado por la rama derecha de dicha clave, o sea, si se encuentra la clave Ki-1, debemos continuar la búsqueda por el apuntador Pi.

LINK DEL CODIGO

VIDEO TUTORIAL DE ARBOLES B+

ESPERAMOS QUE HAYA QUEDADO CLARO EL TEMA