Henry Weismann’s Personal Blog

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

by on Feb.22, 2011, under Web Development

So here goes my first code snippet post.  I recently needed to create a hierarchical list of categories.  Since I am no genius and I don’t want to recreate the wheel I looked at all the methods I could find in a google search.  This brought me to Evolt.org which mentioned:

  1. Recursion
  2. Stack
  3. Flat Table
  4. Modified Preorder Tree Traversal Algorithm

Then I found an article on sitepoint.om which got me stoked cause sitepoint always has the best articles.  All these articles and numerous other results left me wanting to use the data structure I see most apps using with a parent_id and recursion but all the examples, even on sitepoint, used a database call inside the recursive function which I thought was a really big no no.  I couldn’t believe all these sites were discarding recursion as too much overhead because of the database call when they just needed to rework it a bit to get rid of that overhead.

So here is the recursive method, named the adjacency list model by sitepoint, to storing hierarchical data without multiple calls to the database.

First get your categories from the database and sort using the parent id, then the sort column.  Then go through the result array and create an array with each row having the parent_id as the key.  Here is how that would look in codeigniter:

 $this->db->order_by('parent_id, display_order', $direction);
 $categories = $this->db->get('categories');

 foreach($categories->result() as $category)
 {
 $organized_categories[$category->parent_id][] = $category;
 }

 return $organized_categories;

Then use a function like this to output the hierarchy:

function display_categories_list_options($categories, $group, $indent_level, $selected='')
{
     foreach($group as $row)
     {
          $html = '<option value="'.$row->id.'" '.set_select('parent_id',$row->id,($row->id==$selected)).'>'.str_repeat('--',$indent_level).$row->name.'</option>';

          echo $html;

          if(isset($categories[$row->id]))
          {
            display_categories_list_options($categories, $categories[$row->id], $indent_level+1,$selected);
          }
     }
}

You could also load a view, if your using MVC, in the $html variable.  That should do it.  This is not fully tested yet but it works for me so far.  Let me know if you find this helpful.

:, , , ,

Leave a Reply

Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Blogroll

A few highly recommended websites...

    Archives

    All entries, chronologically...