php / Mysql best tree structure

Question

I have to build a tree that will contain about 300 nodes inside it. The tree has no depth limitations. So it can have 3 or 15 levels. Each node can have an unlimited number of children.

The priority is to get a complete tree / subtree the faster as possible, but I also need to add nodes or move nodes sometimes but not that often.

I want to know the best way to store the tree in the database and the best way to retrieve the data, if possible, in php.

• OMG Ponies: This is what MySQL recommends: dev.mysql.com/tech-resources/articles/hierarchical-data.html
• hakre: @OMGPonies: That link is broken :(
• Marm: @hakre: This site is a copy/paste of what is was on the mysql site: mikehillyer.com/articles/managing-hierarchical-data-in-mysql

Answer 1

You can use a Nested Set Model as it yields very efficient queries. Check out Managing Hierarchical Data in MySQL and read the section called Nested Set Model.

If you're using an ORM like Doctrine, it includes nested set capabilities.

It can be difficult for some to grasp the nested set concepts of left and right. I have found that using those numbers as an analogy for the line numbers of open/close tags in an XML document, folks find it easier to grasp.

For instance, take the data example from the MySQL link above:

+-------------+----------------------+-----+-----+
| category_id | name | lft | rgt |
+-------------+----------------------+-----+-----+
| 1 | ELECTRONICS | 1 | 20 |
| 2 | TELEVISIONS | 2 | 9 |
| 3 | TUBE | 3 | 4 |
| 4 | LCD | 5 | 6 |
| 5 | PLASMA | 7 | 8 |
| 6 | PORTABLE ELECTRONICS | 10 | 19 |
| 7 | MP3 PLAYERS | 11 | 14 |
| 8 | FLASH | 12 | 13 |
| 9 | CD PLAYERS | 15 | 16 |
| 10 | 2 WAY RADIOS | 17 | 18 |
+-------------+----------------------+-----+-----+

If you take the lft, rgt fields and use them as line numbers for an XML document, you get:

1. <electronics>
2. <televisions>
3. <tube>
4. </tube>
5. <lcd>
6. </lcd>
7. <plasma> 
8. </plasma> 
9. </televisions>
10. <portable electronics>
11. <mp3 players>
12. <flash>
13. </flash>
14. </mp3 players>
15. <cd players>
16. </cd players>
17. <2 way radios>
18. </2 way radios>
19. </portable electronics>
20. </electronics>

Seeing it this way can make it much easier for some to visualize the resulting nested set hierarchy. It also makes it clearer why this approach improves efficiency as it makes it possible to select entire nodes without the need for multiple queries or joins.

• Dunhamzzz: I could never get my head around saving hierarchal data until you put it so simply.
• Martin Bean: Up-voting for the line numbers analogy. That’s amazing and I instantly "get" it now!
• provance: and how to insert/delete rows? Do I need to resset entire and both columns if a row is inserted or deleted ?

Answer 2

This is great article about it: Managing Hierarchical Data in MySQL. I used for a long time.

If you have some mathematical capabilities, you can really understand why it is so great!

Answer 3

 <?php
 $host = "localhost";
 //Database user name. 
 $login = "root";
 //Database Password.
 $dbpass = "";
 $dbname = "abc";
 $PDO = new PDO("mysql:host=localhost;dbname=$dbname", "$login", "$dbpass");
 $rows = array();
 $sql = 'SELECT id, parent_id, name FROM employee';
 $query = $PDO->prepare($sql);
 $query->execute();
 $rows = array();
 if (!$query)
 {
 $error = 'Error fetching page structure, for nav menu generation.';
 exit();
 }
 while($row = $query->fetch(PDO::FETCH_ASSOC)){
 if( strcasecmp($row['parent_id'],'null') === 0 || empty($row['parent_id']) ) {
 $row['parent_id'] = null;
 }
 $rows[] = $row;
 }
 // covert raw result set to tree
 $menu = convertAdjacencyListToTree(null,$rows,'id','parent_id','links');
 // echo '<pre>',print_r($menu),'</pre>';
 // display menu
 echo themeMenu($menu,1);
 /*
 * ------------------------------------------------------------------------------------
 * Utility functions
 * ------------------------------------------------------------------------------------
 */
 /*
 * Convert adjacency list to hierarchical tree
 *
 * @param value of root level parent most likely null or 0
 * @param array result
 * @param str name of primary key column
 * @param str name of parent_id column - most likely parent_id
 * @param str name of index that children will reside ie. children, etc
 * @return array tree
 */
 function convertAdjacencyListToTree($intParentId,&$arrRows,$strIdField,$strParentsIdField,$strNameResolution) {
 $arrChildren = array();
 for($i=0;$i<count($arrRows);$i++) {
 if($intParentId === $arrRows[$i][$strParentsIdField]) {
 $arrChildren = array_merge($arrChildren,array_splice($arrRows,$i--,1));
 }
 }
 $intChildren = count($arrChildren);
 if($intChildren != 0) {
 for($i=0;$i<$intChildren;$i++) {
 $arrChildren[$i][$strNameResolution] = convertAdjacencyListToTree($arrChildren[$i][$strIdField],$arrRows,$strIdField,$strParentsIdField,$strNameResolution);
 }
 }
 return $arrChildren;
 }
 /*
 * Theme menu
 *
 * @param array menu
 * @param runner (depth)
 * @return str themed menu
 */
 function themeMenu($menu,$runner) {
 $out = '';
 if(empty($menu)) {
 return $out;
 }
 $out.='<ul>';
 foreach($menu as $link) {
 $out.= sprintf(
 '<li class="depth-%u">%s%s</li>'
 ,$runner
 ,$link['name']
 ,themeMenu($link['links'],($runner+1))
 );
 }
 $out.='</ul>';
 return $out;
 }
 ?>