I have a Ruby On Rails project with a fair amount of hierarchical data.  I have already tried a few different techniques of managing this data.  Nested sets and materialized paths sound good in theory but in practice they didn’t work out so well.  Here are some thoughts thus far.

What I’ve Tried

• Adjacency List – This is where I started with a simple parent_id to map the data.  This biggest downside is that getting data for an entire tree is expensive and somewhat difficult.  If you have a tree and want to know the number of descendants you have to recursively query through the table.
• I implemented this myself so I have no recommendations on gems.
• erdah/acts_as_tree – GitHub
• saturnflyer/acts_as_tree – GitHub – acts_as_tree_rails3
• drewtempelmeyer/acts_as_king – GitHub
• parndt/acts_as_tree – GitHub
• Path Enumeration / Materialized Path – This is a somewhat obvious idea in which you store a list of ancestor id’s and use a SQL LIKE query to easily query the entire tree or any subset of the tree.  The problem I ran into is that my data had enough depth to overflow the string fields.  Also, from a data storage perspective there is a lot more data being stored in the table and referential integrity is not ensured.
• I implemented this myself so I have no recommendations on gems.
• mdub/arboreal – GitHub
• stefankroes/ancestry – GitHub
• tma/acts-as-tree-with-dotted-ids – GitHub
• Nested Set – I think nested sets are a very clever idea.  I thought this would be a good solution since this project has read a lot more than writes which are problematic for nested sets.  However in practice I found nested sets to be very difficult to manage.  I think the complexity is a bit too high.  I also found the existing gems to be buggy and I didn’t want to invest the time in my own implementation.
• I found simple_nested_set to be the best though it does not have an efficient rebuild method.  So I took the rebuild method from nested_set and awesome_nested_set and adapted it as well as the each_with_level code.
• svenfuchs/simple_nested_set – GitHub
• skyeagle/nested_set – GitHub
• collectiveidea/awesome_nested_set – GitHub
• railsbros-dirk/better_nested_set – GitHub
• jnicklas/eb_nested_set – GitHub
• julik/make_like_a_tree – GitHub
• probably more

Other Options

• Closure Table – more efficient than other methods but I’m not sold on having an additional table with large numbers of rows.  After my experience with nested sets I’m leery of overkill solutions and I think this fits.  But there is a gem called closure_tree and I would probably choose this over nested set or materialized path solutions.
• mceachen/closure_tree – GitHub
• SQL99 WITH RECURSIVE – If using a database that implements SQL-99 recursion (postgres does, mysql does not) you can use an adjacency list and have SQL do the heavy lifting of finding descendants.  The gem acts_as_sane_tree implements this for postgres databases.
• chrisroberts/acts_as_sane_tree – GitHub
• Adjacency List plus root_id – It occurs to me that there is a distinct difference between needing to get a subset of a tree and just wanting to query an entire tree with 1 query.  For this project I have only need of the latter which makes most of these options overkill because I simply do not need their features.  I think I can get the performance I want by simply adding a root_id field and using that to query entire trees or count descendants from the root.  It’s a lot less data than other solutions and relatively trivial to implement.  As far as I know there are no gems with this pattern, though it would be a nice addition to something like acts_as_tree.

Links

• Trees and Hierachies in SQL: Adjacency List Model
• TOP 1 WITH TIES: Path Enumeration using Prime Number Products
• http://www.slideshare.net/billkarwin/models-for-hierarchical-data/69