in reply to Re^4: New PM Feature Request - Node Watch
in thread New PM Feature Request - Node Watch
Yes thats correct. As is quite normal in DB stored trees. Its the easiest way to store a tree as it means that the entire dataset can be stored in only one table. If you have child pointers then you need two tables, one base table for the leafs and one associative table showing which children are associated to which parents. So for instance with parent pointers to find all children of a node you say
select * from nodes where parent_id=?
Whereas as with a child pointer representation you have to do something like:
select * from nodes,children where nodes.node_id=children.node_id and children.parent_id=?
However the real contrast is totally different representations, such as using overlapping line segments to determine parenting. In this model you store root pointer information along with left/right markers. The root of the thread has a left marker of 0 and a right marker of ∞, child nodes have subsections, so if there were two children they might have bounds of (0,∞/2) and (∞/2,∞). (With ∞; being some huge number). The nice thing about this approach is that you can do things like find the descendants of a given node (call it X) quickly:
select * from nodes where nodes.root_id=X.root_id and X.left<= nodes.right and nodes.left<=X.right
The advantage of this approach for node watching is that you can easily determine if the descendent tree has changed, by simply doing the above query to determine the latest timestamp. Doing similar with parent pointer or child pointer representations is much more computationally intensive.