Re: Making a tree with "millions and millions" of dynamic nodes

The one performance concern I would have here (and I think it's there for
any of these except the simple adjacency list) is when I want to move a node
high up in the tree how long is it going to take?

That is the only change that I really need to make that will be initiated by
a user, thus I would like response times to be fast.  My tree is not that
big, it's only got about 40,000 rows.  But if I move a node near the top of
the tree and all of a sudden I've got to delete 20,000 rows and insert
20,000 rows.  That's not going to be that fast it seems and the user is
going to be sitting around waiting for it to finish.

At the same time any system that gives you a fast getAllDescendants and
getAllAncestors is going to require a large amount of updates in this
situation.  I don't think it's even possible to get around it.  I have
another idea that I this will give me the same quick performance on
getAllDescendants and getAllAncestors but will require exactly one row to be
updated per descendant node on a move.  This method will have several
(inserts and updates) per descendant node.

I guess I will just have to try the two and see which one is faster.

rg

----- Original Message -----
From: "Christian Fowler" <google@NOSPAM.gravesweeper.com>
To: <pgsql-general@postgresql.org>
Sent: Monday, December 08, 2003 11:28 PM
Subject: Re: [GENERAL] Making a tree with "millions and millions" of dynamic
nodes


> Here is another approach (only first half of the page applies here)
> I was emailed personally in response to my orginal post:
>
> http://fungus.teststation.com/~jon/treehandling/TreeHandling.htm
>
> Basically, the (too obivious for me to think of ;-) concept appears to
> be storing a mapping of the Node / Parent for every parent in the
> chain. Basically it splits up the materialized view concept into
> multiple rows, or one can think of it as the adjancency list with all
> parents stored. Perhaps call this the "Materialized List".
>
> Personally, this is my likely favorite since I tend to "trust" the
> performance of giant tables that are nothing more than 2 columns of
> integers. Seems like this approach would handle most of the desired
> tree cases (select path & child count, insert, delete, move) very
> well.
>
> Hopefully postgres can handle a very active, very narrow 50 million
> row table without breaking a sweat.