Fast tree

drisate · October 2, 2013

Hey guys i have a database of 2800 items that needs to be displayed inside a colaseble tree systeme. I am having a very big speed issue ... At the moment my code works with 2 fonctions in a recursive way. The page can take up to 50 seconds to load and it uses a lot of the servers CPU. I need to find an other way of doing it ...

<?php
function page_treeview(){GlOBAL $_SESSION;
    $select_page = mysql_query("SELECT * FROM pages WHERE parent='0' order by ordre asc") or die(mysql_error());  
    if($select_page){
        echo '<form method="POST" id="ajaxform" class="load_form">
        <ul class="menu-tree accordion dark strips">';  
        
        while ($list_page = mysql_fetch_array($select_page))
        {
            echo '<li>
                    <input type="checkbox" id="category-'.$list_page[id].'" />
                    <label for="category-'.$list_page[id].'">
                        <i onclick="location.href=\'index.php?mod=page&id='.$list_page[id].'&pid='.$list_page[parent].'\'" class="icon-edit-sign"></i>
                        <i onclick="location.href=\'index.php?mod=page&del='.$list_page[id].'\'" class="icon-remove-sign"></i>
                        <i onclick="location.href=\'index.php?mod=page&id='.$list_page[id].'&pid='.$list_page[parent].'&action=add\'" class="icon-plus-sign-alt"></i>
                         '.$list_page[titre].'
                        <span class="notification"></span>
                    </label>';
                    page_enfant($list_page[id]);          
            echo'</li>';
        }
        echo '</ul><br><input type="submit" value="Sauvegarder l\'ordre" name="saveordre"></form>';
    }
}

function page_enfant($parent, $level = 1){
    $select_page_enfant = mysql_query("SELECT * FROM pages WHERE parent ='$parent' order by ordre asc") or die(mysql_error());
    if(mysql_num_rows($select_page_enfant)!='')
    {
        $selectparent = mysql_fetch_array(mysql_query("SELECT * FROM pages WHERE id='$parent'"));
        echo "\n".'<ul>';
        while ($list_page_enfant = mysql_fetch_array($select_page_enfant)) {
         
        $selectparent = mysql_fetch_array(mysql_query("SELECT * FROM pages WHERE id='$list_page_enfant[id]'"));
            
            echo "\n".'<li>
                    <input type="checkbox" id="category-'.$list_page_enfant[id].'" />
                    <label for="category-'.$list_page_enfant[id].'">
                        <i class="icon-edit-sign"></i>
                        <i class="icon-remove-sign"></i>
                        <i class="icon-plus-sign-alt"></i> '.$list_page_enfant[titre].'
                        <span class="notification"></span>
                    </label>';
                    page_enfant($list_page_enfant[id], $level+1);                 
            echo'</li>'."\n";
        }
        echo '</ul>'."\n";
    }
}
 
echo page_treeview();
?>

drisate · October 2, 2013

I think i am up to something .... but it's not working yet as expected .... The parent = 0 loops well but then everything under breaks.

function mapTree($dataset) {
    $tree = array();
    foreach ($dataset as $id=>&$node) {
        if ($node['parent'] === null) {
            $tree[$id] = &$node;
        } else {
            if (!isset($dataset[$node['parent']]['children'])) $dataset[$node['parent']]['children'] = array();
            $dataset[$node['parent']]['children'][$id] = &$node;
        }
    }
    
    return $tree;
}

// Liste des pages
function page_treeview(){GlOBAL $_SESSION;

    $pages = mysql_query("SELECT id, parent, titre FROM pages"); $t=0;
    while($page = mysql_fetch_array($pages)){
        $tree[$page[id]][name] = $page[titre];
        $tree[$page[id]][parent] = $page[parent];
        $tree[$page[id]][id] = $page[id];
        $t++;
    }
    

    $pages = mapTree($tree,"0");
    
    if($pages[0][children]){
        
        echo '<form method="POST" id="ajaxform" class="load_form">
        <ul class="menu-tree accordion dark strips">';  
        
        foreach($pages[0][children] as $page){
                        
            if ($page[parent]=='0'){
                echo '<li>
                        <input type="checkbox" id="category-'.$page[id].'" />
                        <label for="category-'.$page[id].'">
                            <i onclick="location.href=\'index.php?mod=page&id='.$page[id].'&pid='.$page[parent].'\'" class="icon-edit-sign"></i>
                            <i onclick="location.href=\'index.php?mod=page&del='.$page[id].'\'" class="icon-remove-sign"></i>
                            <i onclick="location.href=\'index.php?mod=page&id='.$page[id].'&pid='.$page[parent].'&action=add\'" class="icon-plus-sign-alt"></i>
                             '.$page[name].'
                            <span class="notification"></span>
                        </label>';
                        page_enfant($page[id], $pages);          
                echo'</li>';
            }
            
        }
        echo '</ul><br><input type="submit" value="Sauvegarder l\'ordre" name="saveordre"></form>';
    }
    
}



