Nested sets: another data model for record hierarchies

Continuing the discussion from Performance core principles: 13. Miscellaneous:

I guess that was because you were relying on some data that could not be indexed. It is one of the drawbacks of the adjecency list model (the traditional approach to hierarchies). Nested set relies on indexed data to query the structure, so you can expect to have great performance gains right there.

Are your users going to be browsing the structure via a portal or a list view? Do you expect them to explode many nodes from different branches at the same time or a single one at a time (closer to accordion behavior, opening one closes the other ones.)

I retrieved my sample file from 2015 (1.7 MB) . I tried to make some of it more English, but it was built for a French audience. This sample file does not implement transactions, so it is simply for showcasing the basic concepts. The category list & detail layouts contain the things that are relevant to nested sets.

Here are some elements that are worth outlining:

  • Each child can only have one parent
  • Each extremity has right tag = left tag +1
  • The left tag of a node is always included between the left and right tags of each of its parents
  • Getting a parent children count is easy: (right - left - 1)/2
  • queries that used to rely on recursion (expensive performance wise, degrading based on the amount of data) no longer rely on recursion (performance gains)

Some drawbacks:

  • Not as easy to find direct parent or child (only one level above or under)
  • Sorting the data can be challenging.
  • Updates usually require to update many records from the whole structure, so that requires more work (performance wise, updating multiple records can only be more expensive than updating a single record.)

Recommended reading:


@Bobino Thank you for your time and effort in helping me understand the nested set model. Also for the fact that you translated some things in your example file into English. Whereby: Je comprends le français dans une certaine mesure. Je l'ai appris à l'école - il y a environ 35 ans. Malheureusement, j'avais rarement l'occasion de parler français, mais au moins je lisais quelque chose de temps en temps.

I will understand the file - hopefully :wink:

The topic is surely interesting for others, too. I will have a look in the file tomorrow how you have approached this. And then I will experiment with my material and see how well the model works for it. Of course, I'll also try to make it transactional.

Once again - thank you very very much! :+1:
This is really great! And I will of course have a look at the websites you linked.


As soon as I have worked my way through it, I will report here about my experiences with it. Whether the performance is as I hope and whether the whole thing works in my scenario. This will take a few days, but: I'll be back! :sunglasses: