Jump to content


Photo

Fast tree


Best Answer drisate, 03 October 2013 - 01:59 PM

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

Go to the full post


  • Please log in to reply
16 replies to this topic

#1 drisate

drisate

    Advanced Member

  • Members
  • PipPipPip
  • 796 posts

Posted 02 October 2013 - 09:50 AM

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

?>

 


www.VersatileBB.com - Open Source Board
Easy to use and modify board for your website. A very good alt to all those to much  popular boards

#2 drisate

drisate

    Advanced Member

  • Members
  • PipPipPip
  • 796 posts

Posted 02 October 2013 - 12:00 PM

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
www.VersatileBB.com - Open Source Board
Easy to use and modify board for your website. A very good alt to all those to much  popular boards

#3 Psycho

Psycho

    Advanced Member

  • Gurus
  • 10,907 posts
  • LocationCanada

Posted 02 October 2013 - 12:09 PM

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.


The quality of the responses received is directly proportional to the quality of the question asked.

I do not always test the code I provide, so there may be some syntax errors. In 99% of all cases I found the solution to your problem here: http://www.php.net

#4 Psycho

Psycho

    Advanced Member

  • Gurus
  • 10,907 posts
  • LocationCanada

Posted 02 October 2013 - 12:34 PM

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.


The quality of the responses received is directly proportional to the quality of the question asked.

I do not always test the code I provide, so there may be some syntax errors. In 99% of all cases I found the solution to your problem here: http://www.php.net

#5 vinny42

vinny42

    Advanced Member

  • Members
  • PipPipPip
  • 414 posts

Posted 02 October 2013 - 12:37 PM


 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.



#6 drisate

drisate

    Advanced Member

  • Members
  • PipPipPip
  • 796 posts

Posted 02 October 2013 - 12:46 PM

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, 02 October 2013 - 12:54 PM.

www.VersatileBB.com - Open Source Board
Easy to use and modify board for your website. A very good alt to all those to much  popular boards

#7 drisate

drisate

    Advanced Member

  • Members
  • PipPipPip
  • 796 posts

Posted 02 October 2013 - 01:12 PM

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

( it's 110 Mo ... )


www.VersatileBB.com - Open Source Board
Easy to use and modify board for your website. A very good alt to all those to much  popular boards

#8 kicken

kicken

    Wiser? Not exactly.

  • Gurus
  • 2,731 posts
  • LocationBonita, FL

Posted 02 October 2013 - 02:07 PM

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.
Recycle your old CD's, don't trash them!
Did I help you out?  Feeling generous? I accept tips via Paypal or Bitcoin @ 14mDxaob8Jgdg52scDbvf3uaeR61tB2yC7

#9 vinny42

vinny42

    Advanced Member

  • Members
  • PipPipPip
  • 414 posts

Posted 02 October 2013 - 02:12 PM

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?



#10 Psycho

Psycho

    Advanced Member

  • Gurus
  • 10,907 posts
  • LocationCanada

Posted 02 October 2013 - 02:18 PM

You can't do recursion in a join.

 

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


Edited by Psycho, 02 October 2013 - 02:18 PM.

The quality of the responses received is directly proportional to the quality of the question asked.

I do not always test the code I provide, so there may be some syntax errors. In 99% of all cases I found the solution to your problem here: http://www.php.net

#11 kicken

kicken

    Wiser? Not exactly.

  • Gurus
  • 2,731 posts
  • LocationBonita, FL

Posted 02 October 2013 - 02:19 PM

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.
Recycle your old CD's, don't trash them!
Did I help you out?  Feeling generous? I accept tips via Paypal or Bitcoin @ 14mDxaob8Jgdg52scDbvf3uaeR61tB2yC7

#12 drisate

drisate

    Advanced Member

  • Members
  • PipPipPip
  • 796 posts

Posted 02 October 2013 - 02:25 PM

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, 02 October 2013 - 02:28 PM.

www.VersatileBB.com - Open Source Board
Easy to use and modify board for your website. A very good alt to all those to much  popular boards

#13 vinny42

vinny42

    Advanced Member

  • Members
  • PipPipPip
  • 414 posts

Posted 02 October 2013 - 02:35 PM


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



#14 kicken

kicken

    Wiser? Not exactly.

  • Gurus
  • 2,731 posts
  • LocationBonita, FL

Posted 02 October 2013 - 03:17 PM

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

Recycle your old CD's, don't trash them!
Did I help you out?  Feeling generous? I accept tips via Paypal or Bitcoin @ 14mDxaob8Jgdg52scDbvf3uaeR61tB2yC7

#15 drisate

drisate

    Advanced Member

  • Members
  • PipPipPip
  • 796 posts

Posted 02 October 2013 - 03:31 PM

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


www.VersatileBB.com - Open Source Board
Easy to use and modify board for your website. A very good alt to all those to much  popular boards

#16 drisate

drisate

    Advanced Member

  • Members
  • PipPipPip
  • 796 posts

Posted 03 October 2013 - 11:39 AM

* bump *


www.VersatileBB.com - Open Source Board
Easy to use and modify board for your website. A very good alt to all those to much  popular boards

#17 drisate

drisate

    Advanced Member

  • Members
  • PipPipPip
  • 796 posts

Posted 03 October 2013 - 01:59 PM   Best Answer

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


www.VersatileBB.com - Open Source Board
Easy to use and modify board for your website. A very good alt to all those to much  popular boards




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Cheap Linux VPS from $5
SSD Storage, 30 day Guarantee
1 TB of BW, 100% Network Uptime

AlphaBit.com