Re: How to store a tree structure in a relational db?

Post #158,377 by johnu 6/4/04 8:16:45 AM Reply	Re: How to store a tree structure in a relational db? [link\|http://www.intelligententerprise.com/001020/celko.jhtml?_requestid=52999\|Trees in SQL ]
Post #158,380 by admin 6/4/04 8:54:08 AM Reply	AKA Nested Set Trees. :-) Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."
Post #158,537 by bluke 6/5/04 2:29:53 PM Reply	After reading about nested sets ... It sounds like that they are very expensive for inserts in that you have to shift all the left and rights after the node that you inserted and therefore if you have a tree where there are a lot of updates this becomes a problem. Since in my case teh data is fairly dynamic and is updated often it doesn't sound like nested sets fit the bill. Our tree is fairly shallow so encoding the hierarchy in the nodes may be the best solution.
Post #158,551 by admin 6/5/04 4:48:38 PM Reply	Updates aren't an issue. Only inserts and deletes. If the tree itself stays fairly stable and only the data is changed, then you won't have an issue. And an update of a tree is only expensive if 1) the tree is very large and 2) there is lock contention from more than one insert at a time. We have very large trees here (each thread is a full nested set hierarchy) without inserts being an issue. It's probably worth testing. Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."
Post #158,603 by ChrisR 6/5/04 11:27:30 PM Reply	If I had to do it over.... ...I think I might've put the nested set data in a seperate table. This would help on the inserts/deletes by minimizing the amount of data to traverse. One other side note: In my nested sets, I have different customers with unrelated trees. The nested set is keyed of the customer id first, meaning that the insert/delete operations for one customer do not have to effect all the data in the table. In effect, I have multiple roots in the table. Each root acts independently. Not sure if it is similar, but I was thinking that in something like zIWTHEY, you could have each top level message be a seperate tree.
Post #158,628 by admin 6/6/04 7:19:32 AM Reply	That's exactly how I do it. Each thread (top level message) is its own tree. This version separates the tree data from the content data, but it's a pain in the ass to deal with. The new one keeps them in the same table. Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."
Post #158,646 by ChrisR 6/6/04 2:12:53 PM Reply	Guess I'll have to try it for myself I figure a view would be in order for the times I need to merge the tree data with the data itself. The problem in my case is that I have to keep historical data on the values (similar to you keeping the edit history on the messages), but the tree data only needs to be current (or if it needs to be kept, it needs to have it's own archive seperate from the rest).
Post #158,625 by bluke 6/6/04 5:24:23 AM Reply	We have a lot of inserts Thanks for all the info

Welcome to IWETHEY!