Jump to content

Fast tree


drisate
Go to solution Solved by drisate,

Recommended Posts

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();
?>
 

Link to comment
Share on other sites

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
Link to comment
Share on other sites

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.

Link to comment
Share on other sites

 


 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.

Link to comment
Share on other sites

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 2O(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 by drisate
Link to comment
Share on other sites

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.

Link to comment
Share on other sites

 

Both these solutions are of exponential time complexity 2O(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?

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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 by drisate
Link to comment
Share on other sites

 


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 :-)

Link to comment
Share on other sites

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);
  }
}
Link to comment
Share on other sites

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";
}

Link to comment
Share on other sites

  • Solution

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

Link to comment
Share on other sites

This thread is more than a year old. Please don't revive it unless you have something important to add.

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.