Zebra_Mptt, a PHP class providing an implementation of the modified preorder tree traversal algorithm

Get the latest updates on this PHP library via RSS

What is Modified Preorder Tree Traversal?

MPTT is a fast algorithm for storing hierarchical data (like categories and their subcategories) in a relational database. This is a problem that most of us have had to deal with, and for which we’ve used an adjacency list, where each item in the table contains a pointer to its parent and where performance will naturally degrade with each level added as more queries need to be run in order to fetch a subtree of records.

The aim of the modified preorder tree traversal algorithm is to make retrieval operations very efficient. With it you can fetch an arbitrary subtree from the database using just two queries. The first one is for fetching details for the root node of the subtree, while the second one is for fetching all the children and grandchildren of the root node.

The tradeoff for this efficiency is that updating, deleting and inserting records is more expensive, as there’s some extra work required to keep the tree structure in a good state at all times. Also, the modified preorder tree traversal approach is less intuitive than the adjacency list approach because of its algorithmic flavour.

For more information about the modified preorder tree traversal method, read this excellent article called Storing Hierarchical Data in a Database Article.

What is Zebra_MPTT?

Zebra_MPTT is a PHP class that provides an implementation of the modified preorder tree traversal algorithm making it easy for you to use MPTT in your PHP applications.

It provides methods for adding nodes anywhere in the tree, deleting nodes, moving and copying nodes around the tree and methods for retrieving various information about the nodes.

Zebra_MPTT uses table locks making sure that database integrity is always preserved and that concurrent MySQL sessions don’t compromise data integrity. Also, Zebra_MPTT uses a caching mechanism which has as result the fact that regardless of the type, or the number of retrieval operations, the database is read only once per script execution.

Top

Features review

  • provides methods for adding nodes anywhere in the tree, deleting nodes, moving and copying nodes around the tree and methods for retrieving various information about the nodes
  • uses a caching mechanism which has as result the fact that regardless of the type, or the number of retrieval operations, the database is read only once per script execution
  • uses table locks making sure that database integrity is always preserved and that concurrent MySQL sessions don’t compromise data integrity
  • has comprehensive documentation
  • code is heavily commented and generates no warnings/errors/notices when PHP’s error reporting level is set to E_ALL
Top

Requirements

PHP 4.4.9+, MySQL 4.1.22+

Top

Installation

Download the latest version, unpack it, and put it in a place accessible to your scripts. After unpacking, you will notice a directory called “install” containing a file named “mptt.sql”. This file contains the SQL code that will create a table that is used by the class to store the data. Import or execute the SQL code using your preferred MySQL manager (like phpMyAdmin or the fantastic Adminer) into a database of your choice.

Top

How to use

<?php

// include the Zebra_Mptt class
require 'path/to/Zebra_Mptt.php';

// instantiate a new object
$mptt = new Zebra_Mptt();

// populate the table

// add 'Food' as a topmost node
$food = $mptt->add(0, 'Food');

// 'Fruit' and 'Meat' are direct descendants of 'Food'
$fruit = $mptt->add($food, 'Fruit');
$meat = $mptt->add($food, 'Meat');

// 'Red' and 'Yellow' are direct descendants of 'Fruit'
$red = $mptt->add($fruit, 'Red');
$yellow = $mptt->add($fruit, 'Yellow');

// add a fruit of each color
$mptt->add($red, 'Cherry');
$mptt->add($yellow, 'Banana');

// add two kinds of meat
$mptt->add($meat, 'Beef');
$mptt->add($meat, 'Pork');

// move 'Banana' to 'Meat'
$mptt->move($banana, $meat);

// get a flat array of descendants of 'Meat'
$mptt->get_children($meat);

// get a multidimensional array (a tree) of all the data in the database
$mptt->get_tree();

?>

Top

Download

version 2.2 (zip, 14.1Kb)
If you find this library to be useful to you, you can support the author by donating a small amount via PayPal:

Zebra_Mptt is distributed under the LGPL.

In plain English, this means that you have the right to view and to modify the source code of this software, but if you modify and distribute it, you are required to license your copy under a LGPL-compatible license, and to make the entire source code of your derivation available to anybody you distribute the software to.

You also have the right to use this software together with software thas has different licensing terms (including, but not limited to, commercial and closed-source software), and distribute the combined software, as long as state that your software contains portions licensed under the LGPL license, and provide information about where the LGPL licensed software can be downloaded.

If you distribute copies of this software you may not change the copyright or license of this software.


You may also like:

Top

Documentation

Documentation Become a ninja.
Read the comprehensive documentation.
Top

Changelog

Click on a version to expand/collapse information.

version 2.2 (January 20, 2012)
  • fixed an issue with some constructs in the code that would trigger a “Strict standards: Only variables should be passed by reference” warnings in PHP 5.3+; thanks Juan Gutierrez
