Recorrido de preorden de árboles

Una de las características exclusivas de nuestra base de datos worldCities es el uso del recorrido de árboles en la tabla features_hierarchy (jerarquía).
(Si actualmente no cuenta con worldCities pero quiere ver cómo funciona en la práctica, descargue gratis la demo de worldCities y cheque las consultas al final de este artículo)

Relación padre-hijo

Antes de empezar con el recorrido de árboles, demos un vistazo a la clásica relación padre-hijo, que la mayoría de los desarrolladores conocen bien. Una lista de los continentes y macro-regiones sgún las Naciones Unidas podría representarse así, donde feature_id representa los hijos y parent_id los padres :

feature_idparent_idnombre
10Mundo
21África
32África Occidental
42África Oriental
52África del Norte
62África Central
72África Austral
81Américas
98Norteamérica
108América Latina y el Caribe
1110Sudamérica
1210Centroamérica
1310El Caribe
141Asia
.........

Es bastante sencillo buscar la lista de los continentes, por ejemplo. Sólo es necesario buscar en la base de datos todos los registros con parent_id=1 (Mundo) y el resultado es África, Américas, Asia, etc…

Si también se requieren las macro-regiones, se puede escribir otra consulta (o añadir un LEFT JOIN si prefiere usar una sola). Sin embargo, en caso de tener múltiples niveles de datos, rápidamente se puede volver complicado usar LEFT JOIN. Consultas individuales y recursión para cada nivel tampoco es muy eficiente.

Recorrido en profundidad de preorden de árboles

Con el recorrido de preorden de árboles, se añaden dos valores (izquierda y derecha) a cada registro.
simplemente se recorre el árbol de datos y asigna el valor izquierdo a cada registro hasta que se encuentra el final de una rama. En este caso, se asigna el valor derecho de dicho registro y se sigue con la rama siguiente. Puede parecer un poco confuso al principio, pero es más fácil entender el concepto viéndolo, como en la imagen siguiente, que muestra como se asignan los valores izquierdo y derecho de cada registro.

Recorrido en profundidad de preorden de árboles

En este ejemplo, empezamos con los valores izquierdos de Mundo, África y África Occidental. Ya que ese último registro se encuentra al final de su rama, le damos el valor derecho y seguimos con África Oriental, etc… Después de dar el valor derecho a África Austral, hacemos lo mismo con África y pasamos a Américas. Una vez que todos los continentes y regiones tengan sus valores izquierdo y derecho, sólo falta asignar el valor derecho (58) a Mundo.

Nuestra tabla de continentes y macro-regiones ahora se ve así, donde left contiene los valores de la izquierda y right los de la derecha:

feature_idparent_idleftrightnombre
10158Mundo
21213África
3234África Occidental
4256África Oriental
5278África del Norte
62910África Central
721112África Austral
811425Américas
981516Norteamérica
1081724América Latina y el Caribe
11101819Sudamérica
12102021Centroamérica
13102223El Caribe
1412637Asia
...............

¿Por qué es útil en la práctica? Para mí, la razón principal es que es muy fácil trabajar con múltiples níveles de datos usando una sola consulta, por lo tanto reduciendo la carga del servidor de la base de datos y acelerando el procesamiento, así como tener cógido más limpio.

Obtener todo lo que está abajo de cierto nodo

Al examinar los valores de iquierda y derecha, rápidamente se puede dar cuenta que:

  1. todos los registros abajo de un nodo tienen valores izquierdos (y derechos) superiores al valor izquierdo de dicho nodo;
  2. todos los registros abajo de un nodo tienen valores izquierdos (y derechos) inferiores al valor derecho de ese nodo.

Entonces, si por ejemplo necesitamos el registro de Américas y todos sus descendientes, tenemos que buscar los registros donde left está entre 14 y 25 (WHERE left BETWEEN 14 AND 25).
Para obtener únicamente los descendientes, buscamos lso registros donde left está entre 15 y 25 (WHERE left BETWEEN 15 AND 25).

Obtener el recorrido hacia abajo hasta cierto nodo

De la misma manera, si se necesita el recorrido hacia abajo hasta cierto nodo, sólo tiene que buscar registros con:

  1. un valor izquierdo inferior o igual al valor izquierdo de ese nodo;
  2. un valor derecho superior o igual al valor derecho de ese nodo.

Para obtener el recorrido hasta El Caribe, buscamos registros con left<=22 y right>=23 (WHERE left<=22 AND right>=23).
Si no necesitamos el registro del Caribe mismo, basta con eliminar el signo de igualdad y buscar registros donde left<22 y right>23 (WHERE left<22 AND right>23).

¿Cuántos descendientes tiene algún nodo?

Como último ejemplo de esta introducción rápida al recorrido de árboles, ¡vamos a contar!
El número de descendientes de un nodo se encuentra muy rápidamente con la sencilla fórmula:
(derecha – izquierda – 1) / 2

Conclusión

El recorrido de árboles es muy poderoso y fácil de uso para trabajar con múltiples níveles de datos y ramas enteras del árbol. Y como se habrá dado cuenta, sin importar que trabajemos con África o las Américas, que tiene un nivel más, ¡las consultas son iguales! No es necesario escribir consultas distintas dependiendo de la cantidad de subdivisiones o incluso del punto de partida en el árbol de datos.
Sin embargo, a veces tiene más sentido usar la clásica relación de padre-hijo, como por ejemplo cuando se necesitan únicamente el padre o hijos directos de un valor, en lugar de toda la ascendencia o descendencia, respectivamente. Por eso se pueden usar ambos métodos con nuestra base de datos worldCities.

En worldCities

Para ver cómo se usan los datos jerárquicos en la práctica, vea los ejemplos de consultas para worldCities. Algunas usan la relación clásica padre-hijo y otras el recorrido de preorden de árboles.