Re: tree structures in sql - my point of view (with request

While I don't have a time to comment your message I want to point to
contrib/ltree package which is extremely fast :-)

http://www.sai.msu.su/~megera/postgres/gist/ltree

Oleg
On Tue, 3 Sep 2002, Hubert depesz Lubaczewski wrote:

> hi
> i recently spent some time on tree-structures in sql.
> i started with simple id/parent_id approach, used by nearly everyone,
> then i stopped at joe celko's nested sets, but i found it not very
> usable.
> then i found my own (maybe someone wrote it before, but i haven't read
> it, so idea is mine) way.
> in my way we have two tables:
> create table data (id serial, name text);
> create table structure (parent_id int8, child_id int8, depth int8);
>
> structure table represents all paths in tree.
> for example for this tree:
>
> sql
> / \
> postgresql oracle-----__
> | / | \
> linux sco linux windows
> / \
> glibc1 glibc2
>
> (sorry for used data - it is just template, and personally i don't like
> oracle).
> so, for this tree we would populate the tables this way:
> data:
> id | name
> ----+------------
> 1 | sql
> 2 | postgresql
> 3 | oracle
> 4 | linux
> 5 | sco
> 6 | linux
> 7 | windows
> 8 | glibc1
> 9 | glibc2
>
> structure:
> parent_id | child_id | depth
> -----------+----------+-------
> 1 | 1 | 0
> 2 | 2 | 0
> 3 | 3 | 0
> 4 | 4 | 0
> 5 | 5 | 0
> 6 | 6 | 0
> 7 | 7 | 0
> 8 | 8 | 0
> 9 | 9 | 0
> 1 | 2 | 1
> 1 | 3 | 1
> 1 | 4 | 2
> 2 | 4 | 1
> 1 | 5 | 1
> 1 | 6 | 1
> 1 | 7 | 1
> 3 | 5 | 2
> 3 | 6 | 2
> 3 | 7 | 2
> 1 | 8 | 3
> 1 | 9 | 3
> 3 | 8 | 2
> 3 | 9 | 2
> 6 | 8 | 1
> 6 | 9 | 1
>
> (records with depth 0 are technologically not necessary, but they
> simplify and speedup some queries).
>
> with this data layout (easily indexable) you can fetch any data with
> just one select statement (no recursion needed in any case):
> - fetching parent
> - fetching childs
> - fetching "from id up"
> - fetching "from id down"
> also when you need to get indirect parents/childs or when you need only
> some of the data (from me, up, but not more then to my
> grand-grand-grand-father).
>
> i'd like to get some comments on this - how do you see my idea, is it
> worth it, do you know any better way to store trees in sql?
>
> best regards
>
> depesz
>
>

Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg(at)sai(dot)msu(dot)su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83