Generando árbol basado en profundidad a partir de datos jerárquicos en MySQL (sin CTE)

Hola. Durante muchos días he estado trabajando en este problema en MySQL, pero no puedo resolverlo. ¿Alguno de ustedes tiene sugerencias?

Básicamente, tengo una tabla de categorías con dominios como: id , name (nombre de la categoría) y parent (id de parent de la categoría).

Ejemplo de datos:

 1 Fruit 0 2 Apple 1 3 pear 1 4 FujiApple 2 5 AusApple 2 6 SydneyAPPLE 5 .... 

Hay muchos niveles, posiblemente más de 3 niveles. Quiero crear una consulta SQL que agrupe los datos según la jerarquía: padre> hijo> nieto> etc.

Debería generar la estructura del árbol, de la siguiente manera:

 1 Fruit 0 ^ 2 Apple 1 ^ 4 FujiApple 2 - 5 AusApple 2 ^ 6 SydneyApple 5 - 3 pear 1 

¿Puedo hacer esto usando una sola consulta SQL? La alternativa, que probé y funciona, es la siguiente:

 SELECT * FROM category WHERE parent=0 

Después de esto, vuelvo a recorrer los datos y selecciono las filas donde parent = id. Esto parece una mala solución. Como es mySQL, no se pueden usar CTE.

Puede hacerlo en una sola llamada de php a mysql si usa un procedimiento almacenado:

Ejemplos de llamadas

 mysql> call category_hier(1); +--------+---------------+---------------+----------------------+-------+ | cat_id | category_name | parent_cat_id | parent_category_name | depth | +--------+---------------+---------------+----------------------+-------+ | 1 | Location | NULL | NULL | 0 | | 3 | USA | 1 | Location | 1 | | 4 | Illinois | 3 | USA | 2 | | 5 | Chicago | 3 | USA | 2 | +--------+---------------+---------------+----------------------+-------+ 4 rows in set (0.00 sec) $sql = sprintf("call category_hier(%d)", $id); 

Espero que esto ayude 🙂

Guión completo

Estructura de la tabla de prueba:

 drop table if exists categories; create table categories ( cat_id smallint unsigned not null auto_increment primary key, name varchar(255) not null, parent_cat_id smallint unsigned null, key (parent_cat_id) ) engine = innodb; 

Datos de prueba:

 insert into categories (name, parent_cat_id) values ('Location',null), ('USA',1), ('Illinois',2), ('Chicago',2), ('Color',null), ('Black',3), ('Red',3); 

Procedimiento:

 drop procedure if exists category_hier; delimiter # create procedure category_hier ( in p_cat_id smallint unsigned ) begin declare v_done tinyint unsigned default 0; declare v_depth smallint unsigned default 0; create temporary table hier( parent_cat_id smallint unsigned, cat_id smallint unsigned, depth smallint unsigned default 0 )engine = memory; insert into hier select parent_cat_id, cat_id, v_depth from categories where cat_id = p_cat_id; /* http://dev.mysql.com/doc/refman/5.0/en/temporary-table-problems.html */ create temporary table tmp engine=memory select * from hier; while not v_done do if exists( select 1 from categories p inner join hier on p.parent_cat_id = hier.cat_id and hier.depth = v_depth) then insert into hier select p.parent_cat_id, p.cat_id, v_depth + 1 from categories p inner join tmp on p.parent_cat_id = tmp.cat_id and tmp.depth = v_depth; set v_depth = v_depth + 1; truncate table tmp; insert into tmp select * from hier where depth = v_depth; else set v_done = 1; end if; end while; select p.cat_id, p.name as category_name, b.cat_id as parent_cat_id, b.name as parent_category_name, hier.depth from hier inner join categories p on hier.cat_id = p.cat_id left outer join categories b on hier.parent_cat_id = b.cat_id order by hier.depth, hier.cat_id; drop temporary table if exists hier; drop temporary table if exists tmp; end # 

Pruebas de prueba:

 delimiter ; call category_hier(1); call category_hier(2); 

Algunas pruebas de rendimiento con Yahoo geoplanet colocan datos

 drop table if exists geoplanet_places; create table geoplanet_places ( woe_id int unsigned not null, iso_code varchar(3) not null, name varchar(255) not null, lang varchar(8) not null, place_type varchar(32) not null, parent_woe_id int unsigned not null, primary key (woe_id), key (parent_woe_id) ) engine=innodb; mysql> select count(*) from geoplanet_places; +----------+ | count(*) | +----------+ | 5653967 | +----------+ 

entonces eso es 5,6 millones de filas (lugares) en la tabla, veamos cómo la implementación de la lista de adyacencia / procedimiento almacenado llamado desde php maneja eso.

  1 records fetched with max depth 0 in 0.001921 secs 250 records fetched with max depth 1 in 0.004883 secs 515 records fetched with max depth 1 in 0.006552 secs 822 records fetched with max depth 1 in 0.009568 secs 918 records fetched with max depth 1 in 0.009689 secs 1346 records fetched with max depth 1 in 0.040453 secs 5901 records fetched with max depth 2 in 0.219246 secs 6817 records fetched with max depth 1 in 0.152841 secs 8621 records fetched with max depth 3 in 0.096665 secs 18098 records fetched with max depth 3 in 0.580223 secs 238007 records fetched with max depth 4 in 2.003213 secs 

En general, estoy bastante satisfecho con esos tiempos de ejecución fríos, ya que ni siquiera comenzaría a considerar la posibilidad de devolver decenas de miles de filas de datos a mi interfaz, pero preferiría construir el árbol de forma dinámica obteniendo solo varios niveles por llamada. Ah, y en el caso de que pensaras que innodb es más lento que myisam, la implementación de myisam que probé fue dos veces más lenta en todos los aspectos.

Más cosas aquí: http://pastie.org/1672733

Espero que esto ayude 🙂

Hay dos formas comunes de almacenar datos jerárquicos en un RDBMS: listas de adyacencia (que está utilizando) y conjuntos nesteds. Hay una muy buena reseña sobre estas alternativas en Managing Hierarchical Data in MySQL . Solo puede hacer lo que quiera en una sola consulta con el modelo de conjunto nested. Sin embargo, el modelo de conjunto nested hace que sea más útil actualizar la estructura jerárquica, por lo que debe considerar las compensaciones según sus requisitos operativos.

No puede lograr esto usando una sola consulta. Su modelo de datos jerárquicos no es efectivo en este caso. Sugiero que pruebe otras dos formas de almacenar datos jerárquicos en una base de datos: el modelo MPTT o el modelo de “linaje”. El uso de cualquiera de esos modelos le permite hacer la selección que desea de una sola vez.

Aquí hay un artículo con más detalles: http://articles.sitepoint.com/article/hierarchical-data-database

La forma lineal:

Estoy usando una función fea para crear un árbol en un campo de cadena simple.

 / topic title /001 message 1 /002 message 2 /002/001 reply to message 2 /002/001/001/ reply to reply /003 message 3 etc... 

la tabla se puede usar para seleccionar todas las filas en el orden de árbol con una consulta SQL simple:

select * from morum_messages where m_topic=1234 order by m_linear asc

INSERT es simplemente seleccionar el padre lineal (y los hijos) y calcular la cadena según sea necesario.

 select M_LINEAR FROM forum_messages WHERE m_topic = 1234 and M_LINEAR LIKE '{0}/___' ORDER BY M_LINEAR DESC limit 0,1 /* {0} - m_linear of the parent message*/ 

DELETE es simple como eliminar el mensaje, o eliminar linealmente todas las respuestas del padre.