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

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@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83