En los archivos indexados vistos hasta ahora, el recorrido de la tabla de índices es secuencial, con los inconvenientes que ya comentamos que este tipo de accesos tiene. No obstante, existe una técnica de indexación mucho más eficiente que la indexación secuencial, la indexación por árboles, que reduce el tiempo en las búsquedas de manera significativa. En este post voy a explicar la citada técnica.

Con acceso secuencial, cuando busquemos un dato, tendremos que recorrer el fichero de índices de manera secuencial hasta dar con el buscado, donde obtendremos la dirección de memoria de comienzo del registro en el archivo de datos. Como las tablas de índices son mucho menos pesadas que los ficheros con todos los datos, tenemos una mejora considerable usando los índices, aunque la búsqueda en la tabla de estos sea secuencial.

Cambiando la tabla de indices de acceso secuencial por una organización de los indices en un árbol de datos, vamos a conseguir acceder a nuestro indice mucho más rápidamente. Este tipo de estructuras están especialmente indicadas para acelerar las búsquedas, pero veamos como lo hace.

La estructura de árbol

En realidad, con las técnicas de indexación, estamos creando estructuras de datos que nos van a ayudar a trabajar con estos. Con la indexación secuencial creábamos pares clave – dirección que tenían una estructura lineal, uno detrás de otro, ordenados de acuerdo a algún criterio. Por ejemplo, en el caso del fichero proveedores de nuestro amigo Antonio, usábamos como clave el nombre del proveedor, y teníamos la estructura ordenada alfabéticamente en sentido creciente.

Pues bien, la principal característica de las estructuras de arboles, es que no son lineales. Es decir, después de un elemento no viene otro y luego otro y así sucesivamente, sino que a continuación de un elemento, pueden ir varios, uno o ninguno.

En la figura siguiente puedes apreciar la diferencia entre ambas estructuras de datos:

Estructura secuencial vs estructura de árbol

Algunos términos interesantes

Para explicar como funciona la estructura de árbol, resulta conveniente introducir una serie de términos comúnmente empleados. Además, casi seguro que toda la documentación que podéis encontrar sobre este tema, usará esta terminología.

  • Nodo: Cada elemento de la estructura de datos se le denomina nodo.
  • Nodo Padre: Como explicaba antes, y como se puede apreciar en la figura de más arriba, de un nodo pueden salir uno, varios o ningún nodo. Pues bien, un nodo padre es aquel del que sale al menos un nodo, sería el padre para ese nodo.
  • Nodo raíz: Es el primer nodo de la estructura, el único que no tiene un nodo Padre.
  • Nodo hoja: Aquel nodo que no tiene hijos

Después de esta breve explicación, creo que es fácilmente entendible porque a estas estructuras de datos se las denomina de árboles. Cada nodo es como un nudo del árbol, del que nacen ramas, hasta llegar a otro nudo, del que nacen más ramas, y así sucesivamente.

Así, para un nodo dado, este tendría un nodo padre que es el que apunta a nuestro nodo, y podría tener varios nodos hijos que serían aquellos a los que apunta.

¡¡Ojo!!, un nodo sólo puede tener un nodo padre (con la salvedad del nodo raíz que no tiene nodo padre), sino entraríamos en estructura cíclicas y esas ya no son estructuras de árboles.

Ahora, que ya sabemos lo que es una estructura de árbol, voy a aprovechar para introducir ciertos conceptos adicionales que nos va a hacer falta conocer, y que pueden apreciarse en la siguiente figura:

Estructura de arbol

  • Nivel: El nivel de un nodo será los padres que tiene por encima hasta llegar al nodo raíz, incluido este último. Es decir, los saltos que tendría que dar hasta llegar al inicio del árbol.
  • Profundidad del árbol: El máximo nivel del árbol.
  • Orden: Número máximo de hijos que puede tener un nodo.

La indexación por árboles

Ahora que conocemos la estructura de los árboles de datos, podemos entender como ayudan a acelerar las búsquedas.  En realidad, cada vez que llegamos a un nodo, tomaremos una decisión sobre a que nodo hijo movernos. De esta forma, no tenemos que recorrer todos los nodos del árbol hasta encontrar lo que buscamos.

El orden de un árbol es un factor crítico. Normalmente, vamos a querer que sea un número pequeño, para mantener la estructura sencilla, y hacer crecer el árbol en profundidad en lugar de a lo ancho. Los árboles de orden bajo muestran mejor comportamiento en las búsquedas, que es la principal aplicación de estas estructuras de datos. Los árboles binarios (orden 2) son ampliamente utilizados en BBDD obteniendo mejoras notables en los procesos de búsqueda.

NOTA:

Este post es parte de la colección “Arquitectura de Datos” que reproduce los apuntes de la clase que imparto sobre el tema en ESIC. Puedes ver el índice de esta colección aquí.