ÁRBOLES B

¿Qué Son?

Los B-árboles sugieron 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,es decir,con el grave problema de la lentitud de estos dispositivos se pretende aprovechar la gran capacidad de almacenamiento para mantener una cantidad de información muy alta organizada de forma que el acceso a una clave sea lo más rápido posible.

Como se ha visto anteriormente existen métodos y estructuras de datos que permiten realizar una búsqueda dentro de un conjunto alto de datos en un tiempo de orden O(log2n). Así tenemos el caso de los árboles binarios AVL.¿Por qué no usarlos para organizar a través de ellos el índice de una base de datos?la respuesta aparece si estudiamos más de cerca el problema de acceso a memoria externa.Mientras que en memoria interna el tiempo de acceso a n datos situados en distintas partes de la memoria es independiente de las direcciones que estos ocupen(n*cte donde cte es el tiempo de acceso a 1 dato),en memoria externa es fundamental el acceder a datos situados en el mismo bloque para hacer que el tiempo de ejecución disminuya debido a que el tiempo depende fuertemente del tiempo de acceso del dispositivo externo,si disminuimos el número de accesos a disco lógicamente el tiempo resultante de ejecución de nuestra búsqueda se ve fuertemente recortado.Por consiguiente,si tratamos de construir una estructura de datos sobre disco es fundamental tener en cuenta que uno de los factores determinantes en el tiempo de ejecución es el número total de accesos,de forma que aunque dicho n&uacite;mero pueda ser acotado por un orden de eficiencia es muy importante tener en cuenta el número real ya que el tiempo para realizar un acceso es suficientemente alto como para que dos algoritmos pese a tener un mismo orden,puedan tener en un caso un tiempo real de ejecución aceptable y en otro inadmisible.

De esta forma,si construimos un árbol binario de búsqueda equilibrado en disco,los accesos a disco serán para cargar en memoria uno de los nodos,es decir,para poder llevar a memoria una cantidad de información suficiente como para poder decidir entre dos ramas.Los árboles de múltiples ramas tienen una altura menor que los árboles binarios pues pueden contener más de dos hijos por nodo,además de que puede hacerse corresponder los nodos con las páginas en disco de forma que al realizar un único acceso se leen un número alto de datos que permiten elegir un camino de búsqueda no entre dos ramas,sino en un número considerablemente mayor de ellas.Además,este tipo de árboles hace más fácil y menos costoso conseguir equilibrar el árbol.

DEFINICIÓN:

Los B-árboles son árboles cuyos nodos pueden tener un número múltiple de hijos tal como muestra el esquema de uno de ellos en la figura 1. 

Como se puede observar en la figura 1,un B-árbol se dice que es de orden m si sus nodos pueden contener hasta un máximo de m hijos.En la literatura también aparece que si un árbol es de orden m significa que el mínimo número de hijos que puede tener es m+1(m claves).Nosotros no la usaremos para diferenciar el caso de un número máximo par e impar de claves en un nodo.

El conjunto de claves que se sitúan en un nodo cumplen la condición:

INSERCIÓN EN UN B-ÁRBOL:

Para insertar una nueva clave usaremos un algoritmo que consiste en dos pasos recursivos:

1. Buscamos la hoja donde debieramos encontrar el valor de la clave de una forma totalmente paralela a la búsqueda de ésta tal como comentabamos en la sección anterior(si en esta búsqueda encontramos en algun lugar del árbol la clave a insertar,el algoritmo no debe hacer nada más).Si la clave no se encuentra en el árbol habremos llegado a una hoja que es justamente el lugar donde debemos realizar esa inserción.
2. Situados en un nodo donde realizar la inserción si no está completo,es decir,si el número de claves que existen es menor que el orden menos 1 del árbol,el elemento puede ser insertado y el algoritmo termina.En caso de que el nodo esté completo insertamos la clave en su posición y puesto que no caben en un único nodo dividimos en dos nuevos nodos conteniendo cada uno de ellos la mitad de las claves y tomando una de éstas para insertarla en el padre(se usará la mediana).Si el padre está también completo,habrá que repetir el proceso hasta llegar a la raíz.En caso de que la raíz esté completa,la altura del árbol aumenta en uno creando un nuevo nodo raíz con una única clave.

BORRADO EN UN B-ÁRBOL.

La idea para realizar el borrado de una clave es similar a la inserción teniendo en cuenta que ahora,en lugar de divisiones,realizamos uniones.Existe un problema añadido,las claves a borrar pueden aparecer en cualquier lugar del árbol y por consiguiente no coincide con el caso de la inserción en la que siempre comenzamos desde una hoja y propagamos hacia arriba.La solución a esto es inmediata pues 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.

Las operaciones a realizar para poder llevar a cabo el borrado son por tanto:

1. 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.
2. 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.

En definitiva,el algoritmo nos queda como sigue:

1. Localizar el nodo donde se encuentra la clave.
.
2. Si el nodo localizado no es una hoja,intercambiar el valor de la clave localizada con el valor de la clave más a la izquierda del hijo a la derecha.En definitiva colocar la clave a borrar en una hoja.Hacemos nodo actual igual a esa hoja.
3. Borrar la clave.
4. Si el nodo actual contiene al menos el mínimo de claves como para seguir siendo un B-árbol,fin.
5. Si el nodo actual tiene un número menor que el mínimo:
1. Si un hermano tiene más del mínimo de claves,redistribución y fin.
2. Si ninguno de los hermanos tiene más del mínimo,unión de dos nodos junto con la clave del padre y vuelta al paso 4 para propagar el borrado de dicha clave(ahora en el padre).