Á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.