Acts_as_tree_on_steroids plugin

We’ve been using a home-made extension of acts_as_tree on our production site for quite some time. We finally found some time to release it as a plugin. You can find it on github. It’s not anything special, but it may give you some ideas for doing similar things.

In a nutshell

Extend classic acts_as_tree, acts_as_nested_set to support:

  • Fetching descendants with one sinqle query
  • Fetching ancestors with one single query
  • Fetching the root node of a node with one query
  • Store the level of each node
  • Store the children count of each node
  • Configure a “family” based on the level (depth) that can be different from the root node

Why?

The problem with classic acts_as_tree is that you need a large number of queries to retrieve the ascendants or descendants of a node. If you want the path of a node with a level of N , you need N – 1 queries. If you want all the children and grandchildren and so forth , you need to recurse at least N times. This can become a pain if your tree is more than 3 or 4 levels. Acts as nested set offers functionality to retrieve all descendants of a node with a single query, but you can’t do the same for ancestors which is very useful for a number of things (i.e breadcrumbs).

If your application offers hierarchical based browsing, you ‘ll probably need to query the tree all the time to create breadcrumbs or lists with subcategories. Classic examples are ecommerce applications, price comparison sites etc.

Families

In ecommerce applications it’s very common to have families of products or categories.

For example:

Electronics | -> Computers & Peripherals | --> Storage | ----> Hard Disks | --------> SSD

The root node of “SSD” is “Electronics” but that’s not the actual family of the products because it covers a really big range. The actual family (depending on the application logic) can be “Computers & Peripherals” or “Storage”. If family_level is set to 1 for example, the family will be “Computers & Peripherals”.

Installing

As a plugin:

$ script/plugin install http://github.com/bandito/acts_as_tree_on_steroids.git

Usage

Your model must have the following database tables:

  • parent_id (integer)
  • id_path (string)
  • children_count (integer)
  • level (integer)

Optionally you can enable family support by adding the following column:

  • family_id (integer)

You should add indexes for id_path, parent_id and family_id (level and children_count will probably have a low cardinality, but you can index them anyway).

Then include the helper in your model.

class Category acts_as_tree_on_steroids :family_level => 1 end

How does it work

When a node is created or changes parent the id_path reflects the node path from the root to the node as a comma seperated value of ids. For example a really small tree would look like this:

1 1,2 1,2,3 1,2,4 1,5 1,6 1,6,11 1,6,11,17 20 20,21 20,21,22 20,21,23 20,21,23,25

If we want to get the descendants of node with id_path 1,6 then we would query for id_path LIKE '1,6,%' which would match 1,6,11 and 1,6,11,17. The database will use the index on id_path since it’s not starting with a wildcard.

Likewise, if we wanted the ancestors of the node with id_path 1,6,11,17 we would just query for id IN (1,6,11,17) to get them with a single query.

When to use it

  • You have a category tree that rarely changes but you are doing breadcrumbs and tree representations all the time.
  • You have the need to query for i.e products that belong to the current node and the descendant nodes.

When not to use it

  • If your tree changes frequently then the overhead of the tree traverse can be a pain.
  • You don’t need to know the hierarchy of the node.