From: | Christian Rishoej <chrris(at)mail(dot)dk> |
---|---|
To: | pgsql-sql(at)postgresql(dot)org |
Cc: | Anders Johannsen <anders(at)johannsen(dot)com> |
Subject: | Optimizing the implementation of an optimized tree |
Date: | 2002-05-07 01:02:16 |
Message-ID: | 1020733336.892.79.camel@penelope.dyndns.dk |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-sql |
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
Attachment | Content-Type | Size |
---|---|---|
triggers.sql | text/x-sql | 2.8 KB |
From | Date | Subject | |
---|---|---|---|
Next Message | Christopher Kings-Lynne | 2002-05-07 02:00:24 | Re: Optimizing the implementation of an optimized tree |
Previous Message | Gary Stainburn | 2002-05-06 13:08:18 | Re: summary VIEW |