Estructura de datos

Arboles B y B+

En este segmento hablaremos de los arboles B y B+, más que todo de sus operaciones básicas que son la creación la inserción y la eliminación de claves.

Arboles B: 

Los arboles B son una generalización de los arboles balanceados, se utilizan como método de búsqueda externa, cada nodo (pagina) en un árbol B de orden d contiene 2d claves como máximo y d claves como mínimo.

Cada página tiene 2d+1 hijos como máximo y d+1 hijos como mínimo, excepto la página RAIZ que puede tener como mínimo una clave y por consiguiente 2 hijos. Ahora vamos a dar un ejemplo de la creación de un árbol B.

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:

Estas son dos paginas donde puedes complementar información

http://decsai.ugr.es/~jfv/ed1/tedi/cdrom/docs/arb_B.htm

http://rua.ua.es/dspace/bitstream/10045/4411/24/ped-06_07-tema3_6.pdf

Arboles B+

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:

Se comienza con la raíz y llega a las hojas.

Inserción:

Es similar a la inserción del árbol B, cuando se inserta y la página está llena se divide en dos a la izquierda y derecha, una copia de la clave del medio sube a la página antecesora.

Ejemplo:

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

Ahora si vamos a insertar el 13 lo primero que pensamos es que va entre la clave 10 y la 15 pero como pasaba en los arboles B hay que partir la pagina en dos porque no pueden haber 5 claves en una página.

Como la clave 15 es la que queda en el medio esta sube a la raíz pero deja un duplicado en las hojas entonces quedaría de la siguiente manera:

Como dijimos antes el 15 sube pero deja un duplicado en las hojas que es donde está la pagina (15-17-21), y no está rompiendo ninguna regla de los arboles B+.

Ahora vamos a insertar el 51, observamos que al insertarlo queda a la derecha del 31 pero la pagina quedaría de 5 claves y no puede quedar así entonces identificamos quien queda en el medio y seria el 29. Así el 29 sube pero deja un duplicado en las hojas y quedaría de la siguiente forma:

Como se observa el 29 subió y dejo una copia en la hoja y se abrió la pagina, tenga en cuenta que no puede haber un número mayor a la izquierda es decir por ejemplo si el 29 está en la página RAÍZ no puede haber un 40 a la izquierda de él porque estaríamos rompiendo una regla de los arboles B+.

Eliminación del Árbol B+

La eliminación es más simple que en arboles B porque las claves siempre están en las hojas.

Existen dos casos:

*Si al eliminar una clave m queda >=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. El árbol puede disminuir de altura.

Ejemplo 1:

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

Empezamos eliminando el 27, ahora deberíamos identificar que si eliminamos el 27 la clave que contiene al 25 quedaría sola por lo que romperíamos una regla de árbol B+, entonces lo que hacemos es subir el 21 y bajar el 25 de la página raíz a la hoja, se puede hacer ya que tenemos una copia en la hoja, así nos quedaría:

Así nos quedó después de haber eliminado el 27. Ahora eliminemos el 21 y lo primero que se viene a la mente es eliminarlo de la hoja pero si nos fijamos bien también está en la página raíz y no podemos subir el 17 porque el 15 quedaría solo pero lo que si podemos hacer es eliminar el 21 y unir el (15,17, 25), entonces nos quedaría:

Esta eliminación es válida porque como se dan cuenta no estamos rompiendo ninguna regla y lo más importante es que al eliminar es como si nos estuviéramos devolviendo es por eso que quedo la raíz con dos hijos, después de haber tenido tres hijos.

Este es un link donde encontraras mas ejemplos de los arboles B+

http://www.virtual.unal.edu.co/cursos/ingenieria/2001412/capitulos/cap8/85.html