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..

Answer 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>';`

Answer 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.

Answer 3

Can you alter the table structure? In that case you could take a look at the Nested Set Model (link includes description and implementation details, scroll down to The Nested Set Model). Node insertion and removal becomes more complex, but allows you to retrieve the whole tree in just one query.

Answer 4

If you can assume that for any category category_id > parent_id is true, the following recursive functions to represent the menu as a multi-level array and render it as a nested HTML list would work:

$menu = array();

$query = mysql_query("SELECT category_id, category_title, parent_id FROM menu ORDER BY category_id ASC");
if(mysql_num_rows($query) != 0) {
        while($row = mysql_fetch_assoc($query)) {
            if(is_null($row['parent_id']))
                $menu['children'][] = $row;
            else
                add_to_menu(&$menu,$row);
        }
}

function add_to_menu($menu,$item) {
    if(isset($menu['children'])) {
        foreach($menu['children'] as &$child) {
            if($item['parent_id'] == $child['category_id']) {
                $child['children'][] = $item;
            } else {
                add_to_menu(&$child,$item);
            }
        }
    }
}

function render_menu($menu) {
    if(isset($menu['children'])) {
        echo '<ul>';
        foreach($menu['children'] as &$child) {
            echo "<li>";
            echo $child['category_id']." : ".$child['category_title'];
            if(isset($child['children'])) {
                render_menu(&$child);
            }
            echo "</li>";
        }
        echo '</ul>';
    }
}

render_menu($menu);

Answer 5

So after various attempts at different solutions i actually have used jquery and a ajax load to retreive the next level.

With mine main categories all have a parent of 1 - shop i do a mysql scan for all categories with 1 as the parent id.

This will then display the main categories. Attached to each main category i have added a folder icon if they have any sub categories. I have also inserted a blank div with an id of that category.

When the folder is clicked it does an ajax call to a php script to find all categories with that parent. These are appended to the parents_id div.

This inturn adds the category (with a css padding to indicate a sub category) and again a folder sign if it has sub categories as well as another blank div with the category_id.

You can continue this for as many categories and sub categories as the client requires.

I took it a stage further and added an edit icon to category/subcategory so categories can be moved or changed.

If you would like some sample code for this let me know...

Answer 6

Actually, you need very little code to build a tree. You also only need one query. Here is what I came up with (I use Drupal's database but it is explicit enough to understand):

$items = db_select('menu_items', 'mi')
    ->fields('mi')
    ->orderBy('position')
    ->execute()
    ->fetchAllAssoc('id', PDO::FETCH_ASSOC);

// Example of result. The ID as key is important for this to work.
$items = array(
    3 => array('id' => 3, 'parent' => NULL, 'title' => 'Root', 'position' => 0),
    4 => array('id' => 4, 'parent' =>    3, 'title' => 'Sub',  'position' => 0),
    5 => array('id' => 5, 'parent' =>    4, 'title' => 'Sub sub', 'position' => 0),
    6 => array('id' => 6, 'parent' =>    4, 'title' => 'Sub sub', 'position' => 1),
);

// Create the nested structure. Note the & in front of $item.
foreach($items as &$item)
    if($item['parent'])
        $items[$item['parent']]['sub items'][$item['mid']] =& $item;

// Now remove the children from the root
foreach($items as $id => $item)
    if($item['parent']) // This is a child
        unset($items[$id])

At this point, all you need is a recursive function to display the menu:

function print_menu($items) {
    echo '<ul>';
    foreach($items as $item) {
        echo '<li>';

        echo '<a href="#">' . $item['title'] . '</a>';
        if(!empty($item['sub items']))
                print_menu($item['sub items']);

        echo '</li>';
    }
    echo '</ul>';
}