DaveWentzel.com            All Things Data

Hierarchical and Tree Designs


This is not meant to be an all-encompassing look at these items, just some random musings. 
Some background.  In sql most of these designs will be graph structures which are diagrams of dots/nodes/vertices and the lines or edges that connect them.  How to traverse the graph is the solution you will eventually implement.  A directed graph allows edge traversal in a single direction.  A cycle is a graph that makes a loop.  A tree is a graph that has no cycles.  It has one fewer edges than nodes.  A hierarchy is simply a tree when there is the concept of parent and child, or manager and employee. 
The edges are often referenced as a two dimensional array of nodes.  This is the adjacency list model.  You'll recognize this pattern as the way most manger/employee hierarchies are modeled. 
The path enumeration model is another way to model a tree.  In this case you are storing the path in the db.  It's best to make the node identifiers the same format, datatype, and length to make breaking apart the elements and querying a little easier.  To find the depth of the tree you simply divide the length of the path by the length of one identifier.  The use of XPATH is another good way to make querying a lot easier since an XML document is really just path enumeration. 

Add new comment