The nested set model

Hierarchy management

The simplest way is to add a new column parent_fk that points to the primary id of another row. That works great and this is used here. Look at the content_hierarchy table.

 CREATE TABLE {prefix}content_hierarchy
 (
   parent_content_fk       int(6),
   content_fk              int(6),
   left_n                  int(6),
   right_n                 int(6)
 );
 

OK, that does the trick, and I can easily know if a row is the parent of another one, or if a row is the child of another one.

Right, it works, but it works only for one level

What if I want to know this information for several levels ?

For example, how can I have all children of a particular row ?

Or, how can I have all parents of a particular row ?

Of course, you can do it, but you will need to do several queries. The number of queries will be proportional to the number of level and can easily grow exponentially.

The nested model

As you can see in the table content_hierarchy, not only do we have parent_content_fk, but we also have left_n and right_n.

left_n and right_n are transient values. I mean this information can be computed entirely from the hierarchy information (parent_content_fk), so if the values get wrong, this is not serious.

By the way, the menu "Db maintenance/Check and repair db" in admin panel does exactly that : it recompute the nested set model in case there was a bug.

The nested set model works this way : for a top level row that have a left (TL) and right (TR) values, all rows that have left and right values included between TL and TR are children of the top row (be it direct or indirect).

That means, children have values that are nested inside their parents values

And you're free to choose the algorithm you want to compute the values, provided you respect that rule.

In wiclear, I use the following algorithm :

First step

Let's called Hierarchy a map with P a row as the key and ChildList the list of children of P as the values.

1. Get an element R from RowToCompute and remove that element
2. Get all nodes that are direct children of R : ChildList
3. Put all element of ChildList in RowToCompute
4. Put the relationship Hierarchy[R] <- ChildList
5. if RowToCompute is empty, stop, otherwise loop

Second step

Initialise Current to the top level row

Call a recursive function recComputeNestedSet(current, c)

recComputeNestedSet(Current, c)

1. Current.left <- c
2. ChildList = Hierarchy[Current]
3. foreach Child in ChildList
   • c <- recComputeNestedSet(Child, c + 1)
4. c <- c + 1
5. Current.right <- c
6. return c

Generated on Mon Feb 19 19:11:58 2007 for Wiclear by  1.4.7