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.2 (zip, 14.2Kb)
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.2 (November 06, 2012)
  • fixed a bug where the last node returned by the “get_path” method did not have the correct key; thanks to Gus;
version 2.2.1 (July 19, 2012)
  • fixed a bug that escaped fixing in the previous release, where the get_selectables() method was triggering a “Strict Standards” notice in PHP 5.3+; thanks to mrplugins
  • fixed a bug where the “copy” method was not working correctly; thanks to Victor Hugo Contreras
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

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

Follow the comments via RSS
  • mrplugins, 2012-05-30, 16:32

    can you write an example to put the result array in a sistem? please

    Reply
    • hrubost, 2012-11-06, 14:06 
      //code by acmol
function array2ul($array) {
  $out="";
  foreach($array as $key => $elem){
    if(!is_array($elem)){
      $out=$out."$key:[$elem]";
    }
    else $out=$out."$key".array2ul($elem)."";
  }
  $out=$out."";
  return $out; 
}

echo array2ul($mtpp->get_tree());
  • mrplugins, 2012-05-30, 16:43

    list sistem like <ul><li>

    Reply
  • mrplugins, 2012-06-01, 08:39

    get_selectables give me an error:
    Strict Standards: Only variables should be passed by reference in C:\inetpub\mio\zebra\Zebra_Mptt.php on line 956

    Reply
    • Stefan Gabos, 2012-06-01, 20:04

      thanks!
      to fix it, change the whole block to

      // if the node has any parents
if (count($parents) > 0) {

  $keys = array_keys($parents);

  // iterate through the array of parent nodes
  while (array_pop($keys) < $properties[$this->properties['right_column']])

    // and remove parents that are not parents of current node
    array_pop($parents);

}
  • mrplugins, 2012-06-01, 20:52

    how can i order the array by title asc? is it possible?

    sorry for my english

    Reply
  • victor, 2012-07-17, 03:56

    function copy, not copy entire node with childrens into other node

    Reply
    • Stefan Gabos, 2012-07-17, 07:21

      thanks victor, i’ll have a look

      update

      victor, i did some tests and the copy method seems to be working fine. can you be more specific about how and why it is not working? thanks!

    • Victor, 2012-07-18, 02:53

      oki, example:

      child_node1
      |——–child 1-1
      |——–child 1-2
      |——–child 1-3

      child_node2

      copy(child_node1, child_node2)

      child_node2 =

      child_node2
      |———child_node1

      without child 1-1 etc…

    • Victor, 2012-07-18, 05:08

      I think the problem is when you call again get_tree

  • Victor, 2012-07-18, 05:17

    the first get_tree is correct, the second get_tree not.. a process reset parent id node.. check data table

    Reply
  • Victor, 2012-07-18, 13:44

    Hi Steffan, send you an email with 2 attachments. Thanks :)

    Reply
  • Florencia, 2012-09-27, 11:58

    Thank you Stefan, your class saved me a lot of time and work, regrads from Argentina!

    Reply
    • Stefan Gabos, 2012-09-27, 12:57

      no, thank YOU for taking the time and posting back :)

  • Gus, 2012-11-05, 03:14

    in : function get_path($node)

    $parents [] = $this->lookup [$node];
    should be changed to
    $parents [$node] = $this->lookup [$node];

    otherwise this will mess-up your array indicies

    :)

    Reply
    • Stefan Gabos, 2012-11-05, 08:22

      it should make no difference as all indices in $parents will be unique anyway

  • Gus, 2012-11-06, 20:30

    >it should make no difference as all indices in $parents will be unique >anyway

    Previous parents have
    $parents[node_id] = node_info

    when you do

    $parents[] = [node_info]
    On the final go , the index for the last entry wiill not be the node id , but a +1 index PHP assigns…

    Reply
    • Stefan Gabos, 2012-11-06, 20:43

      oh, i get it now! you are right! the fixed version will be available soon for downloading. thanks a lot!

  • David, 2013-01-08, 14:28

    Hi Stefan,

    I’ve started to play around with Zebra_Mptt and immediately ran into a problem, which led me to look up the function. It appears that the mysql functions you use are being deprecated in future versions of PHP. Do you plan to update the library to be compatible with future versions of PHP?

    Thanks!

    Reply
    • Stefan Gabos, 2013-01-08, 18:12

      don’t worry, the mysql extension will most likely be available for the years to come; nevertheless, I do plan to port it to mysqli but cannot give you a time frame.

  • Kaeru, 2013-04-05, 19:40

    Sounds silly but how do I add in additional fields to be displayed?

    Reply
  • Kaeru, 2013-04-05, 22:03

    Also since this loads the entire tree into memory, how would this handle extended trees of say 100,000 levels?

    Reply
  • Kaeru, 2013-04-07, 22:01

    Did some testing and this is a fine example but probably would be better suited without the caching of the fields, good for small datasets but once you hit 10000 or more takes up a huge chunk of memory

    Reply
  • Edgar Veiga, 2013-05-10, 16:50

    Hi! first of all, thanks for the great work!

    I think I’ve spotted a bug in the method get_parent.

    You should be returning:
    $this->lookup[$this->lookup[$node][$this->properties['parent_column']]]

    To ensure returning all of the parent properties and not only the ID.

    Best regards!

    Reply
    • Stefan Gabos, 2013-05-14, 06:36

      thanks, i’ll look into it

« Older comments

Leave a Reply

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