Información jerárquica en bases de datos: lft y rgt.

Los contenidos de una web, y un sistema de información en general, se estructuran de forma lógica en categorías. Dichas categorías pueden ser englobadas por otras de rango superior, o por otro lado, pueden dar pie a otras categorías derivadas.
Dicha lógica debe ser plasmada en un diseño de base de datos. Una implementación intuitiva sería establecer relaciones padre - hijo en cada registro. Nos será sencilla de comprender, pero sus operaciones quizá sean complejas de implementar por los desarrolladores.


En Joomla 2.5 se utiliza un mecanismo para gestionar la jerarquía de la información en la base de datos. En la tabla #__asset se incluye información adicional para cada item del gestor de contenidos, destacando dos campos: lft y rgt. A continuación se comentarán dos modelos para gestionar información jerarquizada en tablas: el modelo de listas de adyacencia (padre - hijo) y el modelo de conjuntos anidadoss (lft - rgt).

Modelo de listas de adyacencia. Implementación padre - hijo

En general nuestras bases de datos almacena información estructurada en una serie de registros. Dichos registros además pueden presentar diversas jerarquías. A nivel lógico resulta intuitiva una visión de estas jerarquías en forma de árboles, la cual deberá implementarse posteriormente en una tabla en la base de datos.

• 

• Item	Padre	Hijo
  A	-	B
  A	-	C
  A	-	D
  B	A	-
  C	A	-
  D	A	-

La implementación de esta jerarquía en una tabla de relaciones es quizá la que a priori parece más intuitiva y lógica a seguir, ya que en una base de datos relacional lo habitual es que relacionemos items por medio de sus claves.
Esta forma de implementar un árbol jerárquico implica cierta redundancia de información como podemos observar en la tabla anterior.
En el caso de insertar un elemento implica además de añadir un nuevo registro (indicando el padre y valor nulo para hijo), actualizar o insertar (para el caso de que haya más hijos) el nuevo nodo hijo en el item padre.

• 

• Item	Padre	Hijo
  A	-	B
  A	-	C
  A	-	D
  B	A	-
  C	A	E
  D	A	-
  E	C	-

En el caso de otras operaciones tales como un recorrido en profundidad de todos los hijos de un nodo padre, partiendo de la estructura de tabla propuesta, reviste cierta complejidad. Tendríamos que, dado un padre, deducir sus descendientes directos, y a su vez por cada uno de ellos realizar la misma operación, así sucesivamente hasta llegar a los nodos terminales que no tengan más descendencia.

Otro problema que presenta la esta implementación es que si quisiéramos establecer algún orden deberíamos añadir información adicional. Es decir, en el gráfico vemos que B, C y D derivan de A. Pero ¿qué orden existe entre ellos? Podría ser D,C, B o cualquier otro, porque la tabla en sí no nos da información que nos lleve a dibujar de forma unívoca un único árbol. Tendríamos que incluir un nuevo campo en la tabla o seguir algún tipo de convención.

Se puede ampliar la información y entrar en  un estudio de mayor profundidad sobre este tipo de implementación en The Adjacency List Model for Trees, de Joe Celko.

Modelo de conjuntos anidados. Implementación left - right.

Otra forma de organizar la información de un árbol para facilitar su almacenamiento en tablas es definir por cada nodo dos índices: lft y rgt, haciendo referencia a left (izquierda) y right(derecha). Estos valores representarán el orden de recorrido en profundidad de los nodos del árbol que representa nuestra información jerarquizada.

• 

• Item	lft	rgt
  A	1	8
  B	2	3
  C	4	5
  D	6	7

Como se muestra en el gráfico, la asignación de valores es sencilla y la tabla que recoge esta información es compacta. Las inserciones tampoco revisten mayor complejidad, pero como veremos, pueden llegar a verse afectados todos los nodos, ya que en el peor de los casos puede requerir una reindexación total del árbol.

