Few year before, I came across a requirement where I needed to build a dynamic hierarchy for organization structure with employee and subordinate relationship. Based on the general idea, I initially thought of implementing it according to one-to-many relationship based on a foreign key. But, soon I realized that this approach is not going to work because the SLA to fetch the data from the database was very tight and this approach incorporated a lot of joins and doesn’t handle large and dynamic hierarchies very well. Then, I came to know about the concept of Nested Set approach which absolutely fit my requirement. Here, we will be discussing about both the approaches in details with their pros and cons.
Introduction
Most of the projects use Relational Databases to persist the data. And many times, they get a requirement where they need to store hierarchical data in the database. The most intuitive way of storing this kind of data is to have a one-to-many relationship within the same table. In this case, there will be a foreign key column which would be pointing to another row in the same table. But is this a very good approach?
Lets take an example of an E-commerce firm. This firm sells furnitures and wants to create a hierarchy of categories in order to represent different types of furnitures. Based on this requirement, the tree structure would consists of several top level categories where each category can contain one or more second level categories and so on. Following is a sample hierarchy of categories:
There are two approaches to handle this scenario.
- Adjacency list
- Nested set
Both of these approaches have pros and cons. Lets discuss about them in detail.
My Experience 