7 Tree Data Structure Plugins for Rails
A surprising number of applications seem to involve storing a tree of similar items out to some arbitrary depth: managers and employees, assemblies and parts, categories for organizing things. Rails doesn't have any native ability to handle a tree structure - but, as with many other things, plugins fill the gap. And even though this requirement has been around for ages, there's still active development in the plugin world as people try to invent a better tree.
The oldest alternative I know of in this are is acts_as_tree, which was actually pulled out of the Rails core code. This plugin established the standards for the genre: it extends ActiveRecord and supplies an API including parent, siblings, ancestors, root, and so on. Succeeding choices have extended this API but remain generally backwards-compatible.
After acts_as_tree came acts_as_nested_set, which provides tree functionality through a different data structure. This plugin optimizes some queries - such as selecting a subtree of descendants - compared to acts_as_tree, and has become a popular alternative. It's also spawned a number of descendants including better_nested_set and awesome_nested_set (which seems to be the most active of the nested set projects). It's worth noting that awesome_nested_set includes STI support.
But that's not the end of the story. Another project, acts_as_materialized_tree, has just put out a release. A materialized tree tags every node with its path. This makes subtree searches more efficient than they are in acts_as_tree, and insertion and removal of children faster than in the nested set plugins. Of course, there are tradeoffs; moving subtrees and counting descendants are not quick with materialized trees.
There are still more choices beyond these three for specialized situations. Two that are worth knowing about are acts_as_category, which combines trees and lists together (and is probably the most heavyweight of the choices here) and acts_as_ordered_tree, which adds a persistent (and arbitrary) sorting to nodes.
It's impossible to recommend a single tree plugin as the best for all circumstances; it depends on the mix of operations in your application. fortunately, the broad API similarity here makes it relatively easy to test the choices and see which one works best for you.
November 26th, 2008 at 6:11 pm
Thank you for this overview. I have an upcoming project that will need a tree and this article pointed me to several projects I did not know about.
November 27th, 2008 at 4:30 pm
Thanks for the Overview, are there any other options to reflect hierarchiacal structures as with nested sets and trees? I am just wondering. Since the performance of both solutions is not really promissing for updates and tree operations in huge structures.
December 4th, 2008 at 8:54 pm
Looks like the "materialized tree" uses something called "Path Enumeration": http://www.onlamp.com/pub/a/onlamp/2004/08/05/hierarchical_sql.html The comments there are also worth reading, as are Joe Celko's books on SQL.
December 28th, 2008 at 9:43 pm
I've been trying for google for a concept, but can't come up with a the keywords necessary. I'd like to find a plugin designed to help query data sets that are arbitrarily self referential. All of these plugins seem follow the idea that each object has one path through the tree. I'm looking for a plugin that can help find the full set of ancestors and descendants of an object that can have an arbitrary number of parents or children.
As an example, think of a server. It has dependancies on other servers and other servers depend upon it. A group of 10 might have 30 different interdependencies, which makes it difficult to see what "goes down" if one is unplugged.
October 23rd, 2009 at 7:10 am
I recently created another plugin with the same purpose. The description on github:
Ancestry allows the records of a Ruby on Rails ActiveRecord model to be organised as a tree structure (or hierarchy). It uses a single, intuitively formatted database column, using a variation on the materialised path pattern. It exposes all the standard tree structure relations (ancestors, parent, root, children, siblings, descendants) and all of them can be fetched in a single sql query. Additional features are named_scopes, depth caching, depth constraints, easy migration from older plugins/gems, integrity checking, integrity restoration, arrangement of (sub)tree into hashes and different strategies for dealing with orphaned records.
You can find the gem at: http://github.com/stefankroes/ancestry