MPTT — Managing Hierarchical Data in Mysql

For a hierarchical table which has depth more than 3 is a tough one to fetch data and show it. And for a bigger table its near to impossible to fetch. It will give you time out. Even if you manage the time the application will be slower. Let me give an example. Suppose you have a region table which have got 4 level of depth and has data about only 100 rows. The levels are State, City, Town, Area. So to show it hierarchically you will have to loop all the data, for this case it will 4 loops which is 100*100*100*100 = 100000000, you might lesser it a bit by some breaks but still it is a n^3 times algorithm which will slow your system definitely and crash your system eventually.

So there is a technique which is called MPTT — modified preordered tree traversal algorithm for multiple depth search or to search hierarchical data. Its a very simple technique where the table in our case the region table is ordered accordingly and serve before the fetch. This technique reminds me the concept of set while I was in grade 8.

 MPTT    Managing Hierarchical Data in Mysql

From the above image you can see

New York State has the range from 1 – 8
New York City has the range from 2 – 7
Manhattan has the range from 3 – 6
Midtown has the range from 4 – 5

Similarly if you have more city or town you need to add them up and whole range would be larger then, for instance if you add two other city Long Island and Columbia then the range should be

New York State has the range from 1 – 12
New York City has the range from 2 – 7
Manhattan has the range from 3 – 6
Midtown has the range from 4 – 5
Long Island has the range from 8 – 9
Columbia has the range from 10 – 11

And you have to make the data base like this. Here we will use the left and right column for the range. Like for new york city the left column should be 2 and the right is 7. Every other rows should have the same thing. Now as I have used symfony2 with doctrine 2.2 with dql I will show how you can generate the full tree

 public function crossJoin(){

 $q = $this->_em->createQuery("
SELECT, node.regionId, node.regionName
FROM ViveZeaBundle:RegionRedefines AS node,
ViveZeaBundle:RegionRedefines AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.regionId
ORDER BY node.lft  ");
return $q->getResult();


Now in my controller I call it and I have used jquery tree to show it.

$tree = $em->getRepository("ViveZeaBundle:RegionRedefines")->crossJoin();
$result = '';
foreach ($tree as $node) {
foreach($tree as $traceTree){
if($traceTree['hierarchyId'] == $node['regionId']){
$node_depth = $node['depth'];
$node_name = $node['regionName'];
if ($node_depth == $current_depth) {
if ($counter > 0)
$result .= '';

elseif ($node_depth > $current_depth) {
$result .= ”, $current_depth – $node_depth) . ”;
$current_depth = $current_depth – ($current_depth – $node_depth);

$result .= ‘<li ‘; if($trace_last_node!=””){ if($catName!=””) $tit = $catName.”-in-“.$node[‘regionName’]; else $tit = $node[‘regionName’];              $tit = preg_replace(“/[^a-zA-Z0-9\/ _-]/”, ”, $tit); $tit = str_replace(‘ ‘,’-‘, ucwords($tit)); $tit = str_replace(‘–‘,’-‘,$tit); $result .= ‘class = “expandable”‘;

$result .=$basePath.’/’.$tit.’/’.$categoryId.’/’.$node[‘regionId’].’/0/ $node_name . ”;

$tit = $catName.”-in-“.$node[‘regionName’];
$tit = $node[‘regionName’];
$result .=$basePath.’/’.$tit.’/’.$categoryId.’/’.$node[‘regionId’].’/0/ $node_name . ”;
$temp = ” . $node_name . ‘ ‘;
$result .= str_repeat(”, $node_depth) . ”;
$result .= ”;

Now just return the result.

Leave a Reply

Your email address will not be published. Required fields are marked *