Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
A drop in replacement for acts_as_tree with super fast ancestors and subtree access
Ruby
branch: master

README.rdoc

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.

  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.

Compatibility

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

Thanks

Gem packaging and Rails 3 compatibility by Thomas Maurer – github.com/tma

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

Something went wrong with that request. Please try again.