Acts_as_tree_on_steroids plugin

02/02/2010 engineering
0

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 anscestors 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 usefull for a number of things (i.e breadcrumbs)

If your application offers a 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 actually family of 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

h2. Usage

Your model must have the following database tables:

  • parent_id (lnteger)
  • 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.

Ποιοι είμαστε

Offices

Η Skroutz Α.Ε. ιδρύθηκε το 2005 και δραστηριοποιείται στην ανάπτυξη καινοτόμων υπηρεσιών τεχνολογίας, δημιουργώντας πρωτοποριακές πλατφόρμες ηλεκτρονικού εμπορίου και ιστοσελίδες υψηλής απόδοσης.

Με έδρα την Αθήνα, η Skroutz Α.Ε. είναι το κορυφαίο digital brand πίσω από τη δημιουργία και την εξέλιξη των δυνατοτήτων της πρωτοποριακής μηχανής αναζήτησης και σύγκρισης τιμών και προϊόντων www.skroutz.gr. Η εταιρεία παρέχει ένα εύρος χρηστοκεντρικών λύσεων λογισμικού και πλατφόρμων ηλεκτρονικού εμπορίου αξιοποιώντας νέες τεχνολογίες και μεθοδολογίες, που αναδεικνύουν το πάθος του ανθρώπινου δυναμικού της.