Árbol-B

De Wikipedia, la enciclopedia libre

Un árbol B+ simple (una variación del árbol B) que enlaza los elementos 1 al 7 a valores de datos d₁-d₇. Note la lista enlazada (en rojo) que permite el recorrido de los elementos en orden.

En las ciencias de la computación, los árboles-B ó B-árboles son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Los árboles B mantienen los datos ordenados y las inserciones y eliminaciones se realizan en tiempo logarítmico amortizado.

La idea tras los árboles-B es que los nodos internos deben tener un número variable de nodos hijo dentro de un rango predefinido. Cuando se inserta o se elimina un dato de la estructura, la cantidad de nodos hijo varía dentro de un nodo. Para que siga manteniéndose el número de nodos dentro del rango predefinido, los nodos internos se juntan o se parten. Dado que se permite un rango variable de nodos hijo, los árboles-B no necesitan rebalancearse tan frecuentemente como los árboles binarios de búsqueda auto-balanceables, pero por otro lado pueden desperdiciar memoria, porque los nodos no permanecen totalmente ocupados. Los límites superior e inferior en el número de nodos hijo son definidos para cada implementación en particular. Por ejemplo, en un árbol-B 2-3 (A menudo simplemente llamado árbol 2-3), cada nodo sólo puede tener 2 o 3 nodos hijo.

Un árbol-B se mantiene balanceado porque requiere que todos los nodos hoja se encuentren a la misma altura.

Los árboles B tienen ventajas sustanciales sobre otras implementaciones cuando el tiempo de acceso a los nodos excede al tiempo de acceso entre nodos. Este caso se da usualmente cuando los nodos se encuentran en dispositivos de almacenamiento secundario como los discos rígidos. Al maximizar el número de nodos hijo de cada nodo interno, la altura del arbol decrece, las operaciones para balancearlo se reducen, y aumenta la eficiencia. Usualmente este valor se coloca de forma tal que cada nodo ocupe un bloque de disco, o un tamaño análogo en el dispositivo. Mientras que los árboles B 2-3 pueden ser útiles en la memoria principal, y además más fáciles de explicar, si el tamaño de los nodos se ajustan para caber en un bloque de disco, el resultado puede ser un árbol B 129-513.

Los creadores del árbol B, Rudolf Bayer y Ed McCreight, no han explicado el significado de la letra B de su nombre. Se cree que la B es de balanceado, dado que todos los nodos hoja se mantienen al mismo nivel en el árbol. La B también puede referirse a Bayer, o a Boeing, porque sus creadores trabajaban en el Boeing Scientific Research Labs en ese entonces.

[editar] Estructura de los nodos

Cada elemento de un nodo interno actúa como un valor separador, que lo divide en subárboles. Por ejemplo, si un nodo interno tiene tres nodos hijo, debe tener dos valores separadores o elementos a₁ y a₂. Todos los valores del subárbol izquierdo deben ser menores a a₁, todos los valores del subárbol del centro deben estar entre a₁ y a₂, y todos los valores del subárbol derecho deben ser mayores a a₂.

Los nodos internos de un árbol B, es decir los nodos que no son hoja, usualmente se representan como un conjunto ordenado de elementos y punteros a los hijos. Cada nodo interno contiene un máximo de U hijos y, con excepción del nodo raíz, un mínimo de L hijos. Para todos los nodos internos exceptuando la raíz, el número de elementos es uno menos que el número de punteros a nodos. El número de elementos se encuentra entre L-1 y U-1. El número U debe ser 2L o 2L-1, es decir, cada nodo interno está por lo menos a medio llenar. Esta relación entre U y L implica que dos nodos que están a medio llenar pueden juntarse para formar un nodo legal, y un nodo lleno puede dividirse en dos nodos legales (si es que hay lugar para subir un elemento al nodo padre). Estas propiedades hacen posible que el árbol B se ajuste para preservar sus propiedades ante la inserción y eliminación de elementos.

Los nodos hoja tienen las misma restricción sobre el número de elementos, pero no tienen hijos, y por tanto carecen de punteros.

El nodo raíz tiene límite superior de número de hijos, pero no tiene límite inferior. Por ejemplo, si hubiera menos de L-1 elementos en todo el árbol, la raíz sería el único nodo del árbol, y no tendría hijos.

Un árbol B de altura n+1 puede contener U veces por elementos más que un árbol B de profundidad n, pero el costo en la búsqueda, inserción y eliminación crece con la altura del árbol. Como todo árbol balanceado, el crecimiento del costo es más lento que el del número de elementos.

Algunos árboles balanceados guardan valores sólo en los nodos hoja, y por lo tanto sus nodos internos y nodos hoja son de diferente tipo. Los árboles B guardan valores en cada nodo, y pueden utilizar la misma estructura para todos los nodos. Sin embargo, como los nodos hoja no tienen hijos, una estructura especial para éstos mejora la performance.

[editar] Algoritmos

[editar] Búsqueda

La búsqueda es similar a la de los árboles binarios. Se empieza en la raíz, y se recorre el árbol hacia abajo, escogiendo el sub-nodo de acuerdo a la posición relativa del valor buscado respecto a los valores de cada nodo. Típicamente se utiliza la búsqueda binaria para determinar esta posición relativa.

[editar] Inserción

Todas las inserciones se hacen en los nodos hoja.

Realizando una búsqueda en el árbol, se halla el nodo hoja en el cual debería ubicarse el nuevo elemento.

Si el nodo hoja tiene menos elementos que el máximo número de elementos legales, entonces hay lugar para uno más. Inserte el nuevo elemento en el nodo, respetando el orden de los elementos.