function page_enfant($parent, $pages, $level = 1){

        echo "\n".'<ul>';
        
        foreach($pages[0][children][$parent] as $page){
            
            echo "\n".'<li>
                    <input type="checkbox" id="category-'.$page[id].'" />
                    <label for="category-'.$page[id].'">
                        <i class="icon-edit-sign"></i>
                        <i class="icon-remove-sign"></i>
                        <i class="icon-plus-sign-alt"></i> '.$page[name].'
                        <span class="notification"></span>
                    </label>';
                    page_enfant($page[id], $level+1);                 
            echo'</li>'."\n";
            
        }
        
        echo '</ul>'."\n";

}

The problem seems to come from the page_enfant function. I not sure how i can loop the $pages var ...

Array dump sample can be found at

http:// pastie.org/8372608

Link broken so it's not public

Psycho · October 2, 2013

NEVER run queries in loops unless absolutely necessary - and this isn't necessary. You need to JOIN the tables to get all the data you need in one query. I'll take a look and post back.

Psycho · October 2, 2013

A couple other points.

1. You are calling the parent function with an ech0, but the functions themselves are echoing content. The functions should return the content.

2. You use GLOBAL $_SESSION in the functions. The $_SESSION variable is global by default.

3. You are referencing array values with a non-numeric index that is not enclosed in quotes. That will work but is very inefficient since the PHP parser will first look for a constant of that name then, if that doesn't exist, it will then treat it as a text.

As to your problem, I see it has many levels. There are numerous articles about handling Hierarchical data in queries. But, that aside, you can get all the data with a greatly reduced number of queries. First query all the records at the parent level. Then query ALL the records at the next level instead of getting the child records for each parent individually.

vinny42 · October 2, 2013

You need to JOIN the tables to get all the data you need in one query. I'll take a look and post back.

You can't do recursion in a join.

You could argue that the recursion could be done in PHP, if the entire tree has to be loaded (and can be loaded) into memory.

But my first thought would be why the query does a SELECT *, and if there is an index on the columns used in the WHERE clause.

50 seconds is bizarly slow for a maximum of 2800 queries no matter what you do.

drisate · October 2, 2013

Thanks for your interest in my problem.

Using a recursive function or joining in SQL usually are the most common ways for creating tree structures. Both these solutions are of exponential time complexity 2^O(n) and therefore very expensive in computational time. For every element you add to the dataset the computational time theoretically doubles.

My problem commes from page_enfant(). it's not completing the loop. On my last version. I am performing only one SQL query and i am using the result to performe my loops instead of my first version where i query the database on every loops almost 3 times.

Edited October 2, 2013 by drisate

drisate · October 2, 2013

I posted my pages table here http://tinyurl.com/drisate.

( it's 110 Mo ... )

kicken · October 2, 2013

Building Tree Structures in PHP Using References - Read that.

Basically you

a) Select everything you need in just one query. Make sure parents come before any of their children

b) As you loop the results you maintain two arrays. One containing the tree structure, and a second which is a simple ID => array map. These arrays are connected via a reference.

vinny42 · October 2, 2013

Both these solutions are of exponential time complexity 2^O(n) and therefore very expensive in computational time. For every element you add to the dataset the computational time theoretically doubles.

Except that it doesn't.

My problem commes from page_enfant(). it's not completing the loop. On my last version. I am performing only one SQL query and i am using the result to performe my loops instead of my first version where i query the database on every loops almost 3 times.

Are you sure you look for children, and not for parents?

Make sure parents come before any of their children

How would you do that, given that you don't know which records are children of which others before you fetch them?

Psycho · October 2, 2013

You can't do recursion in a join.

I didn't realize in my initial post that there were multiple levels of children.

Edited October 2, 2013 by Psycho

kicken · October 2, 2013

How would you do that, given that you don't know which records are children of which others before you fetch them?

There may be ways, depends on the data in question. For example my menu system has an added-on date attached to each node. Unless someone decided to go in an manually fiddle around in the DB vs using the menu management interface, the parent's will always have been added before their children so a simple ORDER BY addedOn works.

