you might be looking for 'nested sets'. these can get failry complex, but they allow you to build an infinant recursive tree that is very quick to query for results, but can get a little slow when inserting nodes.

i was just reading the other day on some drupal, one of there developers had put forward the idea to replace whatever they use now with nested sets.

anyway, here is a link that should help you out with the theory behind it.

    That article is definitely an eye-opener. Thank you for the link thorpe. I think I'll probably go about it that way when I get around to writing up my scripts.

    And to bsgrules, I definitely suggest reading that article as I believe it should give you an idea of what you want to do. :p

      yeah its a cool article. takes a while to get your head around it though. ive been working on a nested sets class for the last few days. i'll probably post it in the 'code critique' forum when im done if you wanna take a look.

      few more days yet i would think.

        16 days later
        thorpe wrote:

        you might be looking for 'nested sets'. these can get failry complex, but they allow you to build an infinant recursive tree that is very quick to query for results, but can get a little slow when inserting nodes.

        i was just reading the other day on some drupal, one of there developers had put forward the idea to replace whatever they use now with nested sets.

        anyway, here is a link that should help you out with the theory behind it.

        Thank you and here is another nice article using the same method.

        http://www.sitepoint.com/article/hierarchical-data-database

          Ok, could anyone fully grasp that article when he uses the tree traversal method? I get lost when adding/deleting a new node. The author of the article just lightly touched that subject, and didn't include any code to make it easier to understand. Was anyone able to extrapolate an add/delete node function from what he wrote?

            Absolutely love that article, cheers for that. I did grasp the adding / deleting straight away as you can almost imagine the whole tree as having a 'string' around it nailed down at the left that gets longer when you insert a node with more string coming in from the right hand side - but just think about the way the string will flow around the nodes when something is added. Those to the left of the node won't have any string flow, but everything on the right will have the string slip around them.

            Hope this doesn't sound really weird as I tend to see and feel problems like this, and I'm sure quite a lot of other programmers do (please confirm this if you like!)

              12 days later

              Hi,

              A while ago, I posted this somewhere else.

              I use it to create a menu structure, and I think in one site I converted it for a forum, but I cannot find it right now.

              Anyhow, have a look. I think it is pretty understandable what happens. The idea is that you select all from a table, in which you store the message ID, a parentID (Which would be the message to which has been replied to) and a colum which defines a sortorder (In your coase you wouldn't need that, you can just sort by the unique ID> In a menu you may want to reshuffle pages). Then you start with the base-threads, where ID=0, and build from there, finding all the values which have a parent ecqual to the currently selected ID. It takes some tinkering, but this works for me, in several nested situations:

              
$menuquery = "select * from $menu_table order by M_sortorder";
   $result=mysql_query($menuquery) or die('An error occured retrieving data');
   $listing = Array();
   while($row = mysql_fetch_array($result))
     { 
     $listing[] = array("This_id" =>  $row[M_page_nr], "parent_id" => $row[M_p_nr],    
              
"category_title" =>  $row[M_label], "link" => $row['M_link'], "path" => $row[M_path]);
     }


function display_tree($parent, $level, $array, $menu_parent, $current_viewing_page)
  {
  foreach ($array AS $node)
    {

if(($node[parent_id] == $parent) and ($node[This_id] <> $current_viewing_page))// If the parent matches the pageid in the array
  {                              // the current page is a child of this parent

  if($node[This_id] == $menu_parent) // If the current page ID matches the parent_id, this child is a direct child
    {
    $selected = "selected";
    }
  else
    {
    $selected = "";
    }

  $indent = "";
  for($i = 1; $i <= $level; $i++) 
    {
    $indent .= "-";
    }

  $html .= "
  <option $selected value=\"$node[This_id]\">$indent 
$node[category_title]</option>
      ";
      $html .= display_tree($node[This_id], 
($level + 1), $array, $menu_parent, $current_viewing_page);
      }
    }

  return $html;

  } // end function display list


// Now use it

$pageslist = display_tree(0, 0, $listing, $menu_parent, $pageid);  

$selected = "";

                Recursion and the adjacency set model are inefficient.

                  Write a Reply...