Storing Hierarchical Data in a Database

PHP
1

This is an article discussion thread for discussing the SitePoint article, “Storing Hierarchical Data in a Database”

2

how can i find the level?

3

Thanks for writing a great article and nice explaining the complex topic.

The Modified Preorder traversal method works if there is a one to one parent child relationship. If a node could be a child to other parents then this does not work, because then depending on which parent the child belongs to, the left and right values will vary. Please let me know if that’s not the case.
Thanks
Rajesh Garg
rajesh.garg@comac.com

4

Great explanation of a potentially complex topic. Great job!

5

Great work. Saved me a lot of stress.

6

how effective is it if i delete or add a new node and there are 1000 of records, wont he reupdate of the left and right numbers be slow??

7

Excellent Explaination! However the update query should be: UPDATE tree SET rgt=rgt+2 WHERE rgt>=5;
UPDATE tree SET lft=lft+2 WHERE lft>5;

When I first read this article, I didn’t understand how the 5 in the previous query was determined. Was it calculated from the right value of the parent node (minus one)?

8

Great article! But how would you find the direct children of a node (by means of only the left and right key)? E.g the direct children of fruit are red and yellow…Thnx!

9

Great article, and that numbering system is a great solution, but i DO use your first (simple) system. The difference is that I cache the html which is created. So all those querys have to run only when editting/adding/deleting items from the data :slight_smile:

10

The article is well written. Thanks Gijs.

The only thing I miss is, that it speaks only about inserting a leaf node (i.e. a node without children). What if I want to insert a new node “color” as a child of “Fruit” and I want “Red” and “Yellow” be children of “Color”?

My proposal:
UPDATE tree SET lft=lft+1 WHERE lft BETWEEN 3 AND 10
UPDATE tree SET rgt=rgt+1 WHERE rgt BETWEEN 3 AND 10
and the rest as proposed in the article:
UPDATE tree SET rgt=rgt+2 WHERE rgt>10
UPDATE tree SET lft=lft+2 WHERE lft>10

3 is the lft-value of the first direct child of the new node (“Red”), 10 is the rgt-value of the last direct child of the new node (“Yellow”).

11

To LoreZyra:

I don’t see why the update should be >=5 instead of >5. I think the statement in the article is correct.

If you use the rgt-value of the parent-node minus 1, it works only if you insert a new leaf to the right of all other leafs (as in the article). But not, if you want to add “Blue” between “Red” and “Yellow”.

If 5 is the lft-value of the new node you insert minus 1, then it works allways (no mather where you insert the new leaf).

12

Hi, Í’m using the first version at this moment as I have a many-to-many relation in my DB. So my question might be a bit stupid, but can anyone explain to me how I can have the first level horizontal, and the second layer under that one (also horizontal), etc etc?
Also how to make a visual indicator (link color change) which item is active?

13

Do you mean horizontal in the sense of presentation? If so, the DB query probably wouldn’t change, it would be done with HTML/CSS.

14

Yes, presentation wise. Problem is, the main “browser” I’m creating this for does not (yet) understand CSS, and at most basic html tags, although no table tags yet.
I “need” something like:

parent1 | parent2 | parent3
child 1 | child 2 | child 3 | child 4
subchild 1 | subchild 2

I’ve been playing around with creative < b r / > placements, but no luck yet. Only option I see is to make a duplicate function which is triggered by a var passed onto it to activate sublevel. Of course this should be able to be done without creating extra functions I’d say. Any suggestions?

15

Hi –
Does anybody know the proper mean to “MOVE” a node using the modified preorder tree traversal? I would like to move an node and all of its children to a new parent node.
Thanks

16

Yo

You might find this thread interesting then :wink:

17

Hi,
how do you select just the first child level with this method? I now solved it in PHP. But i’d rather not select them at all ( performance wise )

18

Friend of mine asked similar question, here’s what I came up with:


SELECT 
    CONCAT( REPEAT('   - ', COUNT(*) ), 
                      t1.Name, 
                      '  (', 
                      t1.l, 
                      '|', 
                      t1.r, 
                      ')' ) AS v 
    FROM t AS t1, 
        t AS 2, 
        t AS t3 
    WHERE t1.l BETWEEN t2.l AND t2.r 
    AND   t2.l BETWEEN t3.l AND t3.r 
    AND   t3.l=2   /*  <=== node to start with   */
    GROUP BY t1.l 
    HAVING count(*) = 2 /* <=== show only direct descendats */

with just three joins one can get any slice of the entire tree (or particular branch). Count(*) equals to node level relative to the level of ‘t3.l’.

19

Wow. This is great. Just what I was looking for. I also like the thread Big Fat Bob posted - thanks!

One question…

Any way I can sort the results alphabetically? It looks like, from the functions in this article and others I have seen, you have to ORDER BY the lft ID. Does the data have to be inserted/updated into the database and placed in the appropriate spot alphabetically for this to work? This will be cumbersome with the amount of inserts/updates.

What I am building is a large document management system that basically will display a “Windows Explorer” type of folder tree. But the tree needs to be alphabatized as well as follow the lft ID so the data stays as a “tree”.

Thanks for any tips!

20

Take a look at the post from Widow Maker at the link Big Fat Bob posted (http://www.sitepoint.com/forums/showthread.php?t=186601).

Toward the middle of the post is a great Tree class and includes a function for what you are trying to do.