Reordering nested sets using PHP and Javascript

The adjancency method

Representing a tree of nodes, for example product categories, in a relational database is not hard. The most common way of doing it is to store a parentid with each node. This is also known as the adjacency list model. It is sometimes also referred to as the recursive model. Whatever the name it is easy to grasp. It is very simple to insert and move nodes around but it is not an optimal solution if you often select the whole tree from the database for displaying on a web page as you need to recursively select all children of nodes.

The nested set model

A much better solution is the nested set model. In this model trees are represented as nested sets. Instead of using a parentid you have a left and right value for each node expressing the relationship to other nodes. A tree of nodes can look like this.

        34
         |
         +--36
         |   |
         |   +--46
         |   |
         |   +--47
         |
         +--38
             |
            +--39

The same data can be viewed more graphically as nested sets. This is also the way they are stored in the database. Notice how the left and right values are numbered in order from the outermost left to the outermost right.

                            id:34
   +----------------------------------------------------+
   |             id:36                     id:38        |
   |   +------------------------+    +--------------+   |
   |   |    id:46      id:47    |    |     id:39    |   |
   |   |   +-----+    +-----+   |    |   +------+   |   |
  1|  2|  3|     |4  5|     |6  |7  8|  9|      |10 |11 |12
   |   |   +-----+    +-----+   |    |   +------+   |   |
   |   +------------------------+    +--------------+   |
   +----------------------------------------------------+

In the database this is stored as in the following table.

 +----+-----+-----+
 | id | lft | rgt |
 +----+-----+-----+
 | 34 | 1   | 12  |
 | 36 | 2   |  7  |
 | 46 | 3   |  4  |
 | 47 | 5   |  6  |
 | 38 | 8   | 11  |
 | 39 | 9   | 10  |
 +----+-----+-----+

This allow you to select the full tree with only one select statement. Normally you select the full list of nodes including the depth of each node as shown below in the small table containing id and depth. It is then easy to loop over the data in PHP to produce a nice tree in HTML/CSS.

The data below can be displayed as the the tree on right. The depth is in parenthesis.

 +----+-------+        34 (0)
 | id | depth |         |
 +----+-------+         +--36 (1)
 | 34 | 0     |         |   | 
 | 36 | 1     |         |   +--46 (2)
 | 46 | 2     |         |   |
 | 47 | 2     |         |   +--47 (2)
 | 38 | 1     |         |
 | 39 | 2     |         +--38 (1)
 +----+-------+             |
                            +--39 (2)

Here is a more thorough article on how you use MySQL with nested sets.

On to the problem

Last night I was working on an application that display a full tree where the user must be able to to drag and drop nodes to reorder the tree. The problem is that it is much more difficult to insert or reorder the tree using the nested set model.

For the actual html I produced nested ordered lists using the OL and LI html element so that it was easy to use with the excellent MooTree script based on MooTools. (It does seem to have trouble with the latest version of MooTools though.) After reordering the structure it was easy to extract the tree list including the depth of each node. I sent this to the PHP backend to be handled there. The text data I sent to the PHP backend then look like below.

 34,0
 36,1
 46,2
 47,2
 38,1
 39,2

As you can see it looks exactly like the data I selected from the database previously. So I had to create a function in PHP that took this indata and produced a list of nodes with the correct left and right values. This list is then looped over to update all the nodes in the database.

function depth2nestedset($data)
{
  $lines = explode("\n", $data);
  $rows = array();
  $stack = array();

  $lft = 0;   // Left value
  $rgt = 0;   // Right value
  $plvl = -1; // Previous node level

  foreach($lines as $line) {
    list($id, $lvl) = explode(',', $line);

    // Skip empty/faulty lines
    if (trim($id) == '') {
      continue();
    }

    if ($lvl > $plvl) {
      $lft++;
      $rgt = 0;
      array_push($stack, $id);
    }
    else if ($lvl == $plvl) {
      $pid = array_pop($stack);
      $rows[$pid][2] = $rows[$pid][1] + 1;
      $lft = $lft + 2;
      $rgt = 0;
      array_push($stack, $id);
    }
    else {
      $lft = $lft + ($plvl - $lvl) + 2;

      $diff = $plvl - $lvl + 1;
      for($n = 0; $n < $diff; $n++) {
        $pid = array_pop($stack);
        $rows[$pid][2] = $lft - $diff + $n;
      }
      array_push($stack, $id);
    }

    $rows[$id] = array($id, $lft, $rgt);
    $plvl = $lvl;
  }

  $plvl++;
  $cnt = count($rows) * 2;
  $leftovers = count($stack);

  for($n = 0; $n < $leftovers; $n++) {
    $pid = array_pop($stack);
    $rows[$pid][2] = $cnt - $plvl-- + $n;
  }

  return $rows;
}

The resulting associated array that is returned looks like below.

Array
(
    [34] => Array
        (
            [0] => 34
            [1] => 1
            [2] => 12
        )
    [36] => Array
        (
            [0] => 36
            [1] => 2
            [2] => 7
        )
    [46] => Array
        (
            [0] => 46
            [1] => 3
            [2] => 4
        )
    [47] => Array
        (
            [0] => 47
            [1] => 5
            [2] => 6
        )
    [38] => Array
        (
            [0] => 38
            [1] => 8
            [2] => 11
        )
    [39] => Array
        (
            [0] => 39
            [1] => 9
            [2] => 10
        )
)

That makes the circle complete. From left/right values in the database to a node tree based on depths that is easy to manipulate in html and then back to left/right values. Hopefully this makes sense. Do you have a better solution or more examples on applications that do this I would love to hear about it.

Tags: Javascript, mysql, PHP