Storing Hierarchical Data in a Relational Database
Posted in Websites or Tools
In a previous job I dealt with the IT tasks related to a multi level marketing business. We stored everything in a database of course and due to the nature of multi level marketing most of the operations performed had to take into account the tree like structure of the people involved.
An example would be, given a party that was run there would be rewards based on future bookings made, how much the party sold and so on. The largest direct benefitor of these rewards was of course the person that ran the party. However this person had a manager, who in turn may have a manager who in turn may have a manager and so on up the tree. At each level the manager got a cut based on a number of factors such as how many people she was managing, what her position was an so on.
At the time the way I dealt with trees was via adjacency lists, mostly because that’s what was most logical to me and how it seemed everyone else did it. I thought I’d have a look around and see if anything had changed in the last couple of years and found this article on using nested sets to deal with hierarchical data.
It seems to me that this method trades insertion performance for selection performance which for most situations is fantastic! It seems to be exactly what I need given I’ll be performing far more selects than inserts and it also has given me another tool in my toolbox.
It’s long been understood that to keep someone in IT happy one of the most important things is change and new stuff. I think this constitutes new stuff for me.
Mark W
Oct 31, 2008
I read the same article a few months back when I was designing a schema for managing a hierarchy of climbing locations. The concern I had was that you need a very robust data access layer. Any corruption in your data could quickly break your entire tree. You can probably forget about running ad-hoc queries from the command line due to the added complexity. For any non-trivial application, I’d be tempted to additionally store parent references, so that the nested sets data could be rebuilt.
It’s frustrating that MySQL doesn’t support hierarchical queries – a feature that has been in MS-SQL for several years and Oracle for significantly longer!
mlambie
Oct 31, 2008
I’m using nested sets in a Rails application to represent a hierarchical menu system with great success. I used the awesome_nested_sets plugin.
This plugin uses a parent_id along with lft and rgt so it’s easy to traverse the tree top-to-bottom, as Mark suggested.