If it's truly not possibly at the SQL level to do such ordering, you can extend the PHP processing to handle it. It's simply easier if you can assume parents always come first.

drisate · October 2, 2013

I saw that link already. If you take a look at my seconde code i posted, thats teh function i am trying to use. But i am failing in the recuresive function. Can you show me an exemple of your "b" point?

I think i am up to something .... but it's not working yet as expected .... The parent = 0 loops well but then everything under breaks.

function mapTree($dataset) {
    $tree = array();
    foreach ($dataset as $id=>&$node) {
        if ($node['parent'] === null) {
            $tree[$id] = &$node;
        } else {
            if (!isset($dataset[$node['parent']]['children'])) $dataset[$node['parent']]['children'] = array();
            $dataset[$node['parent']]['children'][$id] = &$node;
        }
    }
    
    return $tree;
}

// Liste des pages
function page_treeview(){GlOBAL $_SESSION;

    $pages = mysql_query("SELECT id, parent, titre FROM pages"); $t=0;
    while($page = mysql_fetch_array($pages)){
        $tree[$page[id]][name] = $page[titre];
        $tree[$page[id]][parent] = $page[parent];
        $tree[$page[id]][id] = $page[id];
        $t++;
    }
    

    $pages = mapTree($tree,"0");
    
    if($pages[0][children]){
        
        echo '<form method="POST" id="ajaxform" class="load_form">
        <ul class="menu-tree accordion dark strips">';  
        
        foreach($pages[0][children] as $page){
                        
            if ($page[parent]=='0'){
                echo '<li>
                        <input type="checkbox" id="category-'.$page[id].'" />
                        <label for="category-'.$page[id].'">
                            <i onclick="location.href=\'index.php?mod=page&id='.$page[id].'&pid='.$page[parent].'\'" class="icon-edit-sign"></i>
                            <i onclick="location.href=\'index.php?mod=page&del='.$page[id].'\'" class="icon-remove-sign"></i>
                            <i onclick="location.href=\'index.php?mod=page&id='.$page[id].'&pid='.$page[parent].'&action=add\'" class="icon-plus-sign-alt"></i>
                             '.$page[name].'
                            <span class="notification"></span>
                        </label>';
                        page_enfant($page[id], $pages);          
                echo'</li>';
            }
            
        }
        echo '</ul><br><input type="submit" value="Sauvegarder l\'ordre" name="saveordre"></form>';
    }
    
}



function page_enfant($parent, $pages, $level = 1){

        echo "\n".'<ul>';
        
        foreach($pages[0][children][$parent] as $page){
            
            echo "\n".'<li>
                    <input type="checkbox" id="category-'.$page[id].'" />
                    <label for="category-'.$page[id].'">
                        <i class="icon-edit-sign"></i>
                        <i class="icon-remove-sign"></i>
                        <i class="icon-plus-sign-alt"></i> '.$page[name].'
                        <span class="notification"></span>
                    </label>';
                    page_enfant($page[id], $level+1);                 
            echo'</li>'."\n";
            
        }
        
        echo '</ul>'."\n";

}

The problem seems to come from the page_enfant function. I not sure how i can loop the $pages var ...

Array dump sample can be found at

http:// pastie.org/8372608Link broken so it's not public

Edited October 2, 2013 by drisate

vinny42 · October 2, 2013

Unless someone decided to go in an manually fiddle around in the DB vs using the menu management interface

Or a node has been moved using the interface :-)

If it's truly not possibly at the SQL level to do such ordering, you can extend the PHP processing to handle it. It's simply easier if you can assume parents always come first.

True, or you could skip all the PHP business and use a database that can do recursion and generate JSON that PHP only has to json_decode() to get the array :-)

kicken · October 2, 2013

Your page_enfant function is not designed properly. It always references the root using $pages[0][children] so it cannot go any deeper than one level.

The way it should be designed is to just accept a $page argument. It would output the li tag for the $page argument then foreach() over the ['children'] sub array for that page, calling itself once for each child.

function page_enfant($page){
  echo $page['name'];
  foreach ($page['children'] as $child){ 
     page_enfant($child);
  }
}

drisate · October 2, 2013

I can't get your exemple to work ...

function mapTree($dataset) {
    $tree = array();
    foreach ($dataset as $id=>&$node) {
        if ($node['parent'] === null) {
            $tree[$id] = &$node;
        } else {
            if (!isset($dataset[$node['parent']]['children'])) $dataset[$node['parent']]['children'] = array();
            $dataset[$node['parent']]['children'][$id] = &$node;
        }
    }
    
    return $tree;
}

