Download This Article

Download this article or the entire “Implementing An N-Level Nested Tree In PHP And PostgreSQL” series with all listings and files.

Implementing An N-Level Nested Tree In PHP And PostgreSQL, Part 1

By Quentin Zervaas, 4 March 2005, MySQL, PHP, PostgreSQL

Using The Nested Tree Data

There’s a number of things the above data allows us to do.

Selecting the entire tree in order of hierarchy

Listing 4 listing-4.sql

select * from nested_tree order by nleft

Select a portion of the tree

If we wanted to select everything in the tree within the Links section, we do the following (let’s assume we know Links has an ID of 8)

Listing 5 listing-5.sql

select nleft, nright from nested_tree where id = 8;
    /* assume now that nleft and nright values are stored in $nleft and $nright) */
 
select * from nested_tree where nleft > $nleft and nright < $nright;

The above query will not include the Links node. To include it, change the query to:

Listing 6 listing-6.sql

select * from nested_tree where nleft >= $nleft and nright <= $nright;

Or you could do all of this in a single query (but you’re performing the same lookup twice so maybe not the most efficient way to do it:

Listing 7 listing-7.sql

select * from nested_tree
    where nleft > (select nleft from nested_tree where id = 8)
    and nright < (select nright from nested_tree where id = 8)
    order by nleft;

Select all children of a node

We already did this earlier on, using the parent ID. We can also do this using the nlevel value (although the parent ID is probably the easier way)

Listing 8 listing-8.sql

select nleft, nright, nlevel from nested_tree where id = 8;
    /* assume now that nleft, nright, nlevel values are stored in $nleft, $nright and $nlevel) */
 
select * from nested_tree where nleft > $nleft and nright < $nright and nlevel = $nevel + 1;

Find all leaf nodes

This finds all the nodes that have no nodes beneath them:

Listing 9 listing-9.sql

select * from nested_tree where nright = nleft + 1;

Find a node’s bloodline.

This one is the kicker – you can easily find the full path to a node really easily with this method.

Let’s find the path to the Portals node. Let’s say we already know its ID is 11.

Listing 10 listing-10.sql

select nleft, nright from nested_tree where id = 11;
    /* assume now that nleft and nright values are stored in $nleft and $nright) */
 
select * from nested_tree where nleft <= $nleft and nright >= $nright order by nlevel;

You could also order by nleft – it’ll give you the same results. The results will look something like:

Listing 11 listing-11.txt

Title                        ID     PARENT ID     NLEFT     NRIGHT     NLEVEL
------------------------------------------------------------------------------
General Resources             1          0           1        22          1
   Links                      8          1          14        21          2
      Portals                11          8          19        20          3

The titles won’t be indented – it’s just used for demonstration.

Here’s the bloodline of this article. At time of writing, its nleft was 6 and nright 7.

Listing 12 Bloodline output from the psql command line program (listing-12.txt)

phpriot=> select title, nleft, nright, nlevel from documents where nleft <= 6 and nright >= 7 order by nlevel;

                               title                               | nleft | nright | nlevel 
-------------------------------------------------------------------+-------+--------+--------
 Development Articles                                              |     3 |    396 |      1
 PHP                                                               |     4 |      9 |      2
 Application Design                                                |     5 |      8 |      3
 Implementing an N-Level Nested Tree In PHP and PostgreSQL, Part 1 |     6 |      7 |      4
(4 rows)

Next: Summary

Professional Linux Programming