mysql - tabla - select recursivo

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

Question

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.

Answer 1

Hay dos formas comunes de almacenar datos jerárquicos en un RDBMS: listas de adyacencia (que está utilizando) y conjuntos anidados. 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 anidado. Sin embargo, el modelo de conjunto anidado hace que sea más útil actualizar la estructura jerárquica, por lo que debe considerar las compensaciones según sus requisitos operativos.

Answer 2

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.

Answer 3

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

Answer 4

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 :)