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.
En resumen,los árboles con múltiples hijos hacen que el mantenimiento de índices
en memoria externa sea mucho más eficiente y es justamente éste el motivo por el que
este tipo de árboles han sido los que tradicionalmente se han usado para el mantenimiento
de índices en sistemas de bases de datos.Lógicamente,aunque este tipo de estructuras
sean más idóneas para mantener grandes cantidades de datos en almacenamiento externo
es posible construirlas de igual forma en memoria principal,y por consiguiente pueden ser mantenidas en
memoria (mediante el uso de punteros por ejemplo)al igual que las que hemos estudiado hasta ahora.
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:
de forma que los elementos que cuelgan del primer hijo tienen una clave con valor menor que K1,los que cuelgan del segundo tienen una clave con valor mayor que K1 y menor que K2,etc...Obviamente,los que cuelgan del último hijo tienen una clave con valor mayor que la última clave(hay que tener en cuenta que el nodo puede tener menos de m hijos y por consiguiente menos de m-1 claves).
Para que un árbol sea B-árbol además deberá cumplir lo siguiente:
El hecho de que la raíz pueda tener menos descendientes se debe a que si el crecimiento del árbol hace que la raíz se divida en dos hay que permitir dicha situación para que los nuevos nodos mantengan esa propiedad.En el caso de que eso ocurra en un nodo interior distinto a la raíz se soluciona propagando hacia arriba;lógicamente esta operación no se puede realizar en el caso de raíz.
Por otro lado,con el hecho de que los nodos interiores tengan un número mínimo
de descendientes aseguramos que en el nivel n(nivel 1 corresponde a la raíz)haya
un mínimo de 2En-1((m+1)/2)(el 2 es el mínimo de hijos de la raíz
y E((m+1)/2) el mínimo para los demás)y teniendo en cuenta que un árbol
con N claves tiene N+1 descendientes en el nivel de las hojas,podemos establecer la
siguiente desigualdad:
Resolviendo:
que nos da una cota superior del número de nodos a recorrer para localizar un elemento
en el árbol.
Localizar una clave en un B-árbol es una operación simple pues consiste en situarse 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.En definitiva,los pasos a seguir son los siguientes:
Para insertar una nueva clave usaremos un algoritmo que consiste en dos pasos recursivos:
En la figura 2 podemos observar el efecto de insertar una nueva clave en un nodo que está
lleno.
Podemos realizar una modificación al algoritmo de forma que se retrase al máximo el momento de romper un nodo en dos.Con ello podríamos vernos beneficiados por dos razones fundamentalmente:
La forma más sencilla de realizar esta modificación es que en el caso de que tengamos que realizar esa división,antes de llevarla a cabo,comprobemos si los hermanos adyacentes tienen espacio libre de forma que si alguno de ellos lo tiene se redistribuyen las claves que se encuentran en el nodo actual más las de ese hermano m&as la clave que los separa(que se encuentra en el padre)más la clave a insertar de forma que en el padre se queda la mediana y las demás quedan distribuidas entre los dos nodos.
En la figura 3 podemos observar el efecto de insertar una nueva clave en un nodo que está
lleno pero con redistribución.
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:
En definitiva,el algoritmo nos queda como sigue:
AB Crear0(int ne)
{
AB raiz;
raiz = (AB)malloc(sizeof(struct AB));
if (raiz == NULL)
error("Memoria Insuficiente.");
raiz->n_etiquetas = ne;
for (int i=1; i<=(ne+1); i++) {
raiz->hijos[i] = NULO;
}
return(raiz);
}
AB Crear(int ne, int eti[])
{
AB raiz;
raiz = (AB)malloc(sizeof(struct AB));
if (raiz == NULL)
error("Memoria Insuficiente.");
raiz->n_etiquetas = ne;
for (int i=1; i<=(ne+1); i++) {
raiz->hijos[i] = NULO;
}
for (int i=1; i<=lenght(eti[]); i++) {
raiz->etiquetas[i] = eti[i];
}
return(raiz);
}
int Buscar(int eti, int *nod, int *pos)
{
int i,l;
l = lenght(nod->etiquetas[]);
for(i=0;inod->etiquetas[i];i++)
;
*pos = i;
if(*posetiquetas[*pos])
return 1;
else;
return 0;
}
int BuscarNodo(int eti, int *nod, int *pos)
{
int i=0, enc;
enc = Buscar(eti,&nod,&pos);
if (enc == 1)
return 1;
do {
if (etietiquetas[i] && nod->hijos[i]!=NULO)
enc = BuscarNodo(eti,&nod->hijos[i],&pos);
else
if ((etietiquetas[i+1]||nod->etiquetas[i+1]==-1)&&nod->hijos[i+1]!=-1)
enc = BuscarNodo(eti,&nod->hijos[i+1],&pos);
i++;
} while (ietiquetas[]) && enc==0);
return (enc);
}