A drop in replacement for acts_as_tree with super fast ancestors and subtree access
#4 Compare This branch is 14 commits ahead, 1 commit behind xavier:master.
Latest commit 6be7fa1 Feb 10, 2015 @tma Merge pull request #3 from tma/cleanup
! more cleanup, fix tests to cope with arel, version bump to 1.2.0, only...



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"


 \_ child1
      \_ subchild1
      \_ subchild2


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"


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


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

  1. 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.

  2. Call MyTreeModel.rebuild_dotted_ids! and you are ready to go.


From version 1.2.0, this gem is only compatible with Rails 4.x and up.


Kudos to all the contributors to the original plugin.

Copyright © 2007 David Heinemeier Hansson, released under the MIT license

Copyright © 2008 Xavier Defrang, released under the MIT license