version 2.1 (June 15, 2011)
  • fixed a bug where some of the methods were not working anymore if custom column names were used for the MySQL table (thanks to hisham for reporting);
version 2.0 (June 11, 2011)
  • entire code was audited and improved;
  • added new methods;
  • many documentation refinements;
version 1.0 (July 22, 2009)
  • initial release;

Top

32 responses to “Zebra_Mptt, a PHP class providing an implementation of the modified preorder tree traversal algorithm”

Follow the comments via RSS
  • hisham, 2011-06-15, 09:56

    Hi Stefan,

    Thank you for the nice and practical zebra_mptt class. I just want to report an error. I have a table with the name “op_category_module” and the id colomn “cat_mod_id”.

    the constractor is like this :

    function Zebra_Mptt($table_name = ‘op_category_module’, $id_column = ‘cat_mod_id’, $title_column = ‘title’, $left_column = ‘lft’, $right_column = ‘rgt’, $parent_column = ‘cat_parent_id’) {

    But in execution, i have this error Notice: Undefined index: id in D:\wamp\www\zebra_mptt2.0\Zebra_Mptt.php on line 954

    // add node to the stack of nodes
    $nodes[$properties['id']] = (!empty($parents) ? str_repeat($separator, count($parents)) : ”) . $properties[$this->properties['title_column']];

    Thanks for help

    Reply
    • Stefan Gabos, 2011-06-15, 12:44

      thanks hisham for taking the time to write back. it is indeed an error. i’ll have a look later on today and let you know. thanks!

    • Stefan Gabos, 2011-06-15, 18:29

      The fixed version is now available for download. Thank you for letting me know about the bug!

  • hisham, 2011-06-16, 08:41

    You’re welcome. And you’re the one i should thank

    Reply
  • nilp0inter, 2011-09-08, 19:18

    Great job! Thank you.

    Reply
  • Tomas, 2011-09-29, 18:34

    Firstly thank you for great library.
    But i have strange behavior or bug in the library. For example:

    Root
    ->Node
    –>Subnode

    If i delete “Node”, the nested set left and right values are updated correctly but the parent_id of the “Subnode” leaves the same (id of “Node”) and does not updates to “Root” id.

    Reply
    • Stefan Gabos, 2011-09-29, 19:49

      tomas, that is how it is supposed to work; the ID is an auto_increment column.

      imagine a scenario where we use the modified preorder tree traversal implementation for organizing product categories in a database; you’ve assigned one thousand products to a category ID; you would bring chaos if the category IDs would suddenly change.

  • Jirka, 2011-10-11, 07:22

    Hi Stefan, I use your great library. Thanks for it.

    I have one thing I would like you to sugget for implementing. It would be fine to implement “scope” parametr to have independent multiple trees in one table like e.g. kohana mptt. Would do you think?

    Reply
    • Stefan Gabos, 2011-10-11, 07:29

      jirka, you can already create unlimited number of trees in the same table. each entry that has no parent, is the top of a new tree. so, whenever you have

       $node = $mptt->add(0, 'Top of a new tree');

      you are starting a new, independent tree.

    • Jirka, 2011-10-11, 07:57

      Oh, I see. This is so great and you are awesome :]

  • Ayan Banerjee, 2011-12-01, 13:19

    How can I insert other values in the mysql table along with mptt?? is this possible?

    Reply
  • KS, 2011-12-04, 19:32

    Interesting concept and class. Thanks for sharing! I’ve looked a bit at the documentation, but not at the class code itself. I noticed that I can control the $position of a child node. I have a question about this.
    If I have three children of a node and want to add a fourth child at position 2 of the four. Will the add() with parameter $position take automatically care of this? Doesn’t this actually require all of the tree rights and lefts “above” that one getting renumbered? Which could be thousands of records. I mean it could be quite ressource-intensive and need some time – in contrast to adding one record to a parent-child table.

    I wonder if it makes sense to combine the two methods. for instance we have a hierarchy of two category levels (at the moment, we may want to add more levels in the future). Only the bottom-level category can hold other items (in this case a lot of questions and even more possible answers). Would it make sense to use the MPTT method for the categories (of any level), but the classy parent/child method to identify the children relation (questions and answers) for a category node?
    In this case the updating for the categories would only involve updating the categories (which are maybe several dozen to two hundred records). And not any of the several thousand questions and answers.

    Reply
    • Stefan Gabos, 2011-12-05, 08:46

      The MPTT algorithm is useful because you can have infinitely nested trees from which you can then retrieve putting minimum load on the database. Simply put, the MPTT algorithm is faster than any other method when *retrieving* data even if this means putting more stress on the database when inserting records; but, as the “selects” severely outnumber “inserts” in most applications, this is the way you should go

  • Juan Gutierrez, 2012-01-20, 05:42

    I was getting this warning: Strict standards: Only variables should be passed by reference in C:\xampp\htdocs\lib\Zebra_Mptt.php on line 198
    I solved wih this:
    $arraySlice = array_slice($children, $position – 1, 1);
    $children = array_shift($arraySlice);

    Reply
    • Stefan Gabos, 2012-01-20, 07:31

      ah, the warnings since PHP 5.3! :) Thanks!

      also, note that the construct can be found in several places throughout the code, and needs to be changed everywhere

  • ionut, 2012-01-27, 13:14

    you have a error in the class file
    Parse error: syntax error, unexpected T_STRING in Zebra_Mptt.php on line 201

    Reply
    • Stefan Gabos, 2012-01-27, 13:21

      thanks! somehow instead of the minus sign there was a dash…it’s fixed now, please download the package again.

    • ionut, 2012-01-27, 13:24

      hmm line 425 and 1206 same problem

    • Stefan Gabos, 2012-01-27, 13:33

      fixed. thanks a lot!

  • ionut, 2012-01-27, 14:22

    np

    i tried to use your class (to store multple trees in a table) based on the example posted

    $mptt = new Zebra_Mptt();
