Just to throw it into the mix, I have used a different approach to this ever since I first threw together a tree based CMS in 1997. I don't know that it is a good approach, but it is fast on retrieval and capable of quick and easy cascading deletes (which I make optional on an object-property basis).
As with adjacency model, there is ID and ParentID. There is also a separate displayorder field which allows any integer from 0-99 and the global display order which is a string concatenated set of display orders for all of the antecedents of a record and is often set as an index in the database. Example: ID ParentID Title DisplayOrder GlobalDisplayOrder 1 0 Home 01 01 2 0 About Us 02 02 3 2 History 01 0201 4 2 Founders 02 0202 5 2 Employees 03 0203 6 0 Products 03 03 7 6 Clothing 01 0301 8 6 Shoes 02 0302 9 0 Contact Us 04 04 Retrieval is easy - just order by global display order and filter based on your exact requirements. It is particularly useful for partially expanded trees You are ordering by a varchar, but if it is an index, performance is still good. Adding a new record is easy as you just get the parent ID to look up the parents global display order and then concatenate the new instances display order (adding a trailing 0 if only a single digit). No changes to set numbering are required. Cascading deletes (if required) are fairly easy keying off of parent ID's. For systems with high retrieval and moderate add/delete requirements, I've found this performs very well. Obviously the pain point is changing the display order of high level properties as the changes in their display orders must propegate recursively down the tree, but a simple trigger seems to do the job. Probably not as good as the other ideas, but any thoughts on the approach for the scenario listed above (lots of reads, some add/deletes and few display order edits) would be interesting. Naturally the global display order field is auto generated, so the additional data really isn't an issue as it doesn't need to be maintained. I tend to optimize for performance rather than normalization as disk space is usually less precious than processor cycles and I use automated tools for managing all content so I don't need to worry about developers manually creating code that might forget to update all artifacts - the intelligence is encapsulated in the DAL. Best Wishes, Peter -----Original Message----- From: Barney Boisvert [mailto:[EMAIL PROTECTED] Sent: Wednesday, February 01, 2006 3:18 PM To: CF-Talk Subject: Re: Nested Set Model Adjacency lists employ a parentID, so every node knows who it's parent is, but that's it. Nested sets use a set of numbers (starting at 'left' and ending at 'right', typically) for each node, and the relationships between the sets dictate hierarchy. Adjacency list are simple and fast for tree manipulation, but extracting data can be cumbersome. There also isn't any way to order the children of a given node. Nested sets, on the other hand, are more complex to work with, and slower for tree manipulation. However, they are both very fast and very simple to make complex queries against, once you understand how they work. Nested sets also have implicit ordering of ALL nodes, both hierarchially, and within a given level of the hierarchy. So with a nested set you can swap two children of a node, and the tree structure itself will remember that, without the need for a separate ordering key. For example, with your "ancestors" query, using adjacency list, you have to find the node's parent, if it's not null, find it's parent, etc., repeating until you reach a node that has a null parent (the root). With a nested set, you do this: SELECT id, name FROM myTable WHERE left < ( SELECT left FROM myTable WHERE id = #nodeId# ) AND right > ( SELECT right FROM myTable WHERE id = #nodeId# ) ORDER BY left That'll return a recordset that contains all the ancestors of the given node. Change the < and > to <= and >= and you'll get the node itself, and all it's ancestors. Reverse the < and > and you'll get decendants of the node. Etc. >From what you describe, nested sets is probably better for your scenario. You have a relatively static tree hierarchy (compared to the amount of recall), and the recall you need is very tree-centric. Consequently you'll probably find things easier with nested sets than with an adjacency list, and you might get a performance boost out of it as well. cheers, barneyb On 2/1/06, Mike Little <[EMAIL PROTECTED]> wrote: > >I'm not sure what you wish to do with this level count, but be > >careful if you plan on storing it in the original table. The level > >count is already stored inherently in the table through its structure > > brad, are you saying that i could do without the level column and rely > instead on the query to determine which level each category is on? the > reason i wanted this column was so that i could create breadcrumbs > with a simple query. > > also, from the other posts (thanks heaps by the way) is it not > necessary to utilise a parent_id column using nested sets? > > my client wishes to be able to move categories to any other category > and also reorder a category within a particular level, so you can > imagine i am all twisted about on this at the moment. > > mike -- Barney Boisvert [EMAIL PROTECTED] 360.319.6145 http://www.barneyb.com/ Got Gmail? I have 100 invites. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| Message: http://www.houseoffusion.com/lists.cfm/link=i:4:231026 Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4 Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4 Unsubscribe: http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=89.70.4 Donations & Support: http://www.houseoffusion.com/tiny.cfm/54
