Arboles B / B+

Se utilizan para manejar archivos que contengan gran cantidad de información, los cuales son usados como método de búsqueda externa. Fueron propuestos por Bayer McCreight en 1970.

Cada nodo (pagina) en un árbol B de orden N contiene 2N claves como máximo y n claves como mínimo.

Cada página tiene 2N hijos como máximo y N+1 hijos como mínimo excepto la página raíz que puede tener como mínimo 1 clave y por consiguiente 2 hijos.

Las páginas se almacenan en dispositivos secundarios, la página raíz se almacena en la memoria principal.

Las paginas hojas están dotas al mismo nivel.

El árbol crece de abajo hacia arriba.

No aceptan llaves repetidas.

Creación e inserción de un árbol B:

Crear un árbol grado 2 insertando las siguientes claves:

10 – 27 – 29 -17 – 25.

El árbol B como es de orden 2 entonces tiene 4 espacios para guardar claves entonces lo tenemos de la siguiente manera.

Ahora vamos a insertar el 10 y quedaría de la siguiente manera.

Insertamos el 27 y quedaría

Ahora insertamos el 29 

Y por último insertamos el 17 que quedaría de la siguiente manera.

Lo que buscamos es que quede ordenado de menor a mayor, ahora al ingresar el 25 tendría que quedar en la mitad del 17 y 27 pero como es de orden 2 no pueden haber más de 5 claves por pagina porque su máximo son 4 entonces lo que hacemos es partir el árbol y nos quedaría de la siguiente manera:

Como observamos  partimos el árbol B y el 10 y el 17 quedaron a la izquierda del 25 porque son menor que este y el 27 y 29 quedaron a la derecha por ser mayores que el 25.

Ahora insertaremos en un árbol ya creado.

Insertaremos el 90 – 8 – 77.

Empecemos insertando el 90 nos quedaría a la derecha del 52 ya que el 90 es mayor que el 52.

Ahora insertemos el 8, el 8 quedaría a la izquierda del 22 porque el 8 es menor que 22.

Y por último insertemos el 77, al insertar el 77 observamos que tiene que ser entre el 52 y 90 pero ¿cuál es el problema? Que la pagina quedaría de 5 claves y solo se puede de 4 claves porque es de orden 2 si fuera de orden 3 nos quedaría cada página de 6 claves y no tendríamos problema. Entonces para solucionar este problema hay que tener en cuenta el numero que queda en la mitad al insertar el 77 y vemos que es el 52, ahora ya después de haberlo identificado lo que hacemos es subir el 52 a la pagina Raíz y partir la pagina en la que quedo el (39-41-77-90), entonces quedaría de la siguiente manera.

Eliminación en arboles B

Es una operación más complicada, consiste en eliminar o quitar la clave sin violar los principios del árbol B.

-   Si la clave a borrar se encuentra en una hoja simplemente se suprime, si no debe bajarse la clave adyacente de la pagina antecedente y sustituir esta clave por la que se encuentra más a la derecha del sub-árbol izquierdo o por la que se encuentra más a la izquierda del sub-árbol derecho.

Ejemplo:

A partir de este árbol B eliminar el 27, entonces como esta en una hoja y la pagina tiene tres claves simplemente se suprime el 27, así quedaría de la siguiente manera: 

Ahora eliminemos el 10, si observamos nos damos cuenta de que si lo eliminamos el 13 quedaría solo y estaríamos violando una de las reglas del árbol B entonces lo que hacemos es bajar 15 y unirlo con el (13-17-21) y así no estaríamos violando ninguna regla porque el único que puede quedar con una clave es la página RAIZ con dos hijos, quedaría de la siguiente manera:

Código C++:

Arboles B+

*Si la clave a borrar se encuentra en la pagina hoja, simplemente se elimina.

*Si la clave o la llave no esta en la hoja, debe bajarse la clave adyacente de la pagina antecedente y sustituir la clave por la que se encuentre mas a la derecha del sub árbol izquierdo o por la que se encuentre mas a la izquierda del sub árbol derecho

Este tipo de árbol representa una colección de datos ordenados de manera que se permite una inserción y borrado eficientes de elementos. Es un índice, multinivel, dinámico, con un límite máximo y mínimo de claves por nodo, un árbol B+ es una variación de un árbol B.

-       Todas las claves se encuentran en las hojas

-       Cualquier camino desde la raíz hasta la clave tiene la misma longitud

-       Ocupan más espacio que los arboles B porque hay duplicidad de claves

Las operaciones básicas son la búsqueda la inserción y la eliminación.

Búsqueda:

Inicia desde la raiz, hasta llegar a las hojas

Inserción:

Al insertar un elemento y la pagina se encuentra llena, esta se divide (dependiendo del orden) en la misma cantidad tanto a la izquierda, como a la derecha, division de la cual sube una copia del elemento que quedo en el medio.

A partir de este árbol B+ insertar el 13 – 51.

Al insertar 13 la pagina se va a dividir en dos tal como se explico en el punto anterior.

La clave 15 se situa en el medio, por lo que una copia de esta sube:

Al insertar 51, el elemento que resulta en el medio de la pagina 29, subiria un duplicado:

Eliminación del Árbol B+

Se pueden presentar dos casos para la eliminacion:

*Si se elimina la clave a >=d termina la operación, las claves de la página raíz o internas no se modifican por más que sean copias.

* Si m queda menor que “d” debe realizarse una distribución de claves tanto en el índice como en las páginas hojas.

A partir de este árbol eliminar el 27 – 21.

Si se elimina 27, 25 quedaria solo, por lo que es necesario subir 21 (teniendo en cuenta la generacion de la copia)y bajar 25 a la raiz:

Al eliminar 21, se procede a unir 15,17,25:

Código C++: