Re: recursing down a tree - Mailing list pgsql-general
From | Oleg Bartunov |
---|---|
Subject | Re: recursing down a tree |
Date | |
Msg-id | Pine.GSO.4.44.0207151632170.15324-100000@ra.sai.msu.su Whole thread Raw |
In response to | Re: recursing down a tree (71062.1056@compuserve.com (--CELKO--)) |
List | pgsql-general |
On 12 Jul 2002, --CELKO-- wrote: > >> I did a little research on the subject and it seemed quite > interesting. However, it seemed that insertion would require updating > most of the tree for > a minor insert. Can you send along a few more details about your setup > and algorithms? I would like to find more information about this. << > > I am writing a separate book on "Trees in SQL" which will cover > several different models; I hope to be done by the end of the year. I > also hope to win the lottery. Cool. btw, we have developed contrib/tree module which is very fast for r/o operations. It's available on our GiST development page http://www.sai.msu.su/~megera/postgres/gist/tree/README.tree.english The idea is simple - to code path information to the node name, so tuple itself does know it's place in hierarchy. It's sort of cheating of relational data model. Also, we're developing another module - contrib/ltree which will be much more powerful (we use real names in path instead of digits as in contrib/tree). > > Updating is not the problem people think it is. The nodes are in one > table and the structure is in another. The Tree table has (node_id, > lft, rgt) in its rows and those the rows are very short; a lot of them > fit into main storage at once. Since the newest addition (i.e. > youngest sibling) is made on the right side of the immediate > subordinates (siblings are ordered in the Nested Set model), you do > not have to update half the nodes on average. Finally, in the real > world, the tree structure tends to stay the same and the nodes change > -- even dot-com firms don't re-organize faster than their personnel > turnover <g>. > > However, someone did have a situation where they used the nested set > model for the message threads in a newsgroup front end. Their answer > to this "fixed nodes and changing structure" problem was to use large > gaps in the numbering of (lft, rgt) pairs instead of incrementing > (lft, rgt) by one. > > Think about it; subordination is shown with the BETWEEN predicate; any > sequence of unique, nested numbers will work. Subtree size is shown > by the formula ((rgt-lft+1)/2) which does depend on an increment and > happens to also give you subordination. > > ---------------------------(end of broadcast)--------------------------- > TIP 3: if posting/reading through Usenet, please send an appropriate > subscribe-nomail command to majordomo@postgresql.org so that your > message can get through to the mailing list cleanly > 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
pgsql-general by date: