MPTT ( Modified Preorder Tree Traversal) issue in PHP

Question

Hi guys,

My first post here! Seems like this is the place to get wise ;)

I am currently in the middle of some testing with my first ever attempt to try the MPTT (Modified Preorder Tree Traversal) approach to storing data in my Mysql database with the help of PHP.

However, I am trying to find out the most performance-oriented way to get all list elements on a specific level, with a specific parent.

That could translate into getting the categories Saab and Chrysler from the image below, if the parent entered would be named "Bilar". (Which means Cars in Swedish, if that isnt your strongest side ;) )

As i cant post images, here's a link to the flowchart: http://www.phpsidan.nu/files/mptt/mptt1.png

Currently i have been doing two querys to do what i want, and quite some amount of code to calculate the level and spit out all the other elements on the same level.

Is there a better way to do this and by hopefully only using one query?

Thanks a lot!

Answer 1

hi and welcome to SO

http://dev.mysql.com/tech-resources/articles/hierarchical-data.html has infos and query examples on nested sets

getting immediate children in NS is complicated, therefore some people prefer to store explicit parent_id along with "left" and "right" pointers.

Answer 2

I am sure this could be optimized, however assuming you have the columns "name", "lft" and "rgt", the following will give you the level 2 siblings of "Bilar".

SELECT node.name,                                                                                                                                     
       node.lft AS sort,                                                                                                                                                                                                                                                               
       (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth                                                                        

FROM car AS node,                                                                                                                                  
     car AS parent,                                                                                                                                
             car AS sub_parent,                                                                                                                            
             ( SELECT node.name, (COUNT(parent.name) - 1) AS depth                                                                                          
                 FROM car AS node,                                                                                                                         
                      car AS parent                                                                                                                        
                WHERE node.lft BETWEEN parent.lft AND parent.rgt                                                                                            
                  AND node.name = "Bilar"                                                                                                                       
             GROUP BY node.name                                                                                                                             
             ORDER BY node.lft) AS sub_tree

WHERE node.lft BETWEEN parent.lft AND parent.rgt                                                                                                     
  AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt                                                                                             
  AND sub_parent.name = sub_tree.name

GROUP BY node.name HAVING depth <= 2                                                                                                                 
ORDER BY node.lft