Re: pointers on representing tree in db?

keep in mind "space vs time". the more efficient the storage, the more processing required to retrieve data. "walking the tree" will be very process intensive with such a simple representation. a basic course on data structures discusses various tree structures and links to optimize traversals using various links and such...and there is always the pre-order, post-order, in-order considerations.

a programmer finds writing code easier than designing good structures. a data modeler finds designing good structures easier than writing good algorithms. as we are in a "space is cheap and so is processing", i suggest response time is the critical factor, which implies effiecient processing should take precendence over conserving space...

the upshot is to consider using a more complex storage structure which will reduce the processing time to locate a node or nodes.

>
> Each row in the Datatable represent a treenode. parent_id is a reference
 to
> another row which acts as a parent for the current one. Example:
>
> (1,1), (2,1), (3,1), (4,2), (5,4),...,
>
> represents a tree with 1 as root. 2 and 3 are children of 1. 4 is a child
 of
> 2 and 5 is a child of 4. The ancestor table for this tree would look like
>
> (2,1), (3,1), (4,2), (4,1), (5,4), (5,2), (5,1)
>
> Thus the ancestor table can be asked for the subtree or the path from a
 node
> to root
>
> select id from ancestor where ancestorid = x
> select ancestorid from ancestor where id = x
>
> Maintenence of the ancestor table is performed via triggers which includes
> the operations posted earlier. Major drawback is that the ancestor table
> grows quite fast for large trees (but disks are cheap these days :-). A
> typical tree in the system where I implemented this solution involves prox
> 100000 nodes.
>
> I havent been able to look at the solution bye Joe Celko yet, so I cant
> comment on that
>
> Cheers
> /Lennart
>
> [...]
>
>
Received on Sat Apr 21 2001 - 03:31:09 CEST