Re: recursing down a tree

Jeff, some detailed information about nested set model by Celco is in
http://www.mip.berkeley.edu/mip/related/thesaurus/thesaurus.pdf

Generally, if you want to support fast online update of tree stucture,
you have to maintain link information separately - parent, child, level
but this is very slow for select. If you code link information into
something, you will have a very fast select but slow insert.
I didn't found good compomise :( It's a nature of relational database,
when tuple know nothing except itself. We develope our module
tree ( www.sai.msu.su/~megera/postgres/gist) to support tree data type
using path information, so tuple does know hierarchical information
and we was able to provide index support. Unfortunately, it's very fast
for select. I think solution could be separating working with tree
structure (editing) and the exporting into our data type for
public usage.

Oleg
On Thu, 4 Jul 2002, Jeff Davis 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.
>
> Regards,
> Jeff
>
> On Tuesday 02 July 2002 06:07 am, Fran Fabrizio wrote:
> > Carl Meyer wrote:
> > >hi,
> > >
> > >say i have a table with something like
> > >
> > >id,parent,description
> >
> > Depending on what your most common types of queries are, you might be
> > better off with Joe Celko's nested set model (from the book SQL for
> > Smarties). It would do:
> >
> > id, left, right, description
> >
> > where you traverse the tree depth-first and as you pass the left side of
> > each node you increment a counter (left) and as you pass by it again on
> > the right you increment it again (right).
> >
> > This model provides much easier ways of making queries such as "give me
> > all descendants of id=2" because there's then no recursion (WHERE
> > child.left between parent.left and parent.right).
> >
> > I had a table set up exactly as you have described, and when the
> > recursion proved too costly in terms of db performance, I went to nested
> > set and we're pleased with the results.
> >
> > Just another option,
> > Fran
> >
> >
> >
> >
> > ---------------------------(end of broadcast)---------------------------
> > TIP 4: Don't 'kill -9' the postmaster
>
>
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 1: subscribe and unsubscribe commands go to majordomo(at)postgresql(dot)org
>
>

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