Re: Making a tree with "millions and millions" of dynamic - Mailing list pgsql-general

I was glad to see this topic come up on the list as I was about to start
asking about some of these issues myself.  I would like to discuss each of
the methods I have researched so far for doing trees in sql and see if
anyone has some experience or insite into the topic that could help me.

That being said the four methods that seem to be the prevailing ideas are
the following:

1) Adjacency List - Just use a parent field, nothing interesting or
non-obvious here.
2) Materialized Path - Basically you store the path up to the node in a
field called path
3) Nested Sets - uh, read the articles below.
4) Nested Intervals - definitely read the first article

Here are some articles explaining these concepts:

http://www.dbazine.com/tropashko4.html (this is from an earlier posting in
this thread)
http://www.intelligententerprise.com/001020/celko.shtml (the nested set or
Celko method as it seems it should be called)
http://www.dbmsmag.com/9603d06.html (more on the celko method)
http://www.dbmsmag.com/9604d06.html
http://www.dbmsmag.com/9605d06.html
http://www.dbmsmag.com/9606d06.html


I have a lot of thouhts on this but here is my first question:

In the first article at the end of the section on materialized paths and the
beginning of the nested set section Tropashko basically says that neither
one really does a good job at answering "who are all of my ancestors" but
that the materialized path method has a nice kludge that you can do with
some funky string manipulation.

Is this true?  Celko in his articles seems to make it sound like this query
will be very fast.  But Tropashko it seems is saying that it will be slow.
Am I reading this right?  If so is Tropashko right?  Any ideas on this?  Any
articles / papers that might shed some light on this specific question or
the topic in general?

thanks in advance

rg