ÁRBOLES B+

¿Qué Son? 

Descripción:

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 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 direccionan los nodos terminales que contienen los datos.
Es de notar que los arboles-B+ ocupan un poco mas 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.

Formalmente se define un árbol-B+ de la siguiente manera:

Cada pagina, excepto la raíz, contiene entre n y 2n elementos.

Cada pagina, excepto la raíz, tiene entre n + 1 y 2n + 1 descendientes. Se utiliza m para expresar el numero de elementos por pagina.

La pagina raíz tiene al menos dos descendientes.

Las paginas hojas están todas al mismo nivel.

Todas las claves se encuentran en las paginas hojas.

Las claves de las paginas raíz e interiores se utilizan como índices.

Estructura

Conjunto secuencia: Está formado por los registros de datos, agrupados dentro de bloques en los que se mantienen ordenados en base a la clave de búsqueda. Estos bloques no tienen por qué almacenarse físicamente en el archivo según la ordenación lógica, por lo que se mantiene una lista doblemente enlazada de bloques, y de este modo poder recuperar ordenados todos los registros de datos recorriendo toda la lista de bloques.

Conjunto índice: Es un árbol B de orden n que indexa los bloques de registros de datos del conjunto secuencia. En los nodos de este árbol B sólo se almacenan claves de búsqueda y direcciones de nodos descendientes, excepto los nodos hoja, que contienen las direcciones de los bloques con los registros de datos del conjunto secuencia.

Inserción en un árbol B+:

La inserción en un árbol B+ es similar a la del árbol B se diferencia en el momento que una pagina deja de cumplir la condición 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 información cuando la clave que sube es de una pagina hoja.

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

1.Se ubica en la pagina raíz.

2.Se evalúa si es una pagina hoja

    2.1.Si la respuesta es afirmativa, se evalúa 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 así el mismo proceso hasta donde sea necesario, si   este proceso llega hasta la raíz la altura del árbol 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 descendiente donde proseguir la búsqueda. Se regresa al paso 1.

Ejemplo de inserción:

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

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:

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 paginas hojas.

Ejemplo del caso 1:

Ejemplo del caso 2:

Cibergrafia

https://sites.google.com/site/tutoriasarboles/arboles-b-y-b