Arboles B Y B+

Resumen

En este documento se expone la definición y características generales de los árboles b y árboles b+ como estructuras de datos. Se describen las operaciones básicas que se pueden realizar, como son la búsqueda, la inserción y la eliminación de claves en cada una de las estructuras a tratar explicando el paso a paso para cada operación y ejemplificando brevemente. Finalmente se destacan las diferencias entre las estructuras de datos.

Introducción

Las estructuras de datos han de estar presentes siempre que queramos organizar un conjunto de datos ya sea grande o pequeño, en busca de mejorar su manipulación, teniendo en cuenta tiempos óptimos de búsqueda,inserción o eliminación de datos. Así surgen un número considerable de diferentes estructuras de datos, en este caso puntual hablaremos en específico de dos, las cuales son árboles b, y árboles b+ destacando entre estas que los datos se almacenan de forma ordenada y además permite el almacenamiento de grandes cantidades de información.

Árboles B

Definición 1.

Son una generalización de los árboles balanceados. Representan básicamente un método para almacenar y recuperar información en medios externos.

En este tipo de árboles, un grupo de nodos recibe el nombre de página esté llena como mínimo hasta la mitad, cada página de un árbol-B de orden d tiene 2d+1 hijos como máximo y d+1 hijos como mínimo , excepto la página raíz que puede contener como mínimo 1 dato y por consiguiente solamente dos hijos.

formalmente un árbol b se define así:

Cada página, excepto la raíz, contiene entre d y 2d elementos, siendo d el grado del árbol.

La raíz puede almacenar entre 1 y d elementos.

Cada página, excepto la raíz y las páginas hoja, tiene entre d+1 y 2d+1 descendientes. se utilizará m para expresar el número de elementos por página.

La página raíz tiene al menos dos descendientes.

Las páginas hojas están todas al mismo nivel.

Ref: Estructuras de datos, Osvaldo Cairó, Silvia Guardati, tercera edición,página 241.

Definición 2.

B-árbol es un árbol de búsqueda que puede estar vacío o aquel cuyos nodos pueden tener varios hijos, existiendo una relación de orden entre ellos. Los nodos que conforman el árbol B son denominados Páginas, para comprender de una mejor manera el concepto de Árbol B es necesario, primeramente, conocer la estructura básica de una página.

Un campo Puntero Página < Dato, se utiliza para establecer el enlace con otra página que posee datos menores del dato que posee

Dato, información que posee la página

Un campo Puntero Página > Dato, que se utiliza para establecer el enlace con otra página que posee datos menores del dato que posee, si la página fuera el último de la lista, este campo tendrá como valor: NULL (vacío). Al emplearse el campo puntero sig para relacionar dos nodos, no será necesario almacenar físicamente a los nodos en espacios contiguos.

Ref. Universidad Francisco de Paula Santander, programa de ingeniería de sistemas - http://ingsistemas.ufps.edu.co/SEED/arbolb.html

Ejemplo

Los árboles B surgieron en 1972 creados por R. Bayer y E.McCreight. El problema original comienza con la necesidad de mantener índices en almacenamiento externo para acceso a bases de datos, y se resuelve utilizando estos árboles que con múltiples hijos hacen que el mantenimiento de índices en memoria sea mucho más eficiente, además este tipo de estructuras es idónea para mantener grandes cantidades de datos en almacenamiento externo.

Estructura de una página

Las páginas de un árbol B, es decir las páginas que no son hoja, están representados como un conjunto ordenado de elementos y punteros a los hijos. Cada página interna contiene un máximo de M hijos y, con excepción del nodo raíz, un mínimo de X hijo(s). La relación entre M y X implica que dos nodos que están a medio llenar pueden unirse para formar una página con las características básicas, y un nodo lleno puede dividirse en dos páginas con las características básicas. Haciendo posible que el árbol B se ajuste para preservar sus propiedades ante la inserción y eliminación de elementos.

Las páginas hoja tienen la misma restricción sobre el número de elementos, pero no tienen hijos, y por tanto poseen punteros vacíos (nulos). El nodo raíz tiene límite superior de número de hijos, pero no tiene límite inferior.

Operaciones

Búsqueda

La búsqueda de una clave en un árbol B es similar a las de los árboles binarios, para ello debemos situarnos en el nodo raíz del árbol,si la clave se encuentra ahí hemos terminado y si no es así seleccionamos de entre los hijos el que se encuentra entre dos valores de clave que son menor y mayor que la buscada respectivamente y repetimos el proceso hasta que la encontremos.En caso de que se llegue a una hoja y no podamos proseguir la búsqueda la clave no se encuentra en el árbol.

Eliminación

Para eliminar una clave de un árbol B realizamos uniones. Cuando borramos una clave que está en un nodo interior, lo primero que realizamos es un intercambio de este valor con el inmediato sucesor en el árbol, es decir, el hijo más a la izquierda del hijo derecho de esa clave. así podríamos encontrar que es necesario realizar dos operaciones para permitir que el árbol siga cumpliendo las condiciones básicas.

redistribución: la utilizaremos en el caso en que al borrar una clave el nodo se queda con un número menor que el mínimo y uno de los hermanos adyacentes tiene al menos uno más que ese mínimo, es decir, redistribuyendo podemos solucionar el problema.

Unión: la utilizaremos en el caso de que no sea posible la redistribución y por tanto sólo será posible unir los nodos junto con la clave que los separa y se encuentra en el padre.

Ejemplo

Sí

...