Ancestry

Overview

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.

Features

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.

Features from Materialized Path

• 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)

Features from Ancestry gem Implementation

• 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").

Supported Rails versions

• 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

Installation

Follow these steps to apply Ancestry to any ActiveRecord model:

Add to Gemfile

# Gemfile

gem 'ancestry'

$ bundle install

Add ancestry column to your table

$ 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

Configure ancestry defaults

# config/initializers/ancestry.rb

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

Add ancestry to your model

# app/models/[model.rb]

class [Model] < ActiveRecord::Base
   has_ancestry
end

Your model is now a tree!

Organising records into 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'.

Tree Navigation

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 |root^{<a href="#fn1" id="ref1">1</a>} |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").

<sup id="fn1">1. [other root records are considered siblings]<a href="#ref1" title="Jump back to footnote 1.">↩</a></sup>

has_ancestry options

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    Regular expression that matches the format of the primary key:
                       '[0-9]+'            integer ids (default)
                       '[-A-Fa-f0-9]{36}'  UUIDs
: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