Nuevo enfoque a la búsqueda externa por medio de árboles multivía, e independientemente por M.Kauffman, su idea se basaba en un versátil nuevo tipo de estructura de datos llamado árbol B, que hace posible la búsqueda y la actualización en un fichero grande con eficiencia garantizada, en el peor de los casos utiliza comparativamente algoritmos simples.
Historia
Fue descubierto en 1970 por R.Bayer y E. McCreight como un nuevo enfoque a la búsqueda externa por medio de árboles multivía, e independientemente por M.Kauffman, su idea se basaba en un versátil nuevo tipo de estructura de datos llamado árbol B, que hace posible la búsqueda y la actualización en un fichero grande con eficiencia garantizada, en el peor de los casos utiliza comparativamente algoritmos simples.
¿Para que se utilizan los árboles B?
Los árboles B se utilizan para la creación de bases de datos. Así, una forma de implementar los índices de una base de datos relacional es a través de un árbol B. Otra aplicación dada a los árboles B es en la gestión del sistema de archivos del sistema operativo OS/2, con el fin de aumentar la eficacia en la búsqueda de archivos por los subdirectorios. También se conocen aplicaciones de los árboles B en sistemas de comprehensión de datos. Bastantes algoritmos de comprehensión utilizan árboles B para la búsqueda por clave de datos comprimido
Es costumbre denominar a los nodos de un árbol B, página. Cada nodo, cada página, es una unidad a la que se accede en bloque.
Características de los árboles B
- Todas las páginas hoja están en el mismo nivel.
- Todos las páginas internas, menos la raíz, tienen a lo sumo m ramas (no vacías) y como mínimo m/2 (redondeando al máximo entero) ramas.
- El número de claves en cada página interna es uno menos que el número de sus ramas, y estas claves dividen las de las ramas a manera de un árbol de búsqueda.
- La raíz tiene como máximo m ramas, puede llegar a tener hasta 2 y ninguna si el árbol consta de la raíz solamente.
Inserción
El método que se sigue para añadir un nueva clave en un árbol B es el siguiente:
- Primero se busca si la clave a insertar está ya en el árbol, para lo cual se sigue el camino de búsqueda.
- En el caso de que la clave no esté en el árbol, la búsqueda termina en un nodo hoja. Entonces la nueva clave se inserta en el nodo hoja. Más bien, se intenta insertar en el nodo hoja como a continuación estudiamos.
- De no estar lleno el nodo hoja, la inserción es posible en dicho nodo y termina la inserción de la clave.
- El comportamiento característico de los árboles B se pone de manifiesto ahora. De estar la hoja llena, la inserción no es posible en dicho nodo, entonces se divide el nodo (incluyendo virtualmente la clave nueva) en dos nodos en el mismo nivel del árbol, excepto la clave mediana que no se incluye en ninguno de los dos nodos, sino que sube en el árbol por el camino de búsqueda para a su vez insertarla en el nodo antecedente. Es por esto por lo que se dice que el árbol crece hacia arriba. En esta ascensión de claves medianas puede ocurrir que llegue al nodo raíz, entonces ésta se divide en dos nodos y la clave enviada hacia arriba se convierte en una nueva raíz. Esta es la forma de que el árbol B crezca en altura.
Búsqueda
Primero hay que situarse en el nodo raíz y si se ha encontrado ya la clave buscada, se termina; si por el contrario, no se encuentra ahí, se selecciona de entre los hijos el que se sitúe entre el de mayor y menor valor de la clave buscada y así se repetirá el proceso hasta
encontrarla.Si se llega a una hoja y no se puede continuar, es que la clave no se encuentra en el árbol.
Borrado
Es similar a la inserción , pero en lugar de realizar divisiones se realizan uniones, El principal problema es que la clave puede estar en cualquier parte del árbol, por lo tanto, si se encuentra no como hoja sino en el interior, se intercambia primero con el sucesor para
que quede como hoja y se pueda borrar.
Bibliografía
Capel, M. Y. J. (2015). Bases de datos relacionales y modelado de datos. IFCT0310. Madrid, España: Alianza Editorial.
Knuth, D. E. (2001). Clasificacion y Busqueda - Vol. III . Barcelona, España: Reverte.
Aguilar, L. J., Martínez, I. Z., coaut, Z. M. I., Sánchez, A. V., & Vieyra, G. Q. (1998). Estructura de datos . Madrid, España: McGraw-Hill Education.