$a = $mptt->add(0, '1');
$b = $mptt->add($a, '1.1');
$c = $mptt->add($b, '1.1.1');

$aa = $mptt->add(0, '2');
$ab = $mptt->add($aa, '2.1');

    how can i get the first tree ?
    how about the second ?
    would you recommend this for a threaded comment system ? or i need to look for something else ?

    Reply
    • Stefan Gabos, 2012-01-27, 14:31

      there’s a lot written in the documentation; try every method and see what it does. you are probably looking for the get_tree() and get_children() methods.

      always use

      print_r('<pre>');
print_r($variable);

      to have a better view and understanding of the results (instead of var_dump)

      $result = $mptt->get_tree(...);
print_r('<pre>');
print_r($result);

      and yes, this is what you should be using

    • ionut, 2012-01-27, 14:40

      i looked at at the docs before i asked but

      $mptt->get_tree(...)

      returns only the children without the root node

      $mptt = new Zebra_Mptt();
$a = $mptt->add(0, '1');
$b = $mptt->add($a, '1.1');
$c = $mptt->add($b, '1.1.1');

$aa = $mptt->add(0, '2');
$ab = $mptt->add($aa, '2.1');

print_r('<pre>');
print_r($mptt->get_tree($a));

print_r('<pre>');
print_r($mptt->get_tree($aa));

      i will look at the algorithm and addapt it for my needs

      thanks for sharing and your responses
      i know atleast at what algorithm to look

    • Stefan Gabos, 2012-01-27, 14:56

      the root node is $a and $aa…

  • JACKMAN, 2012-02-01, 15:23

    hi Stefan,
    Do you have some Code snippets to show
    How to integrate Zebar_Mptt with Zebra_Database?

    Reply
    • JACKMAN, 2012-02-01, 15:26

      or Example how to Add a database field in the `mptt` table?

  • Bruno, 2012-04-12, 02:41

    Hello,

    How can i move a node up or down ? I know how i can use the move for that, but when using the move i need to have the id to where i want to move the node, what i need is something more moveUp($node) and moveDown($node) and they get the next or previous node id and then use the move function…

    Reply
    • Stefan Gabos, 2012-04-12, 05:58

      i’ll consider that for the next version. thanks!

    • Bruno, 2012-04-12, 18:33

      And when are going to be releasing it ?

      Thanks =)

  • Paul, 2012-05-16, 15:29

    super useful code, thankyou. but looking at your code get_tree is still recursive I thought the point was to be able to output the tree without using recursion? is recursion the only way to do multi-dimensional arrays?

    Reply
    • Stefan Gabos, 2012-05-17, 13:19

      don’t worry about it: on site point’s website the talk is about a *single* tree – the “food” tree. it is highly unlikely that you will be having more than a single tree so this function will never use recursion.

  • Paul, 2012-05-16, 15:40

    I basically want to output the whole tree in nested tags without using recursion if possible. The original sitepoint article had code about how to indent the tree, could you use that method to open and close the tags.

    Could that method also be used to build the json string for the multi-dimensional array, hence outputting the tree as a multi-dimensional arrays without using recursion?

    Reply
  • Paul, 2012-05-16, 17:19

    my json idea wouldn’t work, because json_decode would end up doing recursion anyway.

    I wrote a listing function, and then realised that get_selectables could be adapted to output nested unordered list tags, by tracking the depth you could open and close the lists correctly.

    Reply

Leave a Reply

Your email address will not be published
You can use <strong>, <em>, <a>, <img>, <code>
Characters are not case-sensitive