acts_as_tree_with_dotted_ids

This is an extension to Rails good old acts_as_tree which uses an extra “dotted_ids” column which stores the path of the node as a string of record IDs joined by dots, hence the name.

This optimization solves performance issues related to in-database tree structure by allowing for direct O(1) ancestor/child verification and O(N) subtree access with one single query.

class Category < ActiveRecord::Base
  acts_as_tree_with_dotted_ids :order => "name"
end

Example:

root
 \_ child1
      \_ subchild1
      \_ subchild2

Usage:

root      = Category.create("name" => "root")
child1    = root.children.create("name" => "child1")
subchild1 = child1.children.create("name" => "subchild1")

root.parent   # => nil
child1.parent # => root
root.children # => [child1]
root.children.first.children.first # => subchild1
child1.ancestors_of?(subchild2)    # => true
subchild1.descendant_of?(root)     # => true

root.id              # 1
child1.id            # 2
subchild1.id         # 3
root.dotted_ids      # "1"
child1.dotted_ids    # "1.2"
subchild1.dotted_ids # "1.2.3"

Improvements

The plugin adds the following instance methods:

ancestor_of?(node)
self_and_ancestors
descendant_of?(node)
all_children
depth

The following methods of have been rewritten to take advantage of the dotted IDs:

root
ancestors
siblings
self_and_sibblings

Migration

If you already have an acts_as_tree model, you can easily upgrade it to take advantage of the dotted IDs.

Just add the dotted_ids column to your table. In most case a string should be enough (it’s also better for the indexing) but if your tree is very deep you may want to use a text column.
Call MyTreeModel.rebuild_dotted_ids! and you are ready to go.

Compatibility

Tested with Rails 2.x and MySQL 5.x as well as SQLite.

Thanks

Kudos to all the contributors to the original plugin.