Hyrarchy
Hyrarchy (Hybrid hieRarchy) is a gem and Rails plugin for working with hierarchic data in ActiveRecord. Your models gain methods for finding an instance’s parent, children, ancestors, descendants, and depth, as well as a named scope for finding root nodes.
To use Hyrarchy in your Rails app, copy the plugin from the gem into your app’s vendors/plugins directory. (The plugin is just a two-liner that loads and activates the gem.)
To use Hyrarchy in one of your models, add the following line to the class:
class Comment < ActiveRecord::Base
is_hierarchic
end
Then add the hierarchic columns to the model’s database table:
class MakeCommentsHierarchic < ActiveRecord::Migration
def self.up
add_hierarchy :comments
end
def self.down
remove_hierarchy :comments
end
end
Or you can put it in the same migration as the table’s creation:
class CreateCommentsTable < ActiveRecord::Migration
def self.up
create_table :comments do |t|
t.integer :author_id
t.text :body
end
add_hierarchy :comments
end
def self.down
drop_table :comments
end
end
Performance
On MySQL, Hyrarchy scales to at least one million nodes with insertion and access times below 100ms. On SQLite, times are below 200ms.
Database Compatibility
Hyrarchy has been tested on MySQL 5 and SQLite 3.
Replacing awesome_nested_set
Hyrarchy is designed to be an almost-drop-in replacement for awesome_nested_set. All of awesome_nested_set’s methods are implemented by Hyrarchy, but you’ll need to replace calls to acts_as_nested_set with is_hierarchic. You’ll also need to replace awesome_nested_set’s database columns with Hyrarchy’s, which you can do with an option to the add_hierarchy migration method:
add_hierarchy :comments, :convert => :awesome_nested_set
The convert option will modify the table structure but it won’t rebuild the hierarchy information. You can rebuild it by calling rebuild! on your hierarchic model class:
Comment.rebuild!
The same option can be used with remove_hierarchy for the down half of a migration.
Hyrarchy doesn’t yet support awesome_nested_set’s scoping feature or its view helper.
Implementation Details
Under the hood, Hyrarchy uses a combination of an adjacency list and a rational nested set. The nested set uses a technique developed by (I think) Vadim Tropashko, in which the left and right values are generated using Farey sequences. This makes it possible to insert new records without adjusting the left and right values of any other records. It also makes it possible to do many operations (like determining a record’s depth in the tree) without accessing the database. For operations where rational nested sets perform poorly (such as finding a node’s immediate descendants), the adjacency list is used.
Credits and Copyright
Heavily based on works by Vadim Tropashko and Wim Lewis. Implemented by Dana Danger. Tolerated by VivaZoya. Copyright © 2008 The Indianapolis Star, released under the MIT license. See LICENSE for details.