Ancestry is a gem that allows rails ActiveRecord models to be organized as a tree structure (or hierarchy). It employs the materialized path pattern which allows operations to be performed efficiently.

There are a few common ways of storing hierarchical data in a database: materialized path, closure tree table, adjacency lists, nested sets, and adjacency list with recursive queries.

• Store hierarchy in an easy to understand format. (e.g.: /1/2/3/)
• Store hierarchy in the original table with no additional tables.
• Single SQL queries for relations (ancestors, parent, root, children, siblings, descendants)
• Single query for creating records.
• Moving/deleting nodes only affect child nodes (rather than updating all nodes in the tree)

• relations are implemented as scopes
• some relations can be implemented as ActiveRecord associations
• STI support
• Arrangement of subtrees into hashes
• Multiple strategies for querying materialized_path
• Multiple strategies for dealing with orphaned records
• depth caching
• depth constraints
• counter caches
• Multiple strategies for moving nodes
• Easy migration from parent_id based gems
• Integrity checking
• Integrity restoration
• Most queries use indexes on id or ancestry column. (e.g.: LIKE '#{ancestry}/%')

Since a Btree index has a limitation of 2704 characters for the ancestry column, the maximum depth of an ancestry tree is 900 items at most. If ids are 4 digits long, then the max depth is 540 items.

When using STI all classes are returned from the scopes unless you specify otherwise using where(:type => "ChildClass").

• Ancestry 2.x supports Rails 4.1 and earlier
• Ancestry 3.x supports Rails 4.2 and 5.0
• Ancestry 4.x supports Rails 5.2 through 7.0
• Ancestry 5.0 supports Rails 6.0 through 8.1
• Ancestry 6.0 supports Rails 7.0 through 8.1

Follow these steps to apply Ancestry to any ActiveRecord model:

# Gemfile

gem 'ancestry'

$ bundle install

$ rails g migration add_ancestry_to_[table]

class AddAncestryToTable < ActiveRecord::Migration[7.0]
  def change
    change_table(:table) do |t|
      t.ancestry
    end
  end
end

The t.ancestry helper creates the column with the correct type, collation, and indexes for your database. It accepts options for cached columns and ancestry formats:

t.ancestry format: :materialized_path2, cache_depth: true, parent: true, counter_cache: true

For manual column setup or advanced options, see Ancestry Database Column.

$ rake db:migrate

# config/initializers/ancestry.rb

# use the newer format
Ancestry.default_ancestry_format = :materialized_path2
# Ancestry.default_update_strategy = :sql

# app/models/[model.rb]

class [Model] < ActiveRecord::Base
   has_ancestry
end

Your model is now a tree!

You can use parent_id and parent to add a node into a tree. They can be set as attributes or passed into methods like new, create, and update.

TreeNode.create! :name => 'Stinky', :parent => TreeNode.create!(:name => 'Squeeky')

Children can be created through the children relation on a node: node.children.create :name => 'Stinky'.

The node with the large border is the reference node (the node from which the navigation method is invoked.) The yellow nodes are those returned by the method.

parent	root1	ancestors
nil for a root node	self for a root node	root..parent
parent_id	root_id	ancestor_ids
has_parent?	is_root?	ancestors?
parent_of?	root_of?	ancestor_of?
children	descendants	indirects
child_ids	descendant_ids	indirect_ids
has_children?
child_of?	descendant_of?	indirect_of?
siblings	subtree	path
excludes self	self..indirects	root..self
sibling_ids	subtree_ids	path_ids
has_siblings?
sibling_of?(node)	in_subtree_of?

When using STI all classes are returned from the scopes unless you specify otherwise using where(:type => "ChildClass").

^{1. [other root records are considered siblings]↩}

The has_ancestry method supports the following options:

:ancestry_column       Column name to store ancestry
                       'ancestry' (default)
:ancestry_format       Format for ancestry column (see Ancestry Formats section):
                       :materialized_path   1/2/3, root nodes ancestry=nil (default)
                       :materialized_path2  /1/2/3/, root nodes ancestry=/ (preferred)
                       :ltree               1.2.3, root nodes ancestry='' (PostgreSQL only)
                       :array               {1,2,3}, root nodes ancestry={} (PostgreSQL only)
:orphan_strategy       How to handle children of a destroyed node:
                       :destroy   All children are destroyed as well (default)
                       :rootify   The children of the destroyed node become root nodes
                       :restrict  An AncestryException is raised if any children exist
                       :adopt     The orphan subtree is added to the parent of the deleted node
                                  If the deleted node is Root, then rootify the orphan subtree
                       :none      skip this logic. (add your own `before_destroy`)
:cache_depth           Cache the depth (number of ancestors) in a column: (See Cached Columns)
                       false    Do not cache depth (default)
                       true     Cache depth in 'ancestry_depth'
                       :virtual Use a database generated column
                       String   Cache depth in the column referenced
:parent                Store the parent id in a column: (See Cached Columns)
                       false    Do not store parent id (default)
                       true     Cache parent id in 'parent_id' and define
                                belongs_to :parent and has_many :children associations
                       :virtual Use a database generated column with associations
