Estructuras Jerárquicas en SQL

O cómo representar árboles en bases de datos bi-dimensionales

Escrito por Matías Navarro Carter hace 1 semana
En: SQL / Patrones de Diseño
Lectura de 9 minuto(s).

SQL es un lenguaje poderoso, y los sistemas de bases de datos relacionales que lo utilizan son herramientas indispensables para todo desarrollador de Software. Incluso en esta nueva era del BigData, las bases de datos relacionales en SQL se han mantenido como vigentes, a pesar de la multiplicidad de nuevas tecnologías que han emergido en el nicho de las bases de datos.

Sin embargo, las limitantes de las bases de datos relacionales son conocidas. Al tener un diseño bi-dimensional de tablas (columnas, filas) no están diseñadas para guardar estructuras multidimensionales complejas, como árboles de jerarquía y otras similares.

Hace poco, en uno de los proyectos que estoy realizando, me topé con el requerimiento de un sistema de categorización dinámico y jerárquico. Zonas mayores daban lugar a zonas menores, y estás a su vez, a otras más pequeñas que ellas. El usuario debía tener la capacidad de modificar esa estructura a placer. Fue allí cuando, investigando, aprendí sobre los tres patrones de modelo de árbol jerarquico más famosos para bases de datos relaciones, cada uno con sus ventajas y desventajas.

Patrón Lista Adyacente (Adjacency List)

La lista adyacente es uno de los patrones más comunes para guardar datos de forma jerárquica en bases de datos relacionales. Básicamente, tienes lo siguiente:

id name parent
1 Comida
2 Fruta 1
3 Carne 1
4 Manzana 2
5 Naranja 2
6 Pera 2
7 Cerdo 3
8 Vacuno 3

A cada fila se le llama un nodo y cada nodo guarda el ID de su padre. Si el nodo no tiene padre, se asume que es un nodo raíz o root.

Operaciones Comunes

Para obtener la estructura de árbol de una lista adyacente, debes utilizar una función recursiva que ejecutará una query por cada nodo de tu tabla. Esta operación tiene un costo de n+1, el cual es el peor costo en desarrollo de software. Esta clase Repositorio de ejemplo muestra el método utilizando PDO:

<?php

use PDO;

/**
* Contiene métodos para consultas de una tabla de Lista Adyacente
* @author Matías Navarro Carter <mnavarro@option.cl>
*/
class AdjacencyListTreeRepository {

    /**
    * La clase PDO de PHP
    *
    * @var 
    */
    private $pdo;

    /**
    * TreeRepository Constructor
    */
    public function __construct(PDO $pdo)
    {
        $this->pdo = $pdo;
    }

    /**
    * Obtiene recursivamente los hijos de un nodo,
    * pudiendo reconstruir el árbol por completo.
    *
    * @param int $padre El nodo padre
    * @param int $level El nivel de indentación
    * @return void
    */
    public function getChildren($padre = null, $nivel = 0) { 
        // Esta parte obtiene los hijos de un padre.
        // Devolverá los nodos padre si es null.
        $stmt = $this->pdo->prepare(
            'SELECT title FROM tree WHERE parent="'.$padre.'";'
        );
        $stmt->execute();
        while ($row = $stmt->fetch()) {
            echo str_repeat(' -> ', $nivel).$row['name']."\n"; 
            // Buscamos los hijos de este hijo
            $this->getChildren($row['title'], $nivel+1); 
        } 
    }

}

El método getChildren() debiese devolver el árbol completo de esta forma:

Comida
 -> Fruta
 ->  -> Manzana
 ->  -> Naranja
 ->  -> Pera
 -> Carne
 ->  -> Vacuno
 ->  -> Cerdo

También puedes consultar por un nodo específico llamando getChildren($nodeId).

Por otro lado, para reconstruir el path o la ruta que lleva a cierto nodo (muy útil en contextos de breadcrumbs o navegación). La técnica es similar aunque el costo es el mismo. Sólo debemos añadir este método a nuestra clase:

<?php

//...

    /**
    * Devuelve un array de los nodos que comforman la ruta
    * hacia otro nodo.
    *
    * @param int $nodo
    * @return array
    */
    public function getPath($nodo)
    {
        $ruta = [];

        $stmt = $this->pdo->prepare(
            'SELECT parent FROM tree WHERE id="'.$nodo.'";'
        );
        $row = $stmt->fetch(PDO::FETCH_ASSOC);
        // Continuamos sólo hasta que lleguemos a un nodo sin padre.
        if ($row['parent'] !== null ) {
            $ruta[] = $row['parent'];
            $ruta = array_merge($this->getPath($row['parent']), $ruta);
        }
        // Devolvemos la ruta
        return $ruta;
    }

Si ejecutamos print_r($this->getPath(3)) que es el nodo de Vacuno, deberíamos tener el siguiente resultado:

Array 
( 
    [0] => Comida
    [1] => Carne
)

Para operaciones de escritura, en realidad lo único que hace falta es asociar un registro a un parent y todo funcionará automáticamente: un sencillo INSERT será suficiente.

Ventajas y Desventajas

Las ventajas de una Lista Adyacente son su simplicidad en términos de comprensión del patrón y también de su implementación. Por ello es uno de los patrones más usados para este tipo de situaciones. Además, tiene un bajo costo de escritura.

Sin embargo, su más grande desventaja es su gran costo (n+1) de lectura. Para reconstruir el árbol completo, debemos hacer una query por cada nodo. Para reconstruir la ruta a un nodo, debemos hacer una query por cada elemento dentro de la ruta. Mientras más crece tu árbol, más costoso se hace la lectura del mismo. Definitivamente no es un patrón recomendado cuando tu árbol es grande y cuando la frecuencia de lectura de datos es alta.

