Thread: tree structures in sql - my point of view (with request of comment from joe celko)
tree structures in sql - my point of view (with request of comment from joe celko)
From
Hubert depesz Lubaczewski
Date:
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
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
Re: tree structures in sql - my point of view (with request of comment from joe celko)
From
Josh Berkus
Date:
Hubert, > 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. I'll be posting an article on implementing nested set trees "real soon now". My experieince: Adjacency list trees are easier to understand conceptually, there are more tools on freshmeat.net for them, and they are the most efficient form of tree for graphical display. Nested Set trees are hard to wrap your mind around, lack a lot in the way of code samples on freshmeat, are harder to build GUI tools for, but are much, much faster for determining branch membership and branch parenthood. So which model you use depends on what you intend to do with the tree. -- -Josh BerkusAglio Database SolutionsSan Francisco
Yep! ltree is Faaaast , and i use it at the moment. But will it work in INGRES,DB2 or ORACLE ? what if tommorow my boss ask me to use ORACLE? I have similar issues in using intarray & arrays in PGSQL though reasons of shifting to others dbs are diminishing with every major release of PG ;-) regds mallah. > 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 > > > ---------------------------(end of broadcast)--------------------------- TIP 2: you can get off > all lists at once with the unregister command > (send "unregister YourEmailAddressHere" to majordomo@postgresql.org) ----------------------------------------- Get your free web based email at trade-india.com. "India's Leading B2B eMarketplace.!" http://www.trade-india.com/
mallah@trade-india.com wrote: > > Yep! ltree is Faaaast , and i use it at the moment. > > But will it work in INGRES,DB2 or ORACLE ? > what if tommorow my boss ask me to use ORACLE? > > I have similar issues in using intarray & arrays in PGSQL > > though reasons of shifting to others dbs are diminishing > with every major release of PG ;-) No it will only work on PostgreSQL. If those other apps had loadable types, you might be able to do it by rewriting the code to match their API. -- Bruce Momjian | http://candle.pha.pa.us pgman@candle.pha.pa.us | (610) 359-1001+ If your life is a hard drive, | 13 Roberts Road + Christ can be your backup. | Newtown Square, Pennsylvania19073
Re: tree structures in sql - my point of view (with request of comment from joe celko)
From
knut.suebert@web.de
Date:
Josh Berkus schrieb: > Adjacency list trees are easier to understand conceptually, there are more > tools on freshmeat.net for them, and they are the most efficient form of tree > for graphical display. Hi, for graphical display it may be (the application to display could do the work), but displaying data in tables (or tabulars, if you prefer LaTeX-Syntax) leeds to recursion, I'd say. > Nested Set trees are hard to wrap your mind around, Yes ;-) > lack a lot in the way of code samples on freshmeat, are harder to > build GUI tools for, but are much, much faster for determining > branch membership and branch parenthood. While wrapping around my mind to understand Nested Sets, I got an idea to speed up the count of subnodes and leaves (expensive if only "lft" and "rgt" are used) by adding a third field called "lvl". See http://www.net-one.de/~ks/WOoK/postmaster.php http://www.net-one.de/~ks/WOoK/nset.sql.txt I wrote something about it here some months ago, got a few PMs with positive reactions (so I'm writing this) and a correction. Due to time lack, the 'documents' linked above are still draft, ugly written and the examples may work or not, sorry. The idea of "lvl" maybe useless or not? I'm not an expert. > So which model you use depends on what you intend to do with the tree. And try to understand Oleg's contrib/ltree. It may be better. Greetings, Knut Sübert