:root                  Store the root id in a column: (See Cached Columns)
                       false    Do not store root id (default)
                       true     Cache root id in 'root_id' and define
                                belongs_to :root association
                       :virtual Use a database generated column with association
:primary_key_format    Format of the primary key:
                       :integer  integer ids (default)
                       :uuid     UUIDs
                       :string   alphanumeric string ids
:touch                 Touch the ancestors of a node when it changes:
                       false  don't invalid nested key-based caches (default)
                       true   touch all ancestors of previous and new parents
:counter_cache         Cache the number of children in a column:
                       false  Do not cache child count (default)
                       true   Cache child count in 'children_count'
                       String Cache child count in the column referenced
:update_strategy       How to update descendants nodes:
                       :ruby  All descendants are updated using the ruby algorithm. (default)
                              This triggers update callbacks for each descendant node
                       :sql   All descendants are updated using a single SQL statement.
                              This strategy does not trigger update callbacks for the descendants.
                              This strategy is available only for PostgreSql implementations

Legacy configuration using acts_as_tree is still available. Ancestry defers to acts_as_tree if that gem is installed.

The navigation methods return scopes instead of records, where possible. Additional ordering, conditions, limits, etc. can be applied and the results can be retrieved, counted, or checked for existence:

node.children.where(:name => 'Mary').exists?
node.subtree.order(:name).limit(10).each { ... }
node.descendants.count

A couple of class-level named scopes are included:

roots                   Root nodes
ancestors_of(node)      Ancestors of node, node can be either a record or an id
children_of(node)       Children of node, node can be either a record or an id
descendants_of(node)    Descendants of node, node can be either a record or an id
indirects_of(node)      Indirect children of node, node can be either a record or an id
subtree_of(node)        Subtree of node, node can be either a record or an id
siblings_of(node)       Siblings of node, node can be either a record or an id

It is possible thanks to some convenient rails magic to create nodes through the children and siblings scopes:

node.children.create
node.siblings.create!
TestNode.children_of(node_id).new
TestNode.siblings_of(node_id).create

With depth caching enabled (see has_ancestry options), an additional five named scopes can be used to select nodes by depth:

before_depth(depth)     Return nodes that are less deep than depth (node.depth < depth)
to_depth(depth)         Return nodes up to a certain depth (node.depth <= depth)
at_depth(depth)         Return nodes that are at depth (node.depth == depth)
from_depth(depth)       Return nodes starting from a certain depth (node.depth >= depth)
after_depth(depth)      Return nodes that are deeper than depth (node.depth > depth)

Depth scopes are also available through calls to descendants, descendant_ids, subtree, subtree_ids, path and ancestors (with relative depth). Note that depth constraints cannot be passed to ancestor_ids or path_ids as both relations can be fetched directly from the ancestry column without needing a query. Use ancestors(depth_options).map(&:id) or ancestor_ids.slice(min_depth..max_depth) instead.

node.ancestors(:from_depth => -6, :to_depth => -4)
node.path.from_depth(3).to_depth(4)
node.descendants(:from_depth => 2, :to_depth => 4)
node.subtree.from_depth(10).to_depth(12)

A subtree can be arranged into nested hashes for easy navigation after database retrieval.

The resulting format is a hash of hashes

{
  #<TreeNode id: 100018, name: "Stinky", ancestry: nil> => {
    #<TreeNode id: 100019, name: "Crunchy", ancestry: "100018"> => {
      #<TreeNode id: 100020, name: "Squeeky", ancestry: "100018/100019"> => {}
    },
    #<TreeNode id: 100021, name: "Squishy", ancestry: "100018"> => {}
  }
}

There are many ways to call arrange:

TreeNode.find_by(:name => 'Crunchy').subtree.arrange
TreeNode.find_by(:name => 'Crunchy').subtree.arrange(:order => :name)

If a hash of arrays is preferred, arrange_serializable can be used. The results work well with to_json.

TreeNode.arrange_serializable(:order => :name)
# use an active model serializer
TreeNode.arrange_serializable { |parent, children| MySerializer.new(parent, children: children) }
TreeNode.arrange_serializable do |parent, children|
  {
     my_id: parent.id,
     my_children: children
  }
end

The sort_by_ancestry class method: TreeNode.sort_by_ancestry(array_of_nodes) can be used to sort an array of nodes as if traversing in preorder. (Note that since materialized path trees do not support ordering within a rank, the order of siblings is dependant upon their original array order.)

The t.ancestry migration helper handles column type, collation, and indexes automatically. For most applications, t.ancestry is all you need.

For manual column setup, database-specific collation options, and migrating collation on existing columns, see Formats and Columns.

You can choose from the following ancestry formats:

• :materialized_path - legacy format (default for backwards compatibility)
• :materialized_path2 - recommended for new columns
• :materialized_path3 - like mp2 but root is "" instead of "/"
• :ltree - PostgreSQL ltree type with GiST indexing
• :array - PostgreSQL integer array. No string parsing, native array operations

If you are unsure, choose :materialized_path2. It allows a NOT NULL column and faster descendant queries (one less OR condition).

