Editorial Rss

A Lesson in Hierarchies

The rest of this week I’m going to take a look at some of the options available to you for creating hierarchical data structures in a relational database.

Today we look at a hierarchy built on a linked list through the use of a single table having a self join to a parent node.
The table would have a primary key, and a parent foreign key. Records are associated to a parent record through a value in the ParentHieararchyId column, creating a linked list. Multiple records may have the same ParentHieararchyId value. Every record, except the root record(s) have a ParentHieararchyId. To create an instance of  the hierarchy you walk the chain of relationships defined in the Hiearchy Table.
You have a couple options for building an instance of a  hierarchy using this data structure. You can recursively retrieve each node, starting with the root node (the record with no ParentHierarchyId). Then return all the children of the parent node. Then retrieve the children of the parent nodes children, continuing with this process until no more child records are returned. This method has a lot of traffic back and forth. It works well when you want to lazy load your object, instead of retrieving everything all in a single query.

If you wish to retrieve all of the data up front, this methodology can be improved by simply returning all the data in a single query from the database. Then in an application layer, you can build your hierarchy from all the data retrieved from the database. If you sort the data by ParentId, you can simply work through the set of data, and create nodes under the appropriate parent.

Tomorrow we'll look at another database hierarchical data structure.