From: Hubert depesz Lubaczewski <depesz@depesz.pl>
To: pgsql-sql@postgresql.org
Subject: tree structures in sql - my point of view (with request of comment from joe celko)
Date: Tue, 3 Sep 2002 15:22:07 +0200
Message-ID: <20020903132207.GC24879@depesz.pl> (raw)
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
--
hubert depesz lubaczewski http://www.depesz.pl/
------------------------------------------------------------------------
Mój Boże, spraw abym milczał, dopóki się nie upewnię, że naprawdę mam
coś do powiedzenia. (c) 1998 depesz
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: depesz@depesz.pl
Subject: Re: tree structures in sql - my point of view (with request of comment from joe celko)
In-Reply-To: <20020903132207.GC24879@depesz.pl>
* 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