Re: recursing down a tree

On Fri, 28 Jun 2002, Carl Meyer wrote:

> id,parent,description
>
> and parent points to an id of the very same table. now i have
> a specific id and i want to recurse down the tree to the root.
> is it in any way possible to do that without to doing a sql query
> for each level ?

There are a bunch of different ways to do this (several of which
have been mentioned already), and a lot of it depends on the type
of data you store, how big your trees are, etc. etc.

One really, really fast option, if you don't need to be moving up
and down arbitrary levels, but just need to find the root, or find
all children in a given tree, or similar operations, is to add a
column holding the ID of the root of the tree the node is in:

id, root_id, parent_id, description

I was tending to use smaller trees, though, (typically a few hundred,
almost never more than a few thousand nodes), and so for any more
complex searches manipulation I'd just load the whole tree into
memory with one query. (I had a clustered index on root_id--this
was MS SQL Server--and so this load was extremely fast; just a
matter of reading a few disk blocks.) This turned out to be far
more efficient and faster than doing three or four queries to get
up to the root.

cjs
--
Curt Sampson <cjs(at)cynic(dot)net> +81 90 7737 2974 http://www.netbsd.org
Don't you know, in this new Dark Age, we're all light. --XTC