Encontrar el padre/hijo en un Modified Preorder Tree Traversal

13 marzo, 2015

Cuando en MySQL necesitamos acceder a datos en forma de árbol, la estructura más adecuada son los Modified Preorder Tree Traversal. Existen dos variantes de esta estructura, la primera simplemente almacena la información junto a los datos right y left, como en el caso del enlace que he pegado, y la segunda variante añade un tercer campo parent que apunta al padre (al valor left del nodo padre).

En caso de que tengas la primera versión del Modified Preorder Tree Traversal (MPTT), si necesitas acceder al nodo padre o al nodo hijo en un árbol suficientemente grande, tienes un problema. En mi caso, tenía un árbol de más de 80.000 nodos con la estructura simple right-left y al tratar de realizar operaciones que incluyeran al padre o al hijo, con SELECTs super-optimizados tenía tiempos de consulta superiores a 6 segundos (por ejemplo, esta query). Imposible manejar nada así. He de decir que en árboles pequeños, con solo unos 100 nodos, el tiempo bajaba hasta algunas décimas de segundo y se hacía manejable.

Conclusión: la única manera realmente rápida y manejable de realizar consultas que impliquen al padre o al hijo es convirtiendo el primer tipo de árbol en el segundo, es decir, pasar de un árbol con solo left-right a uno con left-right-parent. En concreto, esta es la UDF que busca un padre para un nodo dado:

DROP FUNCTION IF EXISTS getParent;
DELIMITER $$
CREATE FUNCTION getParent (NODE_LFT INT)
    RETURNS TEXT
BEGIN
    DECLARE result TEXT DEFAULT "";
    SELECT MIN(p.rgt) INTO result
    FROM tree AS node, tree AS p
    WHERE node.lft BETWEEN p.lft+1 AND p.rgt-1 AND node.lft=NODE_LFT;
    RETURN result;
END;
$$
DELIMITER ;

Si a la tabla que contiene el árbol (que le hemos llamado tree en este caso, habría que modificarlo según corresponda), se le añade un campo parent, se puede ejecutar una sentencia simple como esta para asignar a todos los nodos hijos un padre:

UPDATE tree
SET parent=getParent(lft);

Esta sentencia, en mi árbol de más de 80.000 nodos tardó algo más de una hora en ejecutarse manteniendo durante ese tiempo la CPU al 100%. Jamás hagas este tipo de actualizaciones en producción, hazlo en el ordenador de desarrollo y luego subes la base de datos (bloquea las actualizaciones mientras haces todo el proceso).

Por supuesto, una vez hecho esto, la función de inserción debe actualizarse para que guarde también el padre. Otras funciones básicas como el borrado de nodos no se ven afectadas. Si tienes funciones más complejas como reordenaciones y demás, tendrás que ver si resulta necesario modificar alguna consulta.

De esta manera, buscar los hijos directos de un determinado nodo es una tarea sumamente fácil y rápida:

SELECT *
FROM tree
WHERE parent='3';

O lo mismo para dar con el padre:

SELECT *
FROM tree
WHERE rgt=(SELECT parent FROM tree WHERE lft='3');
Be Sociable, Share!

Tags: , , ,
Posteado en Tecnologia | Comentarios (0)

Dejar un comentario