# Thread: Storing Hierarchical Data in a Database

1. Ok, Thanks samsm!! I found other complicated math formula but you describe a simple perfect way.

Only i found one mistake with parents.
In some cases, i have to change lft (or rgt) values (with your rules) of parent's nodes because:

1.sometimes the subtree moved is on other "branch" like destiny node...(so you subtract this nodes of this branch)

2.and others, both of them (original node and destiny node) are on the same branch.(so you subtract nodes of this branch but add the same nodes to the same branch)

if you move Red L3R6 to Beef L13R14, Fruit changes to L2R7.

But if you move "Red" L3R6 to Banana L8R9, Fruit will have L2R11 (without changes)

I hope that i has explained.

2. po

3. Ok, parents problems are solved:

1.Take the parent of original node(subtree to be moved).
2.Generate full path of destiny node(node to put subtree moved)
3.Check if parent of original is on full path of destiny node.

If it isn't, you can be sure that both aren't family so parent of original node will have changes.
In others, the parent haven't got changes.

Ex1: Move Red ==>Banana
1.Parent of RED: Fruit
2.Full path of Banana: Food/Fruit/Yellow/Banana
3. Fruit is contained on Food/Fruit/Yellow/Banana
So Fruit haven't any changes

Ex2: Move Red ==> Beef
1.Parent of Red: Fruit
2.Full path of Beef: Food/Meat/Beef/
3.Fruit isn't contained on Food/Meat/Beef/
So Fruit will have changes

4. To be honest, I'm a little confused as to how my post 50 suggestions wouldn't work for a move to the right on a tree. I'm trying it out in my head and it's working for each of your examples.

5. Ok but i try "on paper" all cases and works fine. Also i try to implements function and post here. Now i have functions but i have to add my last conclusion referer to parents problems.

When i finish, post here the functions and i hope, it will be easier to understand.

6. This is a comment that I am placing on this article. Right? We should be placing comments more often than we have been doing earlier. Yeah! Comments are good for articles, especially when they are free and you want more of them.

But here's a catch. Comments for free articles are posted for free. In this quest to share knowledge only the middlemen earn. Yes. No money for the author, nothing for the reader. Just for sites like these! They earn a lot of dollars by selling ads and selling "free" content. Its the time to revolutionize the entire planet.

Just Kidding.

7. It's a give and take. This forum and the Sitepoint content is provided for the price of us viewing the ads. If you think that service is worth the price you can use it. If you don't, you can refrain.

Authors know what they are getting into when they submit content and we as forum participants know what we are getting into when we interact.

Anyway, although this comment is kind of an interesting commentary on content sites and forums in general, this particular comment does not relate to storing hierarchical data in a database so I suggest that it not be discussed any further. :-)

8. The article is fine up until the point where the author touches the more advanced topics of addition and deletion of data (does he talk about deletion at all?).

