acts-as-tree-with-dotted-ids
acts-as-tree-with-dotted-ids copied to clipboard
xavier
A drop in replacement for acts_as_tree with super fast ancestors and subtree access
= 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
Gem packaging and Rails 3 compatibility by Thomas Maurer -- http://github.com/tma
Kudos to all the contributors to the original plugin.
Copyright (c) 2007 David Heinemeier Hansson, released under the MIT license
Copyright (c) 2008 Xavier Defrang, released under the MIT license
xavier