Interfaz Grafica

B-ÁRBOLES

________________________________________

1. INTRODUCCIÓN.

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.

2. B-ÁRBOLES.

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:

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:

• Todos los nodos excepto la raíz tienen al menos E((m-1)/2) claves.Lógicamente para los nodos interiores eso implica que tienen al menos E((m+1)/2) hijos.

• Todas las hojas están en el mismo nivel.

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.

BÚSQUEDA EN UN B-ÁRBOL.

Localizar una clave en un B-árbol

...