Re: recursing down a tree

On 12 Jul 2002, --CELKO-- wrote:

> >> 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.

Cool. btw, we have developed contrib/tree module which is very fast
for r/o operations. It's available on our GiST development page
http://www.sai.msu.su/~megera/postgres/gist/tree/README.tree.english
The idea is simple - to code path information to the node name,
so tuple itself does know it's place in hierarchy. It's sort of
cheating of relational data model. Also, we're developing another
module - contrib/ltree which will be much more powerful (we use
real names in path instead of digits as in contrib/tree).

>
> 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.
>
> ---------------------------(end of broadcast)---------------------------
> TIP 3: if posting/reading through Usenet, please send an appropriate
> subscribe-nomail command to majordomo(at)postgresql(dot)org so that your
> message can get through to the mailing list cleanly
>

Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg(at)sai(dot)msu(dot)su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83