Efficient query to get all child nodes of a tree (mysql)

Question

I'm looking for an efficient query to return the child nodes of a tree . The data structure is:

  `ct_cid` int(10) unsigned NOT NULL default '0', // the data
  `ct_level` int(10) unsigned NOT NULL default '0', // the level (0 = topmost)
  `ct_parent` int(10) unsigned NOT NULL default '0', // parent ct_cid

I need to make sure there won't be endless loops even if the tree is broken or two nodes point to each other as parent.

Answer 1

I use sql query and then loop through all of the records to create required data set.

SELECT 
  *
 FROM 
  category
 ORDER BY 
  name ASC

then

while ($categoryItem = mysql_fetch_assoc($result_category))
{
 $categoryData['items'][$categoryItem['category_id']] = $categoryItem;
 $categoryData['parents'][$categoryItem['parent_id']][] = $categoryItem['category_id'];
}

This shall help you!

Answer 2

See this entry in my blog on how to do it efficiently in MySQL:

• Hierarchical queries in MySQL: finding loops

You'll need to create two functions:

CREATE FUNCTION hierarchy_connect_by_parent_eq_prior_id_with_level_and_loop(value INT, maxlevel INT) RETURNS INT
NOT DETERMINISTIC
READS SQL DATA
BEGIN
        DECLARE _id INT;
        DECLARE _parent INT;
        DECLARE _next INT;
        DECLARE _i INT;
        DECLARE CONTINUE HANDLER FOR NOT FOUND SET @id = NULL;

        SET _parent = @id;
        SET _id = -1;
        SET _i = 0;

        IF @id IS NULL THEN
                RETURN NULL;
        END IF;

        LOOP
                SELECT  MIN(id)
                INTO    @id
                FROM    t_hierarchy
                WHERE   parent = _parent
                        AND id > _id
                        -- Checking for @start_with in descendants
                        AND id <> @start_with
                        AND COALESCE(@level < maxlevel, TRUE);
                IF @id IS NOT NULL OR _parent = @start_with THEN
                        SET @level = @level + 1;
                        RETURN @id;
                END IF;
                SET @level := @level - 1;
                SELECT  id, parent
                INTO    _id, _parent
                FROM    t_hierarchy
                WHERE   id = _parent;
                SET _i = _i + 1;
        END LOOP;
        RETURN NULL;
END

and

CREATE FUNCTION hierarchy_connect_by_iscycle(node INT) RETURNS INT
NOT DETERMINISTIC
READS SQL DATA
BEGIN
        DECLARE _id INT;
        DECLARE _loop INT;
        DECLARE _node INT;
        DECLARE EXIT HANDLER FOR NOT FOUND RETURN 0;
        SET _id = COALESCE(node, @id);
        SET _loop = 0;
        SET _node = 0;
        LOOP
                SELECT  parent
                INTO    _id
                FROM    t_hierarchy
                WHERE   id = _id;
                IF _id = @start_with THEN
                        SET _loop := _loop + 1;
                END IF;
                IF _id = COALESCE(node, @id) THEN
                        SET _node = _node + 1;
                END IF;
                IF _loop >= 2 THEN
                        RETURN _node;
                END IF;
        END LOOP;
END

that would emulate Oracle's CONNECT BY and CONNECT_BY_ISCYCLE, and use them in a query:

SELECT  CONCAT(REPEAT('    ', lvl - 1), hi.id) AS treeitem,
        hierarchy_sys_connect_by_path('/', hi.id) AS path,
        parent, lvl,
        CASE
            WHEN lvl >= @maxlevel THEN 1
            ELSE COALESCE(
            (
            SELECT  0
            FROM    t_hierarchy hl
            WHERE   hl.parent = ho.id
                    AND hl.id <> @start_with
            LIMIT 1
            ), 1)
        END AS is_leaf,
        hierarchy_connect_by_iscycle(hi.id) AS is_cycle
FROM    (
        SELECT  hierarchy_connect_by_parent_eq_prior_id_with_level_and_loop(id, @maxlevel) AS id,
                CAST(@level AS SIGNED) AS lvl
        FROM    (
                SELECT  @start_with := 97657,
                        @id := @start_with,
                        @level := 0,
                        @maxlevel := NULL
                ) vars, t_hierarchy
        WHERE   @id IS NOT NULL
        ) ho
JOIN    t_hierarchy hi
ON      hi.id = ho.id

Answer 3

This is my issue. Recursive query.

function select_child_ids($parent_id,&$ida) {

    global $sql;

    $items = $sql->select_column("SELECT id FROM test WHERE parent_id = ".$parent_id);

    if ($items) {
        foreach ($items as $id) {
            $ida[] = $id;
            select_child_ids($id,$ida);
        }
    } else {
        return false;
    }
}

Note $sql is a exemplat of my class for work with mysql. You can use your own. After execution you can read childs elements in array $ida