// Liste des pages
function page_treeview(){GlOBAL $_SESSION;

    $pages = mysql_query("SELECT id, parent, titre FROM pages"); $t=0;
    while($page = mysql_fetch_array($pages)){
        $tree[$page[id]][name] = $page[titre];
        $tree[$page[id]][parent] = $page[parent];
        $tree[$page[id]][id] = $page[id];
        $t++;
    }
    

    $pages = mapTree($tree,"0");
    
    if($pages[0][children]){
        
        echo '<form method="POST" id="ajaxform" class="load_form">
        <ul class="menu-tree accordion dark strips">';  
        
        foreach($pages[0][children] as $page){
                        
            if ($page[parent]=='0'){
                echo '<li>
                        <input type="checkbox" id="category-'.$page[id].'" />
                        <label for="category-'.$page[id].'">
                            <i onclick="location.href=\'index.php?mod=page&id='.$page[id].'&pid='.$page[parent].'\'" class="icon-edit-sign"></i>
                            <i onclick="location.href=\'index.php?mod=page&del='.$page[id].'\'" class="icon-remove-sign"></i>
                            <i onclick="location.href=\'index.php?mod=page&id='.$page[id].'&pid='.$page[parent].'&action=add\'" class="icon-plus-sign-alt"></i>
                             '.$page[name].'
                            <span class="notification"></span>
                        </label>';
                        page_enfant($page[id], $pages);          
                echo'</li>';
            }
            
        }
        echo '</ul><br><input type="submit" value="Sauvegarder l\'ordre" name="saveordre"></form>';
    }
    
}

function page_enfant($id, $page){
    
  echo "\n".'<ul>';
      foreach ($page['children'] as $child){
        
            echo "\n".'<li>
                    <input type="checkbox" id="category-'.$child[id].'" />
                    <label for="category-'.$child[id].'">
                        <i class="icon-edit-sign"></i>
                        <i class="icon-remove-sign"></i>
                        <i class="icon-plus-sign-alt"></i> '.$child[name].'
                        <span class="notification"></span>
                    </label>';
             
             page_enfant($child);
             
             echo'</li>'."\n";
      }
  echo '</ul>'."\n";
}

drisate · October 3, 2013

* bump *

drisate · October 3, 2013

Ok i finaly got this to work and it's VERY VERY VERY fast compare to what i was doing previously.

// Create the page array
// FROM: http://www.tommylacroix.com/2008/09/10/php-design-pattern-building-a-tree/
// Thx !
function mapTree($dataset) {
    $tree = array();
    foreach ($dataset as $id=>&$node) {
        if ($node['parent'] === null) {
            $tree[$id] = &$node;
        } else {
            if (!isset($dataset[$node['parent']]['children'])) $dataset[$node['parent']]['children'] = array();
            $dataset[$node['parent']]['children'][$id] = &$node;
        }
    }
    
    return $tree;
}

// Start the page tree view
function page_treeview(){

    // Retreive all pages of the DB and formating it for mapTree()
    $pages = mysql_query("SELECT id, parent, titre FROM pages"); $t=0;
    while($page = mysql_fetch_array($pages)){
        $tree[$page[id]][name] = $page[titre];
        $tree[$page[id]][parent] = $page[parent];
        $tree[$page[id]][id] = $page[id];
        $t++;
    }
    
    // Creating the recursive page array
    $pages = mapTree($tree,"0");

    // Looping the first level
    if($pages[0][children]){
        
        echo '<ul class="menu-tree accordion dark strips">';  
        
        foreach($pages[0][children] as $page){
                        
            if ($page[parent]=='0'){
                echo '<li>'.$page[name];
                        if ($page[children]){
                        page_enfant($page[children]);
                        } 
                echo'</li>';
            }
            
        }
        echo '</ul>';
    }
    
}

// Recursive function
function page_enfant($sub_page){
        
  echo "\n".'<ul>';
         foreach ($sub_page as $child){
                   
            echo "\n".'<li>'.$child[name];
                 
                 if ($child[children]){
                    page_enfant($child[children]);
                 }
             
             echo'</li>'."\n";
             
        }
      
  echo '</ul>'."\n";
}
 
// How to use??
echo page_treeview();

This code will generate a <ul><li> infinite tree structure in only one SQL line

I hope it helps

Sign In

Fast tree

Recommended Posts

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Join the conversation

Important Information