Nested set model

In the previous post I explained the adjacency list model and how to implement it in PHP. There is an alternative – the nested set model (also called modified preorder tree traversal). It is more complicated than the adjacency model but there is a reason why it might be better in certain situations:

• unlimited hierarchy levels

On the other hand, there are reasons why I wouldn’t recommend using it unless you have to:

• very complicated hierarchy modifications compared to the adjacency model (you often have to update almost the whole table)
• a small mistake in PHP code for modifying the hierarchy can break up the whole table (you must test your application carefully before deploying it to the production environment)

Look at the picture to get a better idea about what the nested set model looks like:

Pay special attention to the blue numbers – based on these numbers you can calculate the position of an item in the hierarchy. The schema (‘lft’ and ‘rgt’ are used because ‘left’ and ‘right’ are MySQL reserved words):

CREATE TABLE categories (
id INT NOT NULL AUTO_INCREMENT,
name VARCHAR(255) NOT NULL,
lft INT NOT NULL,
rgt INT NOT NULL,
PRIMARY KEY (id)
) ENGINE = INNODB;

Let’s populate the table with some content we can work with:

INSERT INTO categories (id, name, lft, rgt) VALUES
(NULL, 'Relational databases', 1, 12),
(NULL, 'SQLite', 2, 3),
(NULL, 'MySQL', 4, 9),
(NULL, 'PDO', 5, 6),
(NULL, 'Transactions', 7, 8),
(NULL, 'PostgreSQL', 10, 11);

The query to select the full tree is simple:

SELECT * FROM categories ORDER BY lft

PHP implementation

Displaying the tree in an unordered XHTML list is not the hardest part. There are two important formulas:

rgt < last rgt => increment the hierarchy level (move one level down)
lft - last lft > 2 => decrement the hierarchy level (move one level up)

Therefor you can create the unordered list by keeping a track of left and right values:

Modifying the hierarchy

This is where it gets interesting. Modifying the hierarchy created by the nested set model or in other words adding, updating or removing branches (nodes) from the tree while keeping the hierarchy integrity.

Adding nodes

There are two ways how to add a new node – from the left and from the right. Both have very similar implementation (I will show you just the latter). Before I show you how to do it here is another important formula:

(rgt - lft - 1) / 2 = number of children nodes

In theory, what you need to do is add a new node and update all nodes to the right (those that have higher ‘rgt’ value). First, here is the algorithm in the pseudo language:

get a parent node

for all nodes
    if rgt >= parent->rgt
        rgt = rgt + 2
        if lft <> 1 and lft > parent->lft
            lft = lft + 2
        endif
    endif
endfor

add a new node:
    lft = parent->lft + number of children nodes * 2 + 1
    rgt = lft + 1

Here is a function:

Removing nodes

Very similar to adding nodes but you must also take special care of children branches in case you want to remove a parent node. In the pseudo language:

get a node

if node->lft <> 1

    delete the node

    for all nodes
        if rgt > node->rgt
            rgt = rgt - 2
        endif
        if rgt > node->rgt and lft <> 1 and lft > node->lft
            lft = lft - 2
        endif
        if rgt < node->rgt and lft > node->lft
            lft = lft - 1
            rgt = rgt - 1
        endif
    endfor

endif

And here’s how it could look in PHP:

Note that I made sure that lft is not equal to 1 before removing the node. You cannot remove the top node or else the whole tree hierarchy will break up.

Updating nodes

You might have already guessed it – to update a node you can combine addNodeFromRight() and removeNode() functions.

That’s not the most efficient way to do it though. I’m too tired to think about the algorithm now but I’m sure you can figure it out after reading this post.

A small trick

Most of the time you will need a hierarchy with more separate trees (or subhierarchies) which would be much more complicated to achieve. There’s a small trick you can use though. Just don’t display the top node (it could be named ‘Categories’ in this case) and decrease the hierarchy level in the script by 1.