Árbol B*
Una estructura en árbol es un algorítmo que permite colocar y localizar claves y registros en una base de datos. El algoritmo localiza datos haciendo selecciones repetidas en puntos de decisión denominados nodos. Un nodo puede tener un mínimo de dos ramas (llamadas también hijos), o muchas docenas de ellas. La estructura es sencilla, pero en términos del número de nodos e hijos, un árbol puede ser gigante.
En un árbol, las clases se almacenan en locaciones denominada hojas. Este nombre deriva del hecho de que en los puntos finales del árbol siempre existirán claves. El punto de incio se denomina raíz. El máximo número de hijos por nodo se denomina el orden del árbol. El máximo número de operaciones de acceso requeridas para alcanzar una clave se denomina la altura. En algunos árboles, el orden es el mismo en todos los nodos y la altura es la misma para todas las claves. Se dice que este tipo de estructura está balanceada. Otro árboles pueden tener diferentes números de hijos por nodos y diferentes claves pueden estar a diferente altura. En esta caso se dice que el árbol tiene una estructura no balanceada o asimétrica.
La ilustración muestra 3 ejemplos de las estructuras de árbol. Las estructuras A y B están balanceadas y la estructura C no lo está. Las raíces están en la parte superior y están representadas por flechas y líneas rojas. Los nodos se muestran como puntos grises. Los hijos son las líneas negras y la hojas están en los extremos representadas por puntos verdes. Conforme el proceso avanza hacia las hojas y se aleja de la raíz, los hijos puede ramificarse y separarse del nodo, pero nunca se mezclarán con los nodos.
En un árbol de la vida real, pueden existir miles, millones o billones de nodos, hijos, hojas y claves. No todas las hojas necesariamente contendrán claves, pero más de la mitad lo harán. Una hoja que no contiene claves se denomina "nula". Los árboles mostrados aquí son lo suficientemente simples para ser representados en dos dimensiones, pero en algunas grandes bases datos se necesitan tres dimensiones para representar claramente la estructura.
Arboles-b (B-tree)
Un árbol-B (B-tree) es un método para almacenar y localizar claves y registros en una base de datos. (El significado de la letra B no ha sido explicitamente definido). El algoritmo para manejo de los árboles-B minimiza el número de veces que hay que acceder un medio magnético de almacenamiento para recuperar los registros requeridos acelerando, en consecuencia, el proceso de recuperación.
Los árboles-B son los más convenientes cuando los puntos de decisión, denominados nodos, están localizados en un disco duro y no en memoria RAM. Toma mucho más tiempo accesar un elemento de dato desde una unidad de disco, en comparación con el acceso a memoria RAM, por cuanto la unidad de disco tiene partes mecánicas las cuales leen y escriben data mucho más lento que los medios meramente electrónicos. Los árboles-B ahorran tiempo usando nodos con muchas ramas (llamadas hijos), comparados con los árboles binarios, en el cuales cada nodo tiene solo dos hijos. Cuando existen muchos hijos por nodo, si se definen solo dos hijos por nodo, toma más tiempo localizar las claves por cuanto hay que recorrer más nodos. Un ejemplo simplificado de este principio se muestra en el siguiente gráfico:
En el primer gráfico se definen dos hijos por nodo y toma tres accesos localizar un registro. En el segundo gráfico, donde hay más hijos por nodo, toma 2 accesos localizar el mismo registro.
En un árbol, las claves se almacenan en locaciones denominadas hojas. Este nombre deriva del hecho de que siempre existirán claves en los puntos finales. El máximo número de hijos por nodo es el orden del árbol. El número de accesos a discos requeridos para localizar una clave es la altura. En el gráfico anterior, la imagen ubicada a la izquierda muestra un árbol binario para localizar una clave particular en un conjunto de 8 hojas. La imagen a la derecha muestra un árbol-B de orden 3 para localizar un registro particular en un conjunto de 8 hojas (la novena hoja no está ocupada y se denomina "nula"). El árbol binario a la izquierda tiene una altura de 4; el árbol-B a la derecha tiene una altura de 3. Claramente, el árbol-B permite localizar más rápidamente una clave en particular. La contrapartida es que el proceso de decisión en cada nodo es más complicado en un árbol-B que en un árbol binario. Se requiere un programa más sofisticado para ejecutar las operaciones sobre el árbol-B; pero como los programas residen en la memoria RAM, el proceso en general se ejecuta más rápido.
En la práctica, en un árbol-B pueden existir miles, millones o billones de claves. No todas las hojas contendrán necesariamente claves, pero al menos la mitad de ellas lo harán. La diferencia en altura entre los esquemas de un árbol binario y de un árbol-B es más marcada en bases de datos reales, que la ilustrada en el ejemplo anterior, porque los árboles de la vida real son de orden superior (32, 64, 128 o más nodos). Depending del número de claves en la base de datos, la altura del árbol-B puede no cambiar. Si agregamos un gran número de claves aumentaremos la altura del árbol-B; si eliminamos un gran número de claves reduciremos la altura del árbol-B. Esto garantiza que el árbol-B funciona de manera óptima en relación con el número de claves que contiene.
Los árboles-B son árboles balanceados optimizados para situaciones en las cuales parte o todo el árbol debe ser mantenido en unidades de almacenamiento secundarias, tales como los discos magnéticos. Como los acceso a disco son operaciones que consumen tiempo, un árbol-B trata de minimizar el número de accesos a disco. Por ejemplo, un árbol-B con altura 2 y un factor de ramas de 1001 puede almacenar cerca de un billón de claves, pero requerirá tan solo dos accesos a disco para ubicar cualquiera de sus nodos.