For PostgreSQL users who want native indexing, :ltree and :array avoid string parsing and collation issues entirely:

# ltree — GiST-indexed <@ operator
enable_extension 'ltree'
create_table :tree_nodes do |t|
  t.ancestry format: :ltree
end

# array — integer[], GIN-indexed @> containment
create_table :tree_nodes do |t|
  t.ancestry format: :array
end

For detailed format comparison, migration between formats, and database-specific column options, see Formats and Columns.

It should be relatively simple to migrating from a plugin that uses a parent_id column, (e.g.: awesome_nested_set, better_nested_set, acts_as_nested_set).

When running the installation steps, also remove the old gem from your Gemfile, and remove the old gem's macros from the model.

Then populate the ancestry column from rails console:

Model.build_ancestry_from_parent_ids!
# Model.rebuild_depth_cache!
Model.check_ancestry_integrity!

It is time to run your code. Most tree methods should work fine with ancestry and hopefully your tests only require a few minor tweaks to get up and running.

Once you are happy with how your app is running, remove the old parent_id column:

$ rails g migration remove_parent_id_from_[table]

class RemoveParentIdFromToTable < ActiveRecord::Migration[6.1]
  def change
    remove_column "table", "parent_id", type: :integer
  end
end

$ rake db:migrate

Ancestry derives parent_id, root_id, and depth by parsing the ancestry column. These options store those values in real database columns for use in queries, joins, and indexing.

Each option also accepts :virtual to use a database generated column instead of callbacks. Generated columns are defined in your migration and computed automatically by the database from the ancestry column — no rebuild step is needed. Requires Rails 7.2+ for SQLite, or Rails 7.0+ for PostgreSQL and MySQL.

The parent_id and root_id are already derived efficiently from the ancestry column, so most applications do not need parent: true or root: true. Use :virtual if you want these columns for database-level joins or foreign keys without callback overhead.

Note: root: :virtual is not supported on MySQL. MySQL generated columns cannot reference auto-increment columns, and root_id must equal id for root nodes. Use root: true (callback-maintained) on MySQL instead.

Note: root: true requires an extra UPDATE after creating root nodes, since the root_id of a root node is its own id, which is not available until after the record is inserted.

When parent: true is set, ancestry defines real ActiveRecord associations:

• belongs_to :parent — enables includes(:parent) and joins(:parent)
• has_many :children — enables includes(:children) and joins(:children)

When root: true is set:

• belongs_to :root — enables includes(:root) and joins(:root)

These are standard ActiveRecord associations backed by real database columns, so they support eager loading, preloading, and inverse caching:

class TreeNode < ActiveRecord::Base
  has_ancestry parent: true
end

# Eager load parents to avoid N+1
TreeNode.where(depth: 2).includes(:parent)

# Eager load children
roots = TreeNode.roots.includes(:children)
roots.each { |r| r.children } # no extra queries

# Join queries
TreeNode.joins(:parent).where(parents_tree_nodes: { name: "Root" })

Virtual columns (parent: :virtual, root: :virtual) also define associations. Since the database computes these columns automatically, they support eager loading and joins without callback overhead.

Cache columns can be added with t.ancestry when creating the table:

create_table :table do |t|
  t.ancestry cache_depth: true, parent: true
end

Or added to an existing table manually:

class AddDepthCacheToTable < ActiveRecord::Migration[7.0]
  def change
    change_table(:table) do |t|
      t.integer "ancestry_depth", default: 0
    end
  end
end

class [Model] < ActiveRecord::Base
  has_ancestry cache_depth: true
end

After adding a cached column to an existing table, populate it from the console or a script:

Model.rebuild_depth_cache!

You can use standard Rails validations on your depth cache column to restrict the depth of your tree. For example, to ensure no nodes are deeper than 2:

class TreeNode < ActiveRecord::Base
  has_ancestry cache_depth: true
  validates :ancestry_depth, numericality: { less_than_or_equal_to: 2 }
end

Ancestry will automatically validate not just the node itself, but also ensure that moving a subtree does not cause any of its descendants to exceed the maximum depth.

git clone git@github.com:stefankroes/ancestry.git
cd ancestry
cp test/database.example.yml test/database.yml
bundle
appraisal install
# all tests
appraisal rake test
# single test version (sqlite and rails 5.0)
appraisal sqlite3-ar-50 rake test

Other Ruby tree gems, each with different tradeoffs:

• acts_as_list — sortable lists with position column
• acts_as_tree — simple adjacency list (parent_id only)
• awesome_nested_set — nested set pattern (lft/rgt columns), fast subtree queries
• closure_tree — closure table pattern (separate hierarchy table), fast reads
• ltree_hierarchy - Postgres ltree implementation
• parentry - ltree and array implementation of ancestry.
• pg_ltree - Postgres ltree implementation

Question? Bug report? Faulty/incomplete documentation? Feature request? Please post an issue on 'http://github.com/stefankroes/ancestry/issues'. Make sure you have read the documentation and you have included tests and documentation with any pull request.

Copyright (c) 2016 Stefan Kroes, released under the MIT license