One of the most obvious problem showed in previous post is the need to issue a single Select for each node to rebuild the tree, but the good thing is that there are a lot of solutions over there to solve this problem. One of the most interesting technique was developed by Joe Celko, first of all I added two field to the table, one field is named * hierarchyLevel *and the other is named * fullpath *, then I setup a couple of triggers.
Both triggers manages these two columns, the first fire on insert
It is really simple, for each node that I insert into the table it simply finds the parent and updates hierarchylevel and fullpath accordingly. The other trigger updates a whole subtree during an update of the parentId property
Et voilà, with this simple solution you will solve a lot of problems, first of all these two extra fields are completely transparent to the application because all the work is made by the two triggers, the next step is to update the model, and finally modify the two extra properties to have private setter, to avoid update to the additional columns.
With this new structure here is the code to load the whole subtree from a node.
Thansk to the fullPath property each descendant of a given node can be find simply with the condition * fullPath.StartsWith(root.fullPath) *and the beautiful thing is that you need only a single SELECT to find all descendant nodes ;). To make things more interesting, Entity Framework resolves all references for you, this means that the whole tree structure is reconstructed in memory, you can verify this with the PrintNoLoad function that print the whole subtree recursively.
This function differs from the old Print routine because it does not check the * employee.Childs.IsLoaded *condition because it is evaluated to False even if the childs are already loaded. This happens because EF had not explicitly loaded all the childs for tree nodes. We are sure that all descendants are loaded because of the fullpath column, but EF could not know it, so it consider the collection “not loaded” and if you check it you still ends with the N select. As you can verify in the following image, the IsLoaded property is false, but the collection of childs contains all the elements. We are sure that this node contains only 2 nodes because we loaded all nodes whose fullpath starts with the root path, so we did not miss any node.
Thus if you use the fullpath trick, be sure not to explicitly load again references. To make everything clearer you can create a method * LoadSubtree *with partial class to shield the user from a deep knowledge of the fullpath structure.
Now you can simply call LoadSubtree to issue only one select that will load all descendants of a node :D. Update of nodes is a breeze thanks to the trigger, if you run this code
you will obtain this output if you the tree before and after the update
As you can see, moving Daniele under the Guardian node correctly moved the whole subtree, the hierarchyLevel and the fullpath are correct thanks to the trigger.
You can also find the root with this method.
It consists of a single query ;) and immediately find the root without the need to traverse the tree. You can also find all nodes that are sons of the same father.
Each operation consists of only one query, and if you put an index on the fullpath column you can expect high speed tree operation ;).