Generando un árbol basado en profundidad a partir de datos jerárquicos en MySQL (sin CTE)
Hola Llevo muchos días trabajando en este problema en MySQL, sin embargo no logro resolverlo. ¿Alguno de ustedes tiene sugerencias?
Básicamente, tengo una tabla de categorías con dominios como:, id( namenombre de la categoría) y parent(id del padre de la categoría).
Datos de ejemplo:
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 de á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 única consulta SQL? La alternativa, que probé y funciona, es la siguiente:
SELECT * FROM category WHERE parent=0
Después de esto, reviso los datos nuevamente y selecciono las filas donde parent=id. Esto parece una mala solución. Debido a que es MySQL, no se pueden utilizar CTE.
Puedes hacerlo en una sola llamada desde php a mysql si usas un procedimiento almacenado:
Llamadas de ejemplo
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 #
Ejecuciones de prueba:
delimiter ;
call category_hier(1);
call category_hier(2);
Algunas pruebas de rendimiento utilizando datos de lugares geoplanetarios de Yahoo
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 son 5,6 millones de filas (lugares) en la tabla. Veamos cómo la implementación/procedimiento almacenado de la lista de adyacencia 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 en frío, ya que ni siquiera comenzaría a considerar devolver decenas de miles de filas de datos a mi interfaz, sino que preferiría construir el árbol dinámicamente obteniendo solo varios niveles por llamada. Ah, y en caso de que estuvieras pensando 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 anidados. Hay un muy buen artículo sobre estas alternativas en Gestión de datos jerárquicos en MySQL . Solo puedes hacer lo que quieras en una única consulta con el modelo de conjunto anidado. Sin embargo, el modelo de conjunto anidado hace que sea más complicado actualizar la estructura jerárquica, por lo que es necesario considerar las compensaciones en función de sus requisitos operativos.
No puede lograr esto usando una sola consulta. Su modelo de datos jerárquico es ineficaz en este caso. Le 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 realizar la selección que desee de una sola vez.
Aquí hay un artículo con más detalles: http://articles.sitepoint.com/article/hierarchical-data-database
