Last Updated: January 11, 2017

Nested Set Model: the best approach to deal with hierarchical data

When you are working in a Ruby and Rails application, sometimes you need to manage a model/table that represents hierarchical data (aka tree), such as product categories, folders, etc.

The easiest and most common approach to deal with that scenario consist of implementing the Adjacency List Model, in which each table record (node) has a reference to its parent.

Besides, we have a widely used gem to help us: act as tree.

However, this approach has major drawbacks in some situations, specially when you want to query for all the descendants of a specific node. The only way to get it is traversing recursively its children, making a query for each child in each level.

For example: Getting a representation of the complete tree using act as tree gem:

def get_tree(node)
  node.children.each do |child|
    puts child.name
    get_tree(child)
  end
end

get_tree(Category.root)

This is extremely inefficient, specially on large trees, because each "node.children" call makes a query to the database.

Maybe you can implement a more efficient code using SQL directly (assuming the risk of incompatibilities if the project is migrated to another DBMS in the future), but the number of queries will be always size-tree dependant.

There is an exception: using a recursive query. Nevertheless, the world's most used open source relational DBMS, MySQL, lacks of recursive query support.

Nested Set Model to the rescue

Here is when Nested Set Model can help us. It is another approach to represent tree-like data that kill the problem shown above.

To understand the difference between Adjacency List and Nested Set, I recommend you to visit Mike Hillyer's explanation.

In brief, each table record (node) has two extra fields that let us know and extract all its children tree in just one query. Spectacular!

The drawbacks: As you can see in Mike Hillyer's link, it can be a little painful to maintain the tree well formed on insertions or removes.

But here is when ruby gems magic comes to save us. With the awesome nested set gem you can abstract from the maintenance of the tree and take advantage of the improvement in efficiency that bring us Nested Set Model.

The above example rewritten with nested set gem is as simple as follows:

Category.root.descendants

Wow! Simpler code and an awesome performance improvement. It only needs two queries: one to get the Category root and one (and only one) to get the rest of the tree. No matter how large it can be!

Sources: