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.

Development¶ ↑

Setup an sqlite database and run the specs.

rake sqlite migrate:up
rake sqlite spec

You can also enable performance testing by prepending the performance task. Beware these take considerable time to run.

rake sqlite performance spec

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.