Una estructura de árbol es un algoritmo para colocar y ubicar archivos (llamados registros o claves) en una base de datos. El algoritmo encuentra datos tomando decisiones repetidamente en puntos de decisión llamados nodos. Un nodo puede tener tan solo dos ramas (también llamadas secundarias) o hasta varias docenas. La estructura es sencilla, pero en términos de la cantidad de nodos e hijos, un árbol puede ser gigantesco.
En un árbol, los registros se almacenan en lugares llamados hojas. Este nombre se deriva del hecho de que los registros siempre existen en los puntos finales; no hay nada más allá de ellos. El punto de partida se llama raíz. El número máximo de hijos por nodo se denomina orden del árbol. El número máximo de operaciones de acceso necesarias para alcanzar el registro deseado se llama profundidad. En algunos árboles, el orden es el mismo en todos los nodos y la profundidad es la misma para todos los registros. Se dice que este tipo de estructura está equilibrada. Otros árboles tienen diferentes números de hijos por nodo y diferentes registros pueden encontrarse a diferentes profundidades. En ese caso, se dice que el árbol tiene una estructura asimétrica o desequilibrada.
La ilustración muestra tres ejemplos de estructuras de árboles. (Tenga en cuenta que las representaciones están al revés en comparación con las plantas de árboles reales). Las estructuras A y B están equilibradas y la estructura C está desequilibrada. Las raíces están en la parte superior y están representadas por flechas rojas y líneas rojas. Los nodos se muestran como puntos grises. Los niños son líneas negras continuas. Las hojas están en la parte inferior y están representadas por puntos verdes. A medida que el proceso avanza hacia las hojas y se aleja de la raíz, los niños pueden ramificarse desde un nodo, pero los niños nunca se fusionan en un nodo.
En un árbol práctico, puede haber miles, millones o miles de millones de nodos, hijos, hojas y registros. No todas las hojas contienen necesariamente un registro, pero más de la mitad sí. Una hoja que no contiene datos se llama nula. Los árboles que se muestran aquí son lo suficientemente simples como para representarlos en dos dimensiones, pero con algunas bases de datos grandes, se necesitan tres dimensiones para representar claramente la estructura.
Consulte también árbol binario, árbol B, árbol M, árbol cuádruple, árbol de extensión y árbol X.