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.

---
$world=~s/war/peace/g

Replies are listed 'Best First'.
Re^6: New PM Feature Request - Node Watch
by kelan (Deacon) on Jun 20, 2005 at 19:55 UTC

    I have an idea on how it could work, but I don't know how database intensive it would have to be. You can probably judge that when you read it.

    Associate "users subscribed to this thread" information with the root node. Then when someone submits a node, you walk up its ancestor line to the root, get the list of subscribers, and send a message to all of them.

    To make it manageable for users, you would probably also want to keep "threads I'm subscribed to" associated with the user. Keeping what is essentially the same data in two separate places is annoying, but otherwise you'd have to scan the entire node base to find which threads a particular user was subscribed to.

    That was the idea that popped into my head when you said that nodes use a parent pointer representation. To be honest, I personally don't think I would use the feature very much because Recently Active Threads fulfills my needs in the thread-watching category.