Patrón Ruta Materializada (Materialized Path)

La idea de este patrón, como su nombre lo dice, es materializar la ruta de un nodo dentro de un varchar en la base de datos, de la siguiente forma:

id name path
1 Comida /1
2 Fruta /1/2
3 Carne /1/3
4 Manzana /1/2/4
5 Naranja /1/2/5
6 Pera /1/2/6
7 Cerdo /1/3/7
8 Vacuno /1/3/8

Operaciones Comunes

Las operaciones de lectura se vuelven muy baratas. Para buscar los hijos de un nodo se puede hacer uso de LIKE. Veamos Fruta:

SELECT * FROM tree WHERE path LIKE "/1/2/%"

Aquella simple query debiese devolvernos todos los hijos de Fruta en un array.

Para reemplazar un item es muy sencillo también. Si quisieramos mover Manzana, Naranja y Pera como hijos directos de comida, esto es lo que podemos hacer.

UPDATE tree SET path = REPLACE(path, `/1/2`, `/1`) WHERE path LIKE "/1/2/%"

NOTA: Si piensas que LIKE es muy lento, tienes razón. Pero en este ejemplo en particular, la columna path debe estar indexada. Cuando se utiliza LIKE sin un % al inicio, SQL utiliza el índice, lo que lo hace más rápido.

Ventajas y Desventajas

Este patrón también es muy sencillo de aprender y aplicar, sin embargo, tiene limitaciones en cuanto a restaurar la estructura jerárquica del árbol. Si se realiza un ORDER BY a la columna path, el árbol no quedará bien ordenado. Sin embargo, algunas variantes se han propuesto para sobrepasar esta limitante, especialmente por aquellos de Drupal.

Aunque su velocidad de lectura es mucho más rápida que la de la Lista Adyacente, aún no es muy eficiente dado el uso que se hace de LIKE.

Quizás, diseñando una mejor forma de guardar el path para hacerlo susceptible al ORDER BY podría hacer que te beneficiaras mucho de esta forma de construir jerarquías. Con todo, requeriría el uso de preg_replace() para que luego de obtener los resultados puedas reconstruir el árbol.

Patrón Conjunto Anidado (Nested Set)

El patrón conjunto anidado es, sin duda alguna, mi favorito. Sin embargo, estás advertido: no es fácil de entender ni de explicar. Intentaré hacer mi mayor esfuerzo.

Esta es, con algunas variaciones, una típica tabla de Conjunto Anidado:

id name root parent lft rgt lvl
1 Comida 1 1 16 0
2 Fruta 1 1 2 9 1
3 Carne 1 1 10 15 1
4 Manzana 1 2 3 4 2
5 Naranja 1 2 5 6 2
6 Pera 1 2 7 8 2
7 Cerdo 1 3 11 12 2
8 Vacuno 1 3 13 14 2

Como puedes ver, el Conjunto Anidado guarda muchos datos acerca de tus nodos. Esto es para que sea más fácil reconstruir el árbol o realizar consultas muy específicas a gran velocidad.

Lo que más confunde a las personas al estudiar este patrón son los campos lft y rgt (no se usa left y right en SQL por ser palabras reservadas). Aquellos campos simulan un viaje ordenado por nuestro árbol, donde el inicio de un nodo se marca con lft mientras que su fin con rgt. Un nodo padre, por ejemplo, se considera terminado cuando sus hijos terminan.

Esta imagen muestra este "viaje lineal" a través de una jerarquía:

Operaciones Comunes

Cualquier operación común en Conjunto Anidado consta de una sola consulta muy compleja, pero muy barata, a excepción de la operación de actualización. Pero discutiremos eso más adelante.

Para obtener los hijos de un nodo en Conjunto Anidado, esta query es suficiente:

// Seleccionamos los campos que queremos
SELECT
    child.*

// Creamos dos alias de la misma tabla para no confundirnos
FROM
    tree child,
    tree parent
// Buscamos todos los nodos entre el principio y el fin de uno
WHERE
    child.lft BETWEEN parent.lft AND parent.rgt
    AND parent.id != child.id
    AND parent.id = :id;

Donde :id no es más que el id del nodo que queremos rescatar. Esta operación es extremadamente rápida. Luego, teniendo los récord en nuestro poder, podemos agruparlos utilizando el lvl y ordenarlos por lft de acuerdo al nodo root. Las posibilidades de consulta y ordenamiento son infinitas y muy eficientes.

Ventajas y Desventajas

Sin embargo, toda aquella velocidad y flexibilidad tiene un gran costo. Cada vez que se inserta un nuevo registro o se actualiza uno antiguo, dos queries muy complejas deben ser escritas, para recorrer la tabla completa actualizando los campos lft y rgt de los nodos afectados.

Librerías de Ayuda

Mucho de este trabajo ya ha sido hecho por muchas personas que han disponibilizado su trabajo en repositorios open source como Github. Por ejemplo, si utilizas Symfony, tienes stof/doctrine-extensions-bundle que utiliza la famosa librería gedmo/doctrine-extensions. En ella puedes encontrar anotaciones para entidades utlizando Nested Set, Materialized Path y un tipo que no revisamos (Closure Tree).

Es un tópico interesante de aprender, dando que en algún momento de tu carrera como desarrollador, te toparás con el desafío de crear estructuras jerárquicas dinámicas, i.e. sin tener que crear una nueva tabla por cada una.