Los árboles B+ son una variante de los árboles B, se diferencian en que los árboles B+ toda la información se encuentra almacenada en las hojas. En la raíz y en las páginas internas se encuentran almacenado índices o claves para llegar a un dato.
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.
-Toda la información se encuentra almacenada en las páginas hoja, por lo que en las páginas internas se puede duplicar las claves.
Para definir la altura de un árbol b+ se puede dar de 2 diferentes casos. Por ejemplo, dado un M, el cual corresponde al número máximo de hijos que un nodo puede contener se define por:
La altura h de un árbol B+ (El peor caso):
Log de M elevado a la n
La altura h de un árbol B+ (Mejor caso)
log de (M/2) elevado a la n
Este caso se debe a que, si guardamos menos hijos en los nodos, se necesitarán más niveles para almacenar todo.
Para un árbol B+ de orden n, con una altura h:
· El número máximo de claves es: n elevado a la h
· El número mínimo de claves es: 2(n/2) elevado a la h
Operaciones básicas en los Árboles B+
Inserción
La inserción en un árbol B+ es similar a la del árbol B se diferencia en el momento que una página deja de cumplir la condición del número de datos almacenados. Para realizarla se debe subir una copia de la clave mediana de los datos del nodo a la página padre, solo se duplica la información cuando la clave que sube es de una página hoja.
Los pasos por seguir para una inserción son los siguientes:
1.Se ubica en la página raíz.
2. Se evalúa si es una página hoja.
2.1. Si la respuesta es afirmativa, se evalúa si no sobrepasa los límites 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 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.
2.2. 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] (Siendo m la cantidad máxima de hijos que el nodo pueda tener) 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] (Siendo m la cantidad máxima de hijos que el nodo pueda tener) entonces debe realizarse una redistribución de claves, tanto en el índice como en las paginas hojas.
Búsqueda
La operación de búsqueda en arboles B+ no debe detenerse cuando se encuentre la clave en la página raíz o en una página interior, sino que debe proseguir en la página apuntada por la rama derecha de dicha clave.
Referencias
O. Sosa, I. Hammurabi, N. Luna, A. De Jesús, N. Daza. (2014). Arboles B y B+. 2020, de SliderShare Sitio web: https://es.slideshare.net/neltherdaza/arboles-b-y-arboles-b