Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Re: Tree Structure and Db

by ikegami (Patriarch)
on Jul 05, 2005 at 21:31 UTC ( [id://472616]=note: print w/replies, xml ) Need Help??


in reply to Tree Structure and Db

If you're primarily going to read the tree, it might be advantageous to store pointers to every ancestor instead of just the direct parent. You can query for all the ancestors in one query, and then build the path in Perl. For example,

Nodes ===== id | node_name | parent ----+------------------+-------- 1 | Parent Node1 | 0 2 | Child Node 1 | 1 3 | Sub Child Node 1 | 2 4 | Leaf1 | 3 HasAncestor =========== child | ancestor -------+---------- 2 | 1 3 | 2 3 | 1 4 | 3 4 | 2 4 | 1 SELECT Nodes.* FROM Nodes LEFT JOIN HasAncestor ON Nodes.id = HasAncestor.child WHERE Nodes.id = ? Returns for args (3) ==================== id | node_name | parent ----+------------------+-------- 1 | Parent Node1 | 0 2 | Child Node 1 | 1 3 | Sub Child Node 1 | 2

This way, you can easily fetch an entire subtree. For example,

SELECT Nodes.* FROM Nodes LEFT JOIN HasAncestor ON Nodes.id = HasAncestor.child WHERE HasAncestor.ancestor = ? Returns for args (2) ==================== id | node_name | parent ----+------------------+-------- 3 | Sub Child Node 1 | 2 4 | Leaf1 | 3

You can still fetch only the immediate children. For example,

SELECT Nodes.* FROM Nodes WHERE Nodes.parent = ? Returns for args (2) ==================== id | node_name | parent ----+------------------+-------- 3 | Sub Child Node 1 | 2

Similar for the immediate parent.

Replies are listed 'Best First'.
Re^2: Tree Structure and Db
by pg (Canon) on Jul 06, 2005 at 01:38 UTC

    As the author stated, this structure is good for trees that are mostly static.

    In case the tree can be updated, performance becomes an issue. Even a simple operation as to insert a leaf node, could cause you to insert multiple rows (average number of rows inserted equals average depth of all pathes, and in the worst case, the number of rows get inserted is the length of the deepest path.)

    Look at one more operation: to move a subtree to be under a new parent. if you only store the immediate parent-child relationship, you only need to modify 1 row, but if you store all ancestor, you will need to modify multiple rows for each node in the subtree (basically to modify all relationships towards a node that is above the root of the subtree.)

    Data integraty could also be an issue, a simple coding mistake can spread dirty data all over the place, not just an isolated spot.

      Thanks for expanding on this. I intended to do so, but didn't get get a chance 'til now. That is exactly what I meant by my comment.
Re^2: Tree Structure and Db
by InfiniteLoop (Hermit) on Jul 05, 2005 at 21:38 UTC
    Thnx ikegami. I did think of a lookup table, but was the opposite of your design. This is a great help, thnx again.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://472616]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others surveying the Monastery: (3)
As of 2024-03-19 07:01 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found