I have a feeling that the author does not fully understand how the traversal tree approach works and hence he made a terrible mistake when writing the ADD function (it is bogus, try it, and you'll see that you are not adding a leaf node, but a brother/sister node). Moreover the author did not even touch the more delicate part of the theory - deletion of data. There is even more - moving parts of trees from one node to another.

I am terribly dissapointed. Sorry.

9. The article is fine up until the point where the author touches the more advanced topics of addition and deletion of data (does he talk about deletion at all?).

I have a feeling that the author does not fully understand how the traversal tree approach works and hence he made a terrible mistake when writing the ADD function (it is bogus, try it, and you'll see that you are not adding a leaf node, but a brother/sister node). Moreover the author did not even touch the more delicate part of the theory - deletion of data. There is even more - moving parts of trees from one node to another.

I am terribly dissapointed. Sorry.

10. Originally Posted by Dolce0109
...and hence he made a terrible mistake when writing the ADD function...
I don't see an add function. I see a function for converting an adjacency list and a function for displaying a nested tree.

His mention of adding nodes is limited to this, as far as I see:
We’ll use the query:

UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;

Now we can add a new node ‘Strawberry’ to fill the new space. This node has left 6 and right 7.

INSERT INTO tree SET lft=6, rgt=7, title='Strawberry';
Is something incorrect about that? If so, how should it be changed?

You are correct that the author brushes over addition and doesn't really mention deletion. Frankly, I was surprised to see this topic as PART of an article... this topic is really big enough for say, a chapter in SQL For Smarties (chapter 29 to be exact). :-)

11. What he lists is enough to make an add function (he implies that it has to work like this. But frankly it is bogus and needs a very small correction to work fine

Originally Posted by samsm
You are correct that the author brushes over addition and doesn't really mention deletion. Frankly, I was surprised to see this topic as PART of an article... this topic is really big enough for say, a chapter in SQL For Smarties (chapter 29 to be exact). :-)
What is the point of this article if the author does not talk about the important stuff? Here is where he slightly touched upon deletion of data:

The second way to add, and delete nodes is to update the left and right values of all nodes to the right of the new node.
Deletion ain't that hard after all and could be described in two paragraphs. Addition he alsmost got correct and fine. Now the biggest trick comes in when trying to move data. Took me a good hour to figure out how to move trees from one node to another without recursing through the tree.

I mean, gosh, the article is brilliant to the point where the tricky stuff begins. It's like showing someone a palace but not actually letting anyone in to see the interiors.

btw. I've written an object that does all the tree stuff for me and it is a combination of both approaches.

The traversal model has a limitaion - one cannot get, for example, the first level of all the children of a node, which is essential for building foldout lists or drop-down menues or whatever. Hence storing a reference to the parent node sometimes helps

12. Originally Posted by Dolce0109
Deletion ain't that hard after all and could be described in two paragraphs. Addition he alsmost got correct and fine. Now the biggest trick comes in when trying to move data. Took me a good hour to figure out how to move trees from one node to another without recursing through the tree.
I'm currently working on the function for moving data. I've been able to make place for the data I'm moving, but I'm having trouble assigning the new left and right values of the data I'm moving.

Don't know if I just need a little break so I can think clearly again or something.. do you want to share some of the code you're using for moving?

Btw, I've tried the way of adding he mentioned in the article, and I can't really see why you think it's bogus. Could you explain further why it's wrong, and tell us of a better way of doing it?

13. Originally Posted by HLindset
Don't know if I just need a little break so I can think clearly again or something.. do you want to share some of the code you're using for moving?
Yeah, this tree stuff can drive your brain mad I really know this feeling, since I've had to figure out quite a bit of this by myself, and oh gosh, I am too lazy to explain all this stuff, but I will sometime write a full article... in a month or two, when my PhD will not be pressing

About the code: Yeah, no prob, but unfortunately I am on vacation right now in deep forests of Russia, and hey, GPRS works here quite well, but my PDA ain't my laptop, hence I can only give you a link to my Tree Navigating Object for PHP&MySQL. This object is quite well documented, I suppose, BUT it is an older version, I have developed and optimized it even further and even found a small bug. In case you are interested, I will be able to upload the newer code in ten days or so.

Originally Posted by HLindset
Btw, I've tried the way of adding he mentioned in the article, and I can't really see why you think it's bogus. Could you explain further why it's wrong, and tell us of a better way of doing it?
You see, if you do EXACTLY what is done in the artice, then not a new child is added to the tree, but a leaf on the same level as the parent node ONLY in the case when there are other leaves on that level. Quite difficult to explain in words, quite easy to show on screen. Try constructing a complex tree, output it to the browser and test adding nodes to different parents.

14. Thanks, Docle0109... I'll check out your code (oh, yeah, and just post in this thread when you're able to upload the new code).. What exactly is the bug related to?

I'll do some more testing with the add function

Again, thanks for the reply (and the code)

15. Are you back from your vacation yet, Dolce0109? Just wondering if you have had the time yet to update the tree navigating object?

Thanks

16. ## Hope some-one will help ??

I've been away from my computer for a few months (just as I was coming to terms with php).

I have found this article very interesting and would like to build a working example of it as an exercise using my brothers real estate business.

Please prepare yourselves for some lame questions.

17. Great article, very well explained.

I just wanted to give some feedback on the example code. The function display_tree will get stuck in a loop as you need to exit the while loop when the stack is empty.

The while loop should look like this:

while ( count(\$right)>0 && \$right[count(\$right)-1]<\$row['rgt'])

18. Is there some way to add to this function so that it selects the best graphic for the job, eg:
:
:....
or if there are 2 children to original parent:
:
:
:......
:
:
:......
or for 3 or more:
:
:
:....
:
:
:....
:
:
PHP Code:
``` function display_children(\$parent, \$level) {// retrieve all children of \$parent\$result = mysql_query("SELECT title FROM tree WHERE parent='".\$parent."'" );// display each childwhile (\$row = mysql_fetch_array(\$result)) {// indent and display the title of this childecho str_repeat('& n b s p ; & n b s p ; & n b s p ; ',\$level).\$row['title']."\n<br>";// call this function again to display this// child's childrendisplay_children(\$row['title'], \$level+1);}}display_children('',0);  ```
I just want simple graphics, but I'm a bit confused as to how to display the correct one.

Any help appreciated.

19. how can i have a dir reader (virtual) with the tree explaned in this artikel

so if i'am browsing in apple i want to see
/fruit/red/apple

20. Originally Posted by Nova
how can i have a dir reader (virtual) with the tree explaned in this artikel

so if i'am browsing in apple i want to see
/fruit/red/apple

I found out how to do it love the rgt lft thing ^^

this query i was using to get the result
(i had a different db structure but i try to do it with the example used by the articel and it's untested but you'll get the idea how to do it)

SELECT M.parent, M.title
FROM tree as M, tree as M2
WHERE M2.parent = \$parent
&& M2.lft BETWEEN M.lft && M.rgt

this should do the job

21. "I don’t recommend that you use the title of a node to refer to that node. You really should follow the basic rules of database normalization."

What basic rule of db normalization is that?! None of the NF's force you to use numerical id's.

22. I can't Quite Figure out that query, i am a noobie. I want a path that shows Fruit > Red > Apple. I odn't know how to format it out of the array that is used in the first page. I am Using a modified preorder tree traversal. Thanks

23. i dont think the slowdown from the lft rgt is worth the gain in tree retrieval

24. This method is a ton faster when you have lots of queries for the tree itself, like tree parts or the whole one. If you have little to no updates to the tree structure, go for this. If you constantly have to change your structure (example forum threads) you might wanna give another struvture your attention. I tried both, and the speed in this one is amazing. Using a small caching of these data makes it additonally faster, because in case you have to refersh the cache, it will be much faster then with the old adjacency list method.

Then some questions. If I would like to view the tree so that only "active" tree is visible, all others are hidden, how I should do that?

Example:

root-group
-first-level-group
-first-level-group2
-first-level-group3
-second-level-group1
-second-level-group2
-third-level-group1
-fourth-level-group1
-third-level-group2
-third-level-group3
-second-level-group3
-first-level-group4
-first-level-group5

That function in the article prints out all groups in tree, I need to show only active tree. I'm doing some kind of webstore and there is no need to show all groups at same time. When user clicks one group, show its childgroups and when user clicks one childgroup, show its childgroups...

Ask if I you think you can help, but didn't get the idea.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•