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