Join GitHub today
GitHub is home to over 28 million developers working together to host and review code, manage projects, and build software together.Sign up
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
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.
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.
As a plugin:
script/plugin install http://github.com/bandito/acts_as_tree_on_steroids.git
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
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 to 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.