De otra forma, el nodo debe ser dividido en dos nodos. La división se realiza de la siguiente manera: se escoge el valor medio entre los elementos del nodo y el nuevo elemento. Los valores menores que el valor medio se colocan en el nuevo nodo izquierdo, y los valores mayores que el valor medio se colocan en el nuevo nodo derecho; el valor medio actúa como valor separador. El valor separador se debe colocar en el nodo padre, lo que puede provocar que el padre sea dividido en dos, y así sucesivamente. Si las divisiones de nodos suben hasta la raíz, se crea una nueva raíz con un único elemento como valor separador, y dos hijos. Es por esto que la cota inferior del tamaño de los nodos no se aplica a la raíz. El máximo número de elementos por nodo es U-1. Así que debe ser posible dividir el número máximo de elementos U-1 en dos nodos legales. Si este número fuera impar, entonces U=2L, y cada uno de los nuevos nodos tendrían (U-2)/2 = L-1 elementos, y por lo tanto serían nodos legales. Si U-1 fuera par, U=2L-1, así que habría 2L-2 elementos en el nodo. La mitad de este número es L-1, que es el número mínimo de elementos permitidos por nodo.

[editar] Eliminación

La eliminación de un elemento es directa si no se requiere corrección para garantizar sus propiedades. Hay dos estrategias populares para eliminar un nodo de un árbol B.

localizar y eliminar el elemento, y luego corregir, o
hacer una única pasada de arriba a abajo por el árbol, pero cada vez que se visita un nodo, reestructurar el árbol para que cuando se encuentre el elemento a ser borrado, pueda eliminarse sin necesidad de continuar reestructurando

Se pueden dar dos problemas al eliminar elementos: primero, el elemento puede ser un separador de un nodo interno. Segundo, puede suceder que al borrar el elemento número de elementos del nodo quede debajo de la cota mínima. Estos problemas se tratan a continuación en orden.

[editar] Eliminación en un nodo hoja

Busque el valor a eliminar.
Si el valor se encuentra en un nodo hoja, se elimina directamente del nodo, posiblemente dejándolo con muy pocos elementos; por lo que se requerirán cambios adicionales en el árbol.

[editar] Eliminación en un nodo interno

Cada elemento de un nodo interno actúa como valor separador para dos subárboles, y cuando ese elemento es eliminado, pueden suceder dos casos. En el primero, tanto el hijo izquierdo como el derecho tienen el número mínimo de elementos, L-1. Pueden entonces fundirse en un único nodo con 2L-2 elementos, que es un número que no excede U-1 y por lo tanto es un nodo legal. A menos que se sepa que este árbol B en particular no tiene datos duplicados, también se debe eliminar el elemento en cuestión (recursivamente) del nuevo nodo.

En el segundo caso, uno de los dos nodos hijos tienen un número de elementos mayor que el mínimo. Entonces se debe hallar un nuevo separador para estos dos subárboles. Note que el mayor elemento del árbol izquierdo es el mayor elemento que es menor que el separador. De la misma forma, el menor elemento del subárbol derecho es el menor elemento que es mayor que el separador. Ambos elementos se encuentran en nodos hoja, y cualquiera de los dos puede ser el nuevo separador.

Si el valor se encuentra en un nodo interno, escoja un nuevo separador (puede ser el mayor elemento del subárbol izquierdo o el menor elemento del subárbol derecho), elimínelo del nodo hoja en que se encuentra, y reemplace el elemento a eliminar por el nuevo separador.
Como se ha eliminado un elemento de un nodo hoja, se debe tratar este caso de manera equivalente.

[editar] Rebalanceo después de la eliminación

Si al eliminar un elemento de un nodo hoja el nodo se ha quedado con menos elementos que el mínimo permitido, algunos elementos se deben redistribuir. En algunos casos el cambio lleva la deficiencia al nodo padre, y la redistribución se debe aplicar iterativamente hacia arriba del arbol, quizá incluso hasta a la raíz. Dado que la cota mínima en el número de elementos no se aplica a la raíz, el problema desaparece cuando llega a ésta.

La estrategia consiste en hallar un hermano para el nodo deficiente que tenga más del mínimo número de elementos y redistribuir los elementos entre los hermanos para que todos tengan más del mínimo. Esto también cambia los separadores del nodo padre.

Si el nodo hermano inmediato de la derecha del nodo deficiente tiene más del mínimo número de elementos, escoja el valor medio entre el separador y ambos hermanos como nuevo separador y colóquelo en el padre.
Redistribuya los elementos restantes en los nodos hijo derecho e izquierdo.
Redistribuya los subárboles de los dos nodos . Los subárboles son trasplantados por completo, y no se alteran si se mueven a un otro nodo padre, y esto puede hacerse mientras los elementos se redistribuyen.
Si el nodo hemano inmediato de la derecha del nodo deficiente tiene el mínimo número de elementos, examine el nodo hermano inmediato de la izquierda.
Si los dos nodos hemanos inmediatos tienen el mínimo número de elementos, cree un nuevo nodo con todos los elementos del nodo deficiente, todos los elementos de uno de sus hermanos, colocando el separador del padre entre los elementos de los dos nodos hermanos fundidos.
Elimine el separador del padre, y reemplace los dos hijos que separaba por el nuevo nodo fundido.
Si esa acción deja al número de elementos del padre por debajo del mínimo, repita estos pasos en el nuevo nodo deficiente, a menos que sea la raíz, ya que no tiene cota mínima en el número de elementos.