Re: Nested Sets vs. Nested Intervals

Since I like to use an array of folders, I would prefer to use the adjacency list. I just found out that getting an ID out of an array of folders in the URL is extremely efficient with the adjacency list, the same efficency as nested intervals. Also, adjacency list is extremely fast for moving categories. Adjacency list gets the same speed of nested intervals if I use an array of folders in the URL.

If I use an ID in the URL instead of an array of folders, it would turn out very inefficient because it has to use multiple joins to find the path. However, when I use an array of folders in the URL, the path is already in the URL, so I don't have to find the path again. That method is very efficient.

Counting all of the listings recursively in a subcat is anyway very inefficient for all of the methods so I would indeed use an adjacency set.How would I count all of the listings recursively in a subcat efficently? Should I store the number of listings below every cat so I don't have to recursively use the count function? When I was in the 'Arts' category on dmoz.org, and I refreshed that category a couple of times, on every page load, it showed the numbers of listings differently every time in some subcats in the 'Arts' category. Do I have to add a row that stores how many listings are in each category, or are there any other efficient ways to do this? Because when every time I insert a new listing (web page listing, not a node in a tree) in a category, all of the ancestors listings_count row have to be updated. That would be inefficient because the higher the category, the more often listings_count row have to be updated, and it would slow down the directory sufficiently because the hard disk have to rotate to the category_count row frequently so it would slow down other stuff (like selecting categories) considerably. How does dmoz.org do it?

However, the nested interval encoding can fit into the adjacency-list model, so I could done that with nested intervals with the same efficency as adjacency-list. Are there any special advantages for the nested intervals model over the extremely efficent "adjacency-list model with the array of folders in the URL"? If there aren't any special advantages in the nested intervals model, then I would use the adjacency list.

Anyway, I was very "stupid" to not think that getting an ID out of an array of folders in the URL is very inefficient. Received on Wed Nov 16 2005 - 01:50:34 CET