Árbol B*
Una estructura en árbol es un algorítmo que permite colocar y localizar claves y registros en una base de datos. El algorítmo 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 órden del árbol. El máximo número de operaciones de acceso requeridas para alcanzar una clave se denomina la altura. En algunos árboles, el órden 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 arbol 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 raices estan 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 explícitamente definido). El algorítmo para manejo de los árboles-B minimiza el número de veces que hay que accesar 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 (llamdas 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:
