Recursive categories with a single query?

Question

I have a website with articles and sections, each sections can have a parent section, as much as they like for example:

subject 1
 -subject 2 
 --subject 3
 -subject 4
 --subject 5
 --subject 6
 ---subject 7
subject 8
subject 9

etc..

Now, i want to fetch them recursively, what is the most efficient way to do it via php and mysql?

Tnx in advanced.

Crocodile

Answer 1

If the tree isn't too large, you can simply build the tree in PHP using some clever references.

$nodeList = array();
$tree     = array();

$query = mysql_query("SELECT category_id, name, parent FROM categories ORDER BY parent");
while($row = mysql_fetch_assoc($query)){
    $nodeList[$row['category_id']] = array_merge($row, array('children' => array()));
}
mysql_free_result($query);

foreach ($nodeList as $nodeId => &$node) {
    if (!$node['parent'] || !array_key_exists($node['parent'], $nodeList)) {
        $tree[] = &$node;
    } else {
        $nodeList[$node['parent']]['children'][] = &$node;
    }
}
unset($node);
unset($nodeList);

This will give you the tree structure in $tree with the children in the respective children-slot.

We've done this with fairly large trees ( >> 1000 items) and it's very stable and a lot faster than doing recursive queries in MySQL.

Traweek

This is some really nice code, still trying to get my head fully around it but its very compact for its functionality, I might be stealing it :P – Fenton

You need the & because we just add references to the original $node in the $nodeList to be able to add the children not to a copy but to the original $node. – Traweek

@Stefan Gehrig, I have been trying to understand your code and in doing so I removed the third reference, $nodeList[$node['parent']]['children'][] = &$node; became $nodeList[$node['parent']]['children'][] = $node; and it still worked. This hasnt helped me understand it any more :) but I thought I would mention it. Luke – Fenton

@Luke: yes that's right - this & is not required, but the first two are crucial. Let's try to briefly explain what this code does: - we read the DB result set into $nodeList (indexed by the primary key) - we iterate over this list of nodes getting a reference to each node array (first &) - we check if the current node has a parent and the parent exists in the $nodeList - if not (if-branch) we add a reference (second &) to the current node to the root of our $tree - if yes (else-branch) we add the reference (third & which is not required) to the node's parent children collection – Traweek

The trick is to simply add references to $tree so that changes in the children collection of each node get propagated into $tree. Both unset()-calls ensure that we don't leave any references dangling around and that $tree now contains the real nodes (as $tree now holds the last reference to the "real" node). – Traweek

Thanks Stefan thats perfect, I just wrote a quick test script and I understand it all, it was only how the references where affecting it that I could not grasp and now I do. thanks. :) – Fenton

Pure genius! I've learned a lot from this! Very creative, nice use of &...wooow =D – Manager

Neat method Stefan Gehrig, but how would you get a subtree given an id? May I need to use recursion? – Torrid

Nice code. How do you print $tree with nested <ul> and <li> structure? – Lucic

How can I get subsection of the tree? – Sparker

@Victor: If you do not unset($nodeList) you can access every subtree with $nodeList[<<id of the subtree parent node>>]. – Traweek

Answer 2

That depends on how you have stored your data. There is a good article on MySQL.com called Managing Hierarchical Data in MySQL that talks about this.

Keven

i just wanted to say that. this is the only way to fetch all hierarchy in one query – Aesculapius

Answer 3

Well, you can fetch all the categories in an array in just the one query, as you know:

$query = "SELECT `name`,`id` from `table`";

Having that in an array, you can build the tree with some nested loops. It won't be fast, but is simple, and faster than using recursive queries. Also, you can cache the built tree and not having to rebuild it every time.

Anal

i've wrote the tree function not with recursy too, but the script was very large, and doesn't work faster, then recursy, so why not recurcy? – Canberra

SQL queries + recursion is something you want avoid, at least in my experience. – Anal

Answer 4

You could have a look at this topic : how to get the hierarchical menu from mysql that was opened yesterday and is about the same thing.

Werby

Answer 5

Mine uses recursion with one query as well...

A recursive method to storing hierarchical data without multiple calls to the database

I wanted to use recursion also due to its simplicity but like you I wanted to remove the overhead of a recursive query. My logic says in this way you are just moving the load from the database to memory depending on the size of your database result but I have not done any real scalability testing on this so I don't know how much of an impact it has vs non recursive methods.

Oxyacid

Answer 6

I cant guarentee I havent made any syntax mistakes but this should work with one query.

class menuSystem{ 
var $menu;
var $db; #this variable is my db class assigned from the construct, I havent written the construct in, I can if you need it
function startNav(){
    $this->db->runQuery("select * from table order by parent asc");
    $menu = array(0 => array('children' => array()));
    while ($data = $this->db->fetchArray()) {
      $menu[$data['category_id']] = $data;
      $menu[(is_null($data['parent']) ? '0' : $data['parent'] )]['children'][] = $data['category_id'];
    }
    $this->menu = $menu;
    $nav = '<ul>';
    foreach($menu[0]['children'] as $child_id) {
      $nav .= $this->makeNav($menu[$child_id]);
    }
    $nav .= '</ul>';
}

function makeNav($menu){
   $nav_one = '<li>'."\n\t".'<a href="#">'$menu['name'].'</a>';
    if(isset($menu['children']) && !empty($menu['children'])) {
      $nav_one .= "<ul>\n";
      foreach($menu['children'] as $child_id) {
        $nav_one .= $this->makeNav($this->menu[$child_id]);
      }
      $nav_one .= "</ul>\n";
    }
    $nav_one .= "</li>\n";
return $nav_one;
}

}

