OK, I was monkeying around some more, and it's relatively painless to move a node as well. I think. This is hardly an optimal test database - it has a whopping twenty entries - but enough to get the idea.
function move_node($parent, $title) {
// This is the whack-a-mole method of moving a node (I was too lazy to calculate exactly
// what would be involved in a manual move). So here's what I do - get the right value
// of the new parent node. Set the parent of the moved node as appropriate. Rebuild the
// database for the current node, then rebuild the entire database. As I say, ugly as sin.
// BUT IT WORKS!!
// First, we get the parent's right value
$result = mysql_query('SELECT rgt FROM tree WHERE title="'.$parent.'";');
$row = mysql_fetch_array($result);
$newLeft = $row['rgt'];
// Maybe we should take the root of the entire tree, and rebuild from that? Easy, but time-consuming.
$result = mysql_query('SELECT title FROM tree ORDER BY lft ASC LIMIT 1;');
$row = mysql_fetch_array($result);
$rootLevel=$row['title'];
// Next, we set the node's new parent.
$result = mysql_query('UPDATE tree set parent="'.$parent.'" WHERE title="'.$title.'";');
// Rebuild the tree from this node down, based on a new left value.
rebuild_tree($title, $newLeft);
// Rebuild the entire DB, because you just clobbered the hell out of it!
rebuild_tree($rootLevel, 1);
}
... The real disadvantage to this approach is the double-rebuild of the database. I probably don't have to do it, but I figure better safe than sorry. Please do post a quicker or more efficient way of moving nodes, if anybody has one...
I was having a hardtime applying this concept. this can easily be solve by creating a super root, and all multiple trees point to this. but still the problem is, how to solve the multiple tree problem? help
This is a great article and one major positive I see for the Modified Preorder Tree Traversal method is the inbuilt ordering of elements within the same level on the tree.
Jerry - they aren't multiple trees, and you aren't adding a super-root: you're looking at each physical drive as a tree in and of itself, while Micro$oft, for example, looks at 'My Computer' as the root node, each drive as a child node, and so on. A cubicle jockey might decide that the cubicle cluster should be the root, and each computer a child, and each drive a child of that. A corporate IT guy might look at the entire company's network as a root node, and each cubicle cluster as a child, and so on. Ad nauseam.
And falieson, as I said in your thread in the forums, simply rebuilding the tables resolved that -- problem.
On to more fun - I have built a delete_node() function. Basically, it reverses the add_node() - it removes the node and all descendants, then decrements all nodes with a greater lft and rgt value as appropriate. Here's the code for THAT:
function delete_node($title) {
// This will delete a node AND ALL DESCENDANT NODES! If this isn't what you want,
// consider moving all sub-nodes out first. Alternatively, I can rewrite this to
// remove only the node, and change the nlevel of all child nodes to point to the
// deleted node's parent. However, this strikes me as slightly counter-intuitive.
//
// Logically, I think that the process will be similar to that of adding a node, only
// in reverse. First, we'll need to get the left and right value of the node to be
// removed. When we have this, we'll run a delete to remove any node whose left and
// right fall between these values (inclusive, to remove the node itself). Then, we
// need to decrement all left and right node values by the difference between the
// deleted node's right and left values, plus one.
// First, get the right/left from the selected node.
$result = mysql_query('SELECT rgt, lft from tree WHERE title="'.$title.'";');
$row = mysql_fetch_array($result);
$leftVal = $row['lft'];
$rightVal = $row['rgt'];
$decrementBy = $rightVal - $leftVal + 1;
// Now, we have the range of nodes to be deleted.
$result = mysql_query('DELETE FROM tree WHERE lft BETWEEN '.$leftVal.' AND '.$rightVal.';');
// If this is right, we should decrement all remaining nodes with a left and/or right
// greater than the deleted node's right value by our $decrementBy value. I think.
$result2 = mysql_QUERY('UPDATE tree SET rgt=rgt-'.$decrementBy.' WHERE rgt>'.$rightVal.';');
$result3 = mysql_QUERY('UPDATE tree SET lft=lft-'.$decrementBy.' WHERE lft>'.$rightVal.';');
thanx.
i was about to implement this idea but
the difficult part was populating the values of left and right numbers.
i realize that i have multiple trees.
how to populate the left and right values when using different trees?
the only solution i see now is to add a supernode(my computer being top most root or other reserves superroots. hehe) the so that i can populate the left and right values.
i'll be implementing this soon as soon as i clean up the database.
The point of the left and right is kind of obscure, REMIYA, but it is practical. Typically, when querying a database for a given node and it's descendants, you get the parent, then all nodes that point to that parent, then, for each child, you get all the nodes that point to that child, and so on, and so on... But with the left-right values, asking for any left/right values between a given node will return ALL of its descendants. And ordering them by left value will put them into a recognizable tree. If you want to know more, I'm actually building a PHP5 class to do all this for you. The end user should NEVER see the left and right value, it's purely an internal data representation tool.
Just email or IM if you have questions about this - I'm really enjoying this!
It's a tricky thing, jerry - I'm actually using the tree as a table in my DB, then referencing other tables to contain the data for each tree row. Somehow, I'm thinking this'd be easier in XML. But hey! This way's SO much more fun!
Sorry, I wasn't very clear on that last comment - there are two separate tree structures in my DB, and some of the rows in each tree are tangentially connected to others. It's a pain.
I am asking because RDLDB [doc] is hierarchy-related. And I have never felt the need of having right or left and still have never been wondering which child comes first. The first in is the first out (The first child is first, the second is second, the third is third, etc).
That is why I was wondering why would anyone use right and left. And why would anyone need so many computations.
In the quick view I took of RDLDB, you probably wouldn't need right and left values. There are places where it's appropriate, this may or may not be one.
The point of this whole exercise seems to have been a hypothetical romp down alternative lane. Rather than recursing your way down a tree structure to access subnodes, you can retrieve all subnodes at a single call via this modified tree recursion trick. That's all it is - a trick.
There are calculations, and a number of hoops to be jumped through - the relative value is yet do be determined, by my research. I do see that there is an advantage to this - if nothing else, it changed the way I view tree structures. If you don't need the ability to move nodes, don't care about time spent in recursion calling a DB yet again for a node's children, then this is totally irrelevant.
Just my 0.02
The adjacency list has some problems when data is duplicated when using names in place of id values. For example, the items:
fruit-green-apple-green
and
fruit-ripe-apple-green
may not produce expected results. This problem does not exist if row id's are used instead of names.
Here is a comparison between retrievals on the two methods:
retrieve descendents:
left-right: SELECT title FROM tree WHERE lft > {left value} AND rgt < {right value}
adjacency list: SELECT title FROM tree WHERE ancestorId > {current id} AND ancestorId < ???
retrieve ancestors:
left-right: SELECT title FROM tree WHERE lft < {left value} AND rgt > {right value}
adjacency list: SELECT title FROM tree WHERE ancestorId < {current id} AND ancestorId > ???
The value in the left-right list is that there is not only a starting point - as in ascendency lists - but there is also a stopping point.
I don't see how - in a simple search without joins - an adjacency list can find any relatives (outside of one level up or down) without multiple searches. It doesn't *matter* if there is no use for the left-right structure beyond speeding up the search, since that is the whole goal. To use a hierarchical adjacency list may be better for insertions and human data reading, but it is not better for the most common website function - searching for data.
There is a disadvantage if there are more than a few updates. I do not think this could be used, for example, for storing chat-room messages.
Even still, the left-right can be improved by using the idea of pointers instead of actual numbers. That way, there would be no need for actual numbers to be updated. I am not quite sure if there is anything like this in MySQL.
Or else another table column could be used during insertions. The table would store all insertions along with their insertion row until a certain time, and then do all insertions at once. Still not dynamic, though.
Without reading any tutorials I came up with the adjancey method of storing trees. After reading this I'm going to have to change my method. Excellent tutorial even though it's made my head hurt!
Great article! Also, for those who want it, I needed to store the tree and keep everything alphabetized (I was storing category names in a hierarchy). To do so, I used the following (assume a POSTed form with a 'Parent' and 'New Category' field):
//get the id of the parent to which we're going to add a child
$parent = $_POST['parent'];
$new = $_POST['new'];
//this'll work on a where by ID eventually...
$sql = "SELECT id, lft FROM categories WHERE name = '$parent'";
echo "SQL: " . $sql . "<br>";
$result = mysql_query($sql) or die(mysql_error());
$row = mysql_fetch_assoc($result) or die(mysql_error());
//get the left value of the parent to which we need to add a child
$oldleft = $row['lft'];
//and the id of the parent node
$parentid = $row['id'];
//before any updates occur, get the left value we're going to
//use for the new node.
$sql = " SELECT MIN(lft) as newleft FROM categories "
." WHERE (lft>$oldleft AND name > '$new' AND parent = $parentid)"
." OR (lft>$oldleft AND parent != $parentid)";
$result = mysql_query($sql) or die(mysql_error());
$row = mysql_fetch_assoc($result) or die(mysql_error());
//our new node's left value
$newleft = $row['newleft'];
//move all the existing nodes (right and left) that fall
//after this guy up by 2. The comparisons for name and parentid
//are needed to alphabetize everything, otherwise we could
//just do the update where rgt>$oldleft and be done.
$sql = " UPDATE categories SET rgt=rgt+2 "
." WHERE "
." (rgt>$oldleft AND name > '$new' AND parent = $parentid) "
." OR "
." (rgt>$oldleft AND parent != $parentid)";
echo "SQL: " . $sql . "<br>";
$result = mysql_query($sql) or die(mysql_error());
$sql = " UPDATE categories SET lft=lft+2 "
." WHERE "
." (lft>$oldleft AND name > '$new' AND parent = $parentid) "
." OR "
." (lft>$oldleft AND parent != $parentid)";
echo "SQL: " . $sql . "<br>";
$result = mysql_query($sql) or die(mysql_error());
//go ahead and put the new node in place
$sql = " INSERT categories(name,lft,rgt,parent) "
." VALUES ('" . $new . "'," . ($newleft) . "," . ($newleft+1) . ",$parentid)";
echo "SQL: " . $sql . "<br>";
$result = mysql_query($sql) or die(mysql_error());
You'll notice the updates changed slightly, and we had to find for ourselves the left and right values of the new child node. Please note, I have done about 5 minutes of testing -- if there are any bugs, feel free to post back...
This article explains (in MySql, but i'm sure the logic for other dbs would be similar) how to do a number of things with the lft rgt system: http://dev.mysql.com/tech-resources/articles/hierarchical-data.html
What I did is implement the adjacency list method as a DB function. This way you still have its advantages (elegant design and code, only one update/insert) without the performance penalty: You need only one DB-query for any (sub-)tree - and it is the query overhead that sucks CPU cycles, not the function.
PostgreSQL was capable of recursive functions, not MySQL. This may have changed with the latest 5.x version, but I have not (yet) seen any examples online.
However, I don't see why anyone should stay away from Postgres once he has digged into DBs that far.
Very nice article. It was a good read. I found this PHP tree class that has add and delete features and it is pretty interesting. There is no documentation so you might have to dig into the code to find out how to use it.
We have developed a method for handling unlimited hierarchies without the use of primary keys but using the RDBMS backend. The response time is faster than any conventional datbase architecture would involve
Bookmarks