Nested sets tends to be one of the better ways to handle hierarchical information in a relational engine, but still generally sucks in comparison to a hierarchical engine. The hash string method that I briefly describe below tends to be easier to understand than nested sets and has the added benefit of being more scalable. In fact, we used a similar method when I was at DevX to handle our multi-dimensional taxonomy that handled hundreds of thousands nodes.
I highly recommend people look into a hierarchical engine for handle hierarchical information. Matt Liotta President & CEO Montara Software, Inc. http://www.montarasoftware.com/ 888-408-0900 x901 > -----Original Message----- > From: Jeffry Houser [mailto:[EMAIL PROTECTED]] > Sent: Monday, December 09, 2002 7:59 PM > To: CF-Talk > Subject: RE: Lists vs. Arrays vs. Structures > > As an aside to this conversation.. > > Ya'll may want to take a look at this thread > <http://www.sitepointforums.com/showthread.php?s=&threadid=84833>. > I have not been following it religiously, but it does talk about > building > a discussion room / forum. It touch base on self-referencing tables ( as > described below ) and a different method called nested sets, which they go > into in the thread (with links to resources). > > > At 03:30 PM 12/9/2002 -0500, you wrote: > >If I understand you correctly, you are representing a hierarchical > >relationship in a tabular manner. If there is another way you can store > >this information I would suggest it highly as there are many data > >structures much better suited for storage of hierarchical information. > >For example, a tree would give you O(log N) vs. your current O(N) > >performance. As you can see, if N is large it makes a big difference. > > > >Now then, assuming you are stuck on your tabular data structure I would > >suggest some changes to it. Right now you have the following. > > > >itemid parentid name > >1 0 root > >2 1 1st child of root > >3 2 1st sub child > >4 2 2nd sub child > >5 1 2nd child of root > >6 5 1st child of 2nd > > > >Instead of relating a child to its parent via a primary key, I would > >suggest creating a hash string to represent the relationship, which > >might look like the following. > > > >itemId hash name > >1 001 root > >2 001002 1st child of root > >3 001002003 1st sub child > >4 001002004 2nd sub child > >5 001005 2nd child of root > >6 001005006 1st child of 2nd > > > >Above I have used a simple hash formula, which represents the itemId > >using a 3 digit fixed notation. I then create a hash string for each > >item by appending the item's hash to that of its parent's. This allows > >you to just sort the whole table based on a single column and everything > >is done for you. > > > >The above has formula is only an example and is limited to 999 unique > >items. You would need to create a hash formula best suited for the > >number of unique items you need to support. However, resist the > >temptation to make individual item's hash too long as deeply nest items > >would have very long strings. > > > >Matt Liotta > >President & CEO > >Montara Software, Inc. > >http://www.montarasoftware.com/ > >888-408-0900 x901 > > > > > -----Original Message----- > > > From: Michael Dinowitz [mailto:[EMAIL PROTECTED]] > > > Sent: Monday, December 09, 2002 3:08 PM > > > To: CF-Talk > > > Subject: Re: Lists vs. Arrays vs. Structures > > > > > > You can see the code here: > > > http://www.houseoffusion.com/_library/maketree.txt > > > Your example will fail as there can be more than one item with the > >same > > > 'parent', which is what we're looking for. No matter what, we have to > >do a > > > search and the list search functions seem to be the fastest of the > > > searches > > > around, even though the list items have to be parsed. > > > > > > For those wondering what's going on, when dealing with a query that > >has to > > > be > > > turned into a tree, you have to first find the 'root' item, then all > >of > > > its > > > children, then the next root item, etc. > > > > > > itemid parentid name > > > 1 0 root > > > 2 1 1st child of root > > > 3 2 1st sub child > > > 4 2 2nd sub child > > > 5 1 2nd child of root > > > 6 5 1st child of 2nd > > > We would have to first look at root and get its children. Item 2 is > >its > > > first > > > child. Does item 2 have any children? If so, we get those children on > > > down. When > > > item 2 or it's children are finished, we go onto the next chold of the > > > root. > > > That is item 5. We do the same thing for 5, getting all of its > >children. > > > > > > > Michael Dinowitz wrote: > > > > > I think that a new array search function might be in order here. > > > Something > > > to > > > > > look through an array for a value and return its index. > > > > > > > > > >>I'm not sure what you are really trying to accomplish here. > > > > > > > > I agree with matt, are you working on the maketree tag in cf? lets > >talk > > > > examples... > > > > > > > > do you modify the array, ( ie inserting or deleting array members > >other > > > > than from the end?) if not then u could index the array using > >structures > > > > > > > > <cfscript> > > > > item_array=ArrayNew(1); > > > > item_struct=StructNew(); > > > > </cfscript> > > > > > > > > <cfloop query="qry_items"> > > > > <cfscript> > > > > x=arraylen(item_array); > > > > item_array[x]=qry_item.item; > > > > item_struct[qry_item.item]=x; > > > > </cfscript> > > > > </cfloop> > > > > > > > > find where dog is in the array = item_struct["dog"] or > >item_struct.dog > > > > > > > > this method is so fast scaling the dataset makes almost no > >difference in > > > > speed > > > > > > > > now you can always find the position of x in the array using the > >struct, > > > > this of course doesn't handle very well adding elements to the aray > > > > > > > > ideally I would try to eliminate arrays all together... esp when u > > > > consider that have 2 values in a struct, the key and the value > > > > > > > > z > > > > > > > > > > > > > > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| Archives: http://www.houseoffusion.com/cf_lists/index.cfm?forumid=4 Subscription: http://www.houseoffusion.com/cf_lists/index.cfm?method=subscribe&forumid=4 FAQ: http://www.thenetprofits.co.uk/coldfusion/faq This list and all House of Fusion resources hosted by CFHosting.com. The place for dependable ColdFusion Hosting.