EDIT: sorry I use this in my code as a class and thought I had managed to take it out of a class for you but forgot I needed $this->menu

UPDATE: I think the below is out of a class now, sorry for such a long answer

$result = mysql_query("select * from table order by parent_id asc");
$menu = array(0 => array('children' => array()));
while ($data = mysql_fetch_array($result)) {
  $menu[$data['category_id']] = $data;
  $menu[(is_null($data['parent_id']) ? '0' : $data['parent_id'] )]['children'][] = $data['category_id'];
}
$global_menu = $menu;
$nav = '<ul>';
foreach($menu[0]['children'] as $child_id) {
  $nav .= makeNav($menu[$child_id]);
}
$nav .= '</ul>';

function makeNav($menu) {
  global $global_menu;
  $nav_one = '<li>'."\n\t".'<a href="#">' . $menu['name'].'</a>';
  if(isset($menu['children']) && !empty($menu['children'])) {
    $nav_one .= "<ul>\n";
    foreach($menu['children'] as $child_id) {
      $nav_one .= makeNav($global_menu[$child_id]);
    }
    $nav_one .= "</ul>\n";
  }
  $nav_one .= "</li>\n";
  return $nav_one;
}

Hope it helps

Luke

Fenton

Answer 7

the first part of the article relates only to 4 levels, the last part is not the way I want to do it.

my structure is something like that:

+-------------+----------------------+--------+
| category_id | name                 | parent |
+-------------+----------------------+--------+
|           1 | test                 |   NULL |
|           2 | subject1             |   1    |
|           3 | subject2             |   1    |
|           4 | subject3             |   2    |
|           5 | subject4             |   4    |
+-------------+----------------------+--------+

I dont want to complicate things, I want to do it in the most simple way, but to fetch the data in the most efficient way.

Crocodile

I have implemented a very similar structure to this and found it to work well. – Reactive

Answer 8

if assume, that your table has id, id_parrent and name fields

function tree($id)
{
    $query = "SELECT `name`,`id` from `table` WHERE `id_parrent` = '$id'";
    $result = mysql_query($query);
     if(mysql_num_rows($result) != 0)
       {
            echo "<ul>";
            while($row = mysql_fetch_array($result))
            {             
                 echo "<li>",$row[name],"</li>";
                 tree($row[id]);
            }
            echo "</ul>";
       }
}

by so you'll get the whole tree

category1
       category1_1
       category1_2
              category1_2_1
              category1_2_2
       category1_3
...........................

Canberra

i have only one query in my function :P – Canberra

this one is the slowest solution. – Aesculapius

@Dobiatowski don't say slowest. it will be more slower if you deside to print them one by one, by hand :D – Canberra

rotfl, you shouldnt think what will be faster for you but for the CPU ;) – Aesculapius

Answer 9

From your example to each category save its full path in another field:
1 - 1
2 - 1.2
3 - 1.2.3
4 - 1.4
5 - 1.4.5
6 - 1.4.6
7 - 1.4.6.7
8 - 8
9 - 9

and then just query with ORDER BY on that field

Godhood

Answer 10

I have made a query for you. This will give you Recursive Category with a Single Query:

SELECT id,NAME,'' AS subName,'' AS subsubName,'' AS subsubsubName FROM app_category WHERE Parent_id=0
UNION 
SELECT b.id,a.name,b.name AS subName,'' AS subsubName,'' AS subsubsubName FROM app_category AS a LEFT JOIN app_category AS b ON b.parent_id=a.id WHERE a.Parent_id=0 AND b.name IS NOT NULL 
UNION 
SELECT c.id,a.name,b.name AS subName,c.name AS subsubName,'' AS subsubsubName FROM app_category AS a LEFT JOIN app_category AS b ON b.parent_id=a.id LEFT JOIN app_category AS c ON c.parent_id=b.id WHERE a.Parent_id=0 AND c.name IS NOT NULL 
UNION 
SELECT d.id,a.name,b.name AS subName,c.name AS subsubName,d.name AS subsubsubName FROM app_category AS a LEFT JOIN app_category AS b ON b.parent_id=a.id LEFT JOIN app_category AS c ON c.parent_id=b.id LEFT JOIN app_category AS d ON d.parent_id=c.id WHERE a.Parent_id=0 AND d.name IS NOT NULL 
ORDER BY NAME,subName,subsubName,subsubsubName 

Here is a fiddle.

Pareto

This assumes that the OP is only interested in recursing to a finite depth. This is not a flexible solution. – Staffard