Re: recursing down a tree

>> I did a little research on the subject and it seemed quite
interesting. However, it seemed that insertion would require updating
most of the tree for
a minor insert. Can you send along a few more details about your setup
and algorithms? I would like to find more information about this. <<

I am writing a separate book on "Trees in SQL" which will cover
several different models; I hope to be done by the end of the year. I
also hope to win the lottery.

Updating is not the problem people think it is.  The nodes are in one
table and the structure is in another.  The Tree table has (node_id,
lft, rgt) in its rows and those the rows are very short; a lot of them
fit into main storage at once.  Since the newest addition (i.e.
youngest sibling) is made on the right side of the immediate
subordinates (siblings are ordered in the Nested Set model), you do
not have to update half the nodes on average.  Finally, in the real
world, the tree structure tends to stay the same and the nodes change
-- even dot-com firms don't re-organize faster than their personnel
turnover <g>.

However, someone did have a situation where they used the nested set
model for the message threads in a newsgroup front end.  Their answer
to this "fixed nodes and changing structure" problem was to use large
gaps in the numbering of (lft, rgt) pairs instead of incrementing
(lft, rgt) by one.

Think about it; subordination is shown with the BETWEEN predicate; any
sequence of unique, nested numbers will work.  Subtree size is shown
by the formula ((rgt-lft+1)/2) which does depend on an increment and
happens to also give you subordination.