From: Oleg Bartunov <oleg@sai.msu.su>
To: Hubert depesz Lubaczewski <depesz@depesz.pl>
Cc: pgsql-sql@postgresql.org
Subject: Re: tree structures in sql - my point of view (with request
Date: Tue, 3 Sep 2002 21:42:44 +0300 (GMT)
Message-ID: <Pine.GSO.4.44.0209032141350.10568-100000@ra.sai.msu.su> (raw)
In-Reply-To: <20020903132207.GC24879@depesz.pl>
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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-sql@postgresql.org
Cc: oleg@sai.msu.su, depesz@depesz.pl
Subject: Re: tree structures in sql - my point of view (with request
In-Reply-To: <Pine.GSO.4.44.0209032141350.10568-100000@ra.sai.msu.su>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox