Στις Wednesday 07 April 2010 10:53:00 ο/η silly sad έγραψε:
> On 04/07/10 11:00, Achilleas Mantzios wrote:
>
> > Column | Type | Modifiers
> > ---------+-----------+---------------------------------------------------------------------------
> > id | integer | not null default nextval(('public.paintgentypes_id_seq'::text)::regclass)
> > name | text | not null
> > parents | integer[] |
>
> > The parents of any node to the root, i.e. the path of any node to the root are depicted as
> > parents[0] : immediate parent
> > parents[1] : immediate parent of the above parent
> > .....
> > parents[n] : root of the tree
>
> what this schema gives?
>
> (1) the parent branch in one select.
1st the number of selects has nothing to do with speed
2nd as you will see below, the number of select is always 1, for any basic tree operation.
> what else?
> nothing.
>
No, you are wrong.
1) find immediate father
parents[0] (O(1) complexity)
2) find root
parents[level(parents)] (O(1) complexity)
3) insert a node under a father
O(1) complexity
4) find all immediate children of a father node: (e.g. 2)
SELECT * from paintgentypes where parents[1] =2; (caution: NON indexed select)
or
SELECT * from paintgentypes where itoar(2) ~ parents and level(parents)=(level of node 2 )+1;
5) find all children and grandchildren of a father node: (e.g. 2)
SELECT * from paintgentypes where itoar(2) ~ parents and level(parents)<=(level of node 2 )+2;
6) find whole subtree of a node (e.g. 2)
SELECT * from paintgentypes where itoar(2) ~ parents;
In PostgreSQL, the above model i think is superior to nested trees in every apsect.
This is due to the excellent intarray module.
PS
Excuse me for the typo in the previous mail.
Arrays in postgresql are 1-based.
> compare it to a nested-tree
>
> id | integer | NOT NULL
> name | text | not null
> parent | integer |
> l | numeric
> r | numeric
>
> (1) parent branch in one select
> (2) child subtree in one select
> (it makes a sence!)
>
>
>
--
Achilleas Mantzios