• 

• Item	lft	rgt
  A	1	10
  B	2	3
  C	4	7
  D	8	9
  E	5	6

Esta necesidad de cálculo y actualización puede significar incrementar el coste de añadir información a dicho árbol, así que habrá que analizar si podemos partir de supuestos que nos simplifiquen esta gestión tanto como sea posible. Analizaremos las caracterisiticas y propiedades de esta implementación para comprobar así que motivos justifican su uso frente a la propuesta anterior.

Detección de nodos terminales

Podemos verificar que, dadas las propiedades de este árbol, todo nodo final tiene valores lft y rgt consecutivos. Por ejemplo si un nodo n tiene valores tales como

        $node->lft=i y $node->rgt=i+1

podemos asegurar que no tiene hijos y es por tanto un nodo terminal.

Cálculo de nodos del (sub)árbol.

Otra propiedad de este tipo de árbol es que podemos calcular inmediatamente el número de nodos totales a partir del nodo cima, siendo este valor rgt/2 (tomando que lft comienza en 1). Sí sólo hay un elemento el valor rgt puede ser null y será un caso excepcional.

De hecho podemos extender esta propiedad a cualquier nodo para saber cuantos nodos derivan de un padre, incluído el mismo, siendo este valor

            (rgt-lft)/2 redondeando al entero superior 

Por ejemplo un nodo con valores

            lft=7 y rgt=12

tendríamos que

            (12-7)/2=2.5 

aproximando al entero superior daría 3 , lo que nos indicaría que ese nodo es la cima de un árbol que tiene 3 nodos, incluido él mismo

Mecanismo de inserción.

También podemos comprobar que la inserción de un elemento nunca implica incrementar el valor lft de sus ancestros, aunque sí requiere actualizar este valor en los hermanos de los ancestros más "jóvenes", es decir, los que tengan un valor lft superior al del nodo insertado, es decir, los que se sitúan en la parte derecha del árbol a partir de él.
Además, dado que la inserción del nuevo elemento implica añadir dos nuevos valores (lft y rgt) el incremento que haremos siempre será de 2 en los atributos de dichos nodos.
Los nodos implicados en la actualización siempre serán los superiores y los que se situen a la derecha. Si son ancestros sólo incrementaremos en 2 su valor rgt, dejando tal cual su valor lft. Si no lo son y están a la derecha incrementaremos en 2 sus valores lft y rgt.

Nodos ancestros.

Un nodo es ancestro de otro si su valor lft es menor que el que estamos tomando en consideración. De esta forma si estamos definiendo una serie de categorías jerarquizadas para los elementos de nuestra base de datos, nos será muy sencillo deducir en que categorías está englobado.

Nodos al mismo nivel.

También podemos deducir otras propiedades del árbol fácilmente, como por ejemplo los nodos que están a un mismo nivel de profundidad que uno dado. Podemos observar que si se cumple que

                 $nodo1->rgt+1 == $nodo2->lft

podremos asegurar que $nodo1 y $nodo2 están a la misma profundidad. Siguiendo con esta dinámica podremos buscar que nodo cumple que su valor lft es igual a $nodo2->rgt+1 y así sucesivamente para completar toda la lista de nodos al mismo nivel de profundidad.

Vemos que estructurar nuestra información jerarquizada de esta forma, además de ofrecernos información más compacta, nos permite realizar con relativa sencillez multitud de operaciones que con el planteamiento que se presentaba al principio del artículo tendrían cierta complejidad.
Lo mejor de todo es que si analizamos con detenimiento veremos que muchas de estas operaciones las podríamos resolver directamente en SQL sin tener que realizar implementaciones en otro lenguaje, lo cual nos hará ganar en eficiencia.

Para consultar información más precisa, así como implementación de estas operaciones recomiendo acceder al siguiente artículo de Mike Hillyer: Managing Hierarchical Data in MySQL