PHP & Mysql tree navigation menu with unlimited sub categories

Question

Im looking for a way to extract the data from the mysql database to create an unlimited subcategry menu. The menu has about 1500 categories in it and they are stored into the database table (menu) in the following format :

category_id , category title , parent_id

i want to do 1 mysql query to put all the data into an array.

$menu_list =array();

$query = mysql_query("SELECT * FROM menu ORDER BY category_id ASC");

if(mysql_num_rows($query) != 0) {
        while($row = mysql_fetch_array($query)){
              $category_id = $row['category_id'];
              $title = $row['category_title'];
              $parent_id = $row[parent_id'];
              $menu_list[] = array($category_id,$title,$parent_id);
        }
}

That is the code that i am currently using to turn the data into the array.

I then need to loop through the array to build a menu up.

I will then hide all subcategories and expand with jquery ( I can do this bit no problem )

The problem i have is going through the array and displaying the data in the right order. The menu has unlimited subcategories so it will probably need to be a recursive function to retrieve the data. I have folllowed alot of the examples on here but then i get lost how to display the data..

i now need to end up with :

main item
  sub cat
  sub cat
      sub cat 
          sub cat 
main item
   sub cat
main item
main item
   sub cat
       sub cat
          sub cat
             sub cat
             sub cat

etc...  

with each category in its own div I will then need to be able to edit each category (ie title name and position if need be) then if i change where a sub category is based a quick page refresh will reload the menu in the new order..

eventually i would like to make this into a drag and drop but that will be at a later date.

I hope this has explained it enough..

Thanks in advance..

---

So the problem has come back to haunt me again... My method of ajax calling another mysql select was ok for the CMS section as it was only used from time to time. But now we have got to the front end. Each time the page is viewed the first 3 levels of the menu are pulled using numerous mysql requests. As the categories are getting bigger this is now resulting in 1600+ categories being pulled numerous times each, and even at 1000 visits a day will result in more than a 1000000 sql requests a day. So i think i will definately need to pull the categories into an array, and then recursively go through the array.

I have looked at the solutions above and they seem to work on paper but not in practise.

If anyone can attempt to give me another solution it would be appreciated..

just to recap in my db i have : id , category_name , parent_id

I am now using PDO with mysql and prepared statements for added security..

Thanks in advance..

Solution 1

Here is the code what you need

category_id AS id , category title AS kategori and parent_id AS kid

function countsubcat($pid)
{

   $r=mysql_query("select count(kid) AS say from meskat where kid='$pid' limit 1");

   $rw=mysql_fetch_array($r);

   return $rw['say'];

}

function listmenu($pid = 0)
{

   $res = mysql_query("select id,kategori,kid from meskat where kid='$pid'");

   while($cat=mysql_fetch_array($res))

   {

     echo '<li>';

     print'<a href="#">'.$cat['kategori'].'</a>';

     if(countsubcat($cat['id'])>0)

     {

      print'<ul>';

         listmenu($cat['id']);

      print'</ul>';

     }
   echo '</li>';

   }

}

echo '<ul>';

listmenu(0); //starting from base category

echo '</ul>';`

Solution 2

In MySQL, this will require many queries, one for each level plus one at a minimum.

1. you grab all the top-level categories, use them as root nodes for a forest (a group of trees).
2. You grab all of the categories that are children of any of them.
3. Add each of these categories as children to the parent node
4. If there are still children, go to step two, otherwise stop.

What you end up with a tree that you do a depth-first walk through to convert to some (presumably) html representation (e.g. nested lists).

There are some optimisations you can perform. If you sort the child levels by parent ID, then you can assume continuous blocks of children, meaning you don't have to do as many lookups to find the correct parent, just check for a parent id change.

If you maintain a list of the current lowest level of categories, indexed by ID, you can speed up forest creation.

If you overlap steps 2 and 4, then you only do n+1 queries (where n is the number of levels), so checking for more children is also grabbing the next level of children.

In terms of memory, this will use the memory required for the tree, plus lowest level lookup table and a current parent id.

The building algorithm it fairly fast, scaling linearly with the number of categories.

This method also successfully avoids corrupted sections of data, because it won't grab data that have cycles (no root node).

I also suggest using a prepared statement for the children query, since MySQL will compile and cache the query, it will speed up the operation by only sending new data across the wire.

If you don't understand some of the concepts, I suggest hitting up Wikipedia as I have tried to use standard terms for these.