# hierarchical tree

Hi experts,
I have to build a hierarchical tree and am uncertain wich method is the best. I have 2 methods to choose from:

1: Flat Table Model - with a parent Id, rank and indent level

2: Modified Preorder Tree Traversal -- with a left and right number

Does anyone know what the advantages / disadvantages are of these methods?

###### Who is Participating?

Commented:
How many nodes you expect to be holding?
How often will nodes be create, destroyed or moved around in the structure?
Will the structure always be accessed from the root or will nodes at lower levers be accessed?

I couldn't see any advantages the the Preorder Tree has over the flat model.   So I thought I would ask what would the set of operations one would want to be able to make on a tree structure.  We would want to be able to acheive these operations without too much complexity balanced with good performance.
One of the problems with trees and DBs is that they often result in cursors or recursive code initiiating queries over and over again so we would want a structure that help us to aviod that.

Defintions.

flat model:-

ID, ParentID, Name, Indentation, Rank  (where rank is a contiguous sequence number through the whole tree)

The pre-ordered model is:-

ID, ParentID, Name, LeftID, RightID (see link in question for diagram)

These are the operations I can think of that we might need and how difficult they might be to achieve.  The list may not be exhaustive and others may better ideas.

Operations on a tree:-

1) Read the tree in sequence given a node in that tree (be that a the root node or a descendant somewhere)

Both methods have a sequential number on which a sort can be achieved.    Both can limit return sets to only children of the current node being queried

2) Limit reading to direct children only  of as specified node.

For both models this is very easy using the ParentID field.

3) Traverse siblings only, forward or backward

At times you might want to the next sibling of the node (or previous sibling) ignoring any children.  This is very similar to the above since siblings will have the same parentID and previous or following sibilings can be identifed by their sequence number.

4) Traverse from child back through ancestors to the final root.

A common operation is discovering a node's ancestors in appropriate sequence (to build a path string for example).  The flat model has trouble with this.  I don't think it can be done with resorting to a cursor (although perhaps there is a better way).  The preordered model can do this since the left hand or right hand sequence id of the original node will always be beween the left hand and right hand sequence ids of it's ancestors also RightID - LeftID  can be used as a sort value to get the ancestors in appropriate order.

5) Delete and Insert nodes.

Both models struggle with this since both have sequence numbers covering the whole range of nodes.  Hence on average half the node records will need to be updated when nodes are randomly added and removed.

6) Testing IsChildOf or IsDescendantOf/IsAncestorOf.

Due to having a ParentID testing for IsChildOf is easy for both.  For IsDescendantOf/IsAncestorOf in the flat model the rank of the next node that has the same or lower indentation level (in effect finding the equivalent to Preorder's RightID) a descendant will be between this and the current nodes rank.   For the Preorder model it is very easy since any node's sequence ids will be within any of those of it's ancestors.

7) Number of Children or Descendants.

For the both models number of children can be acheived with COUNT(*) and the parentID.  Finding number of descendants in the flat model is a little trickier using the same method above to find the effective 'RightID' and then subtracting the current nodes rank.  For the Preordered model number of descendants is simply (Right - Left -1) / 2.

It would seem then that the preordered approach has the more elegant and effecient solutions to the above set of problems.  I also note that IsDescendantOf and Number of Descendants require some special case handling when the context node is on the right-most extremity of the tree.

Anthony.
0

Commented:
Personally I'd go for the first method which in my humble opinion is more clear than the other.

I would  have to say both methods have their strong points and therefor it depends on personal preference which method is 'best'.

You could get several different answers to this questions and all of them would be accurate.

Regards,
Max.
0

Commented:
I second that emotion. Here's some of my own code that seems to work pretty well:

http://www.experts-exchange.com/Web/Web_Languages/ASP/Q_21338262.html
0

Author Commented:
Great anthony, thanks for the answer, this was excactly what i was looking for. Think i'll go for the pre-ordered model, because of the possibility of Traverse from child back through ancestors to the final root.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.