Re: Optimizing the implementation of an optimized tree

Why not try Oleg and Teodor's tree module?

http://cddb.sai.msu.su/~megera/postgres/gist/

You have to expend a little effort in implementing it as the README's in
Russian :) Still has examples tho.

Chris

> -----Original Message-----
> From: pgsql-sql-owner(at)postgresql(dot)org
> [mailto:pgsql-sql-owner(at)postgresql(dot)org]On Behalf Of Christian Rishoej
> Sent: Tuesday, 7 May 2002 9:02 AM
> To: pgsql-sql(at)postgresql(dot)org
> Cc: Anders Johannsen
> Subject: [SQL] Optimizing the implementation of an optimized tree
>
>
>
>
> Hi,
>
> Recently I needed to store a hiearchy of pages on a website in Postgres
> in a way that would allow for fast extraction of parts of the tree for
> menu generation and "path" specification (which nodes in the tree make
> up the path from the root to my position?).
>
> This can be accomplished by letting each node in the tree have an l and
> r value with values determined by traversing the edge of the tree and
> assigning the value of integer that is incremented at each node visit to
> l and doing the same thing for r, this time traversing the edge of the
> tree backwards.
>
> The tree then becomes:
>
> CREATE TABLE tree (
> id serial PRIMARY KEY,
> parent int REFERENCES tree,
> l int DEFAULT NULL,
> r int DEFAULT NULL,
> );
>
> The parent id strictly not needed, but I chose to include it for
> convenience.
>
> I can easily extract a complete branch like this:
>
> SELECT treeNode.id
> FROM tree treeNode, tree treeParent
> WHERE treeNode.l BETWEEN treeParent.l AND treeParent.r
> AND treeParent.id = $1
> ORDER BY treeNode.l
>
> And the "path" from the root to a particular node like this:
>
> SELECT treeNode.id
> FROM tree treeNode, tree currentNode
> WHERE currentNode.r BETWEEN treeNode.l AND treeNode.r
> AND currentNode.id = $1
> ORDER BY treeNode.l;
>
> Now, in order to avoid having to maintain the values of l and r for each
> node when the tree is modified I created triggers in PL/PGSQL that
> handle INSERTs of new nodes into the tree, DELETEs of existing nodes and
> UPDATEs of a node's position in the tree (i.e. the parant field).
>
> The implementation is included as an attachment.
>
> I am very interested in comments on the implementation - especially
> hints on possible optimizations.
>
> It seems to me that the PL/PGSQL-definition of each function is parsed
> at each call. Is this true? Is it possible to avoid this?
>
> It is my understanding that Postgres does not yet support triggers that
> fire on the update of a paricular column. Therefore I have a check in
> the UPDATE trigger that checks if the parent-field was modified. Is
> there any was to do this in a nicer manner?
>
> Regards,
> Christian
>