There are several gems available for handling tree structures in Rails. This article will compare the following solutions:

  1. ancestry
  2. awesome_nested_set
  3. closure_tree

Scenario

Suppose there is a model called Node that can have child nodes in a tree structure.

Features

ancestry

Setup

Using the new rules, add the following to config/initializers/ancestry.rb

1
Ancestry.default_ancestry_format = :materialized_path2

Tables that need to support a tree structure should include some dedicated columns.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
create_table :nodes do |t|
  t.string :name, null: false

  # required
  t.string :ancestry, collation: 'C', null: false

  # optional extensions
  t.integer :ancestry_depth, default: 0
  t.integer :children_count, default: 0

  t.timestamps

  t.index :ancestry
end

Then, add has_ancestry to the model.

1
2
3
4
5
6
7
class Node < ApplicationRecord
  # basic functionality
  # has_ancestry

  # extensions
  has_ancestry counter_cache: true, cache_depth: true
end

Basic Usage

List the commonly used instance methods

1
2
3
4
5
6
node.children
node.ancestors
node.descendants

# including self
node.siblings

List the commonly used class methods

1
2
3
4
5
Node.roots
Node.children_of(id_or_node)
Node.ancestor_of(id_or_node)
Node.descendants_of(id_or_node)
Node.siblings_of(id_or_node)

Use class methods in combination with Ransack.

1
2
3
4
5
6
7
def self.ransackable_attributes(_auth_object = nil)
  %w[ancestry]
end

def self.ransackable_scopes(_auth_object = nil)
  %w[children_of]
end

and then

1
Node.ransack(children_of: 10)

However, to search for roots, you need to query the ancestry column.

1
Node.ransack(ancestry: '/')

awesome_nested_set

Setup

Tables that need to support a tree structure should include some dedicated columns.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
create_table :nodes do |t|
  t.string :name

  # Required
  t.integer :parent_id, null: true, index: true
  t.integer :lft, null: false, index: true
  t.integer :rgt, null: false, index: true

  # optional extensions
  t.integer :depth, null: false, default: 0
  t.integer :children_count, null: false, default: 0

  t.timestamps
end

Then, add acts_as_nested_set to the model.

1
2
3
4
5
6
7
class Node < ActiveRecord::Base
  # Basic functionality
  # acts_as_nested_set

  # extensions
  acts_as_nested_set counter_cache: :children_count
end

Basic Usage

List the commonly used instance methods

1
2
3
4
node.children
node.ancestors
node.descendants
node.siblings

If you want to include self, use a more explicit naming convention.

1
2
3
node.self_and_ancestors
node.self_and_siblings
node.self_and_descendants

List the commonly used class methods

1
Node.roots

Ransack Search

You can directly search using parent_id.

1
2
3
def self.ransackable_attributes(_auth_object = nil)
  %w[parent_id]
end

and then

1
2
3
4
Node.ransack(parent_id: 10)

# roots
Node.ransack(parent_id: nil)

If you need other types of searches, you can define your own scopes to use.

closure_tree

Setup

Unlike other gems, the setup process is relatively complex and should follow the official documentation step by step. In the end, an additional table will be created to record the tree structure. For example, with the Node model above, another table called node_hierarchies will be generated.

Basic Usage

It’s similar to awesome_nested_set, so I won’t repeat it here. However, compared to the first two gems, this one does not store children_count and depth in the database. They are calculated in real time. If you need those features, this gem might not be suitable.

Ransack Search

It’s similar to awesome_nested_set, so I won’t repeat it here.

Benchmark

Next, let’s test the performance. I created a benchmark project, and the results are approximately as follows (reorganized and formatted):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
---------------------------------
benchmark:create
            ancestry      0.114 (± 0.0%) i/s     (8.79 s/i) -      1.000 in   8.786560s
  awesome_nested_set      0.015 (± 0.0%) i/s    (65.36 s/i) -      1.000 in  65.363601s
        closure_tree      0.051 (± 0.0%) i/s    (19.59 s/i) -      1.000 in  19.585828s
---------------------------------
benchmark:update
            ancestry      0.046 (± 0.0%) i/s    (21.83 s/i) -      1.000 in  21.831982s
  awesome_nested_set      1.203 (± 0.0%) i/s  (831.21 ms/i) -      6.000 in   5.062957s
        closure_tree      0.016 (± 0.0%) i/s    (60.76 s/i) -      1.000 in  60.756249s
---------------------------------
benchmark:children_of
            ancestry      0.522 (± 0.0%) i/s     (1.92 s/i) -      3.000 in   5.757987s
   ancestry (faster)      4.291 (± 0.0%) i/s  (233.02 ms/i) -     22.000 in   5.199553s
  awesome_nested_set      9.551 (±10.5%) i/s  (104.70 ms/i) -     48.000 in   5.047880s
        closure_tree     10.207 (± 9.8%) i/s   (97.97 ms/i) -     51.000 in   5.046494s
---------------------------------
benchmark:children
            ancestry     10.863 (± 9.2%) i/s   (92.06 ms/i) -     53.000 in   5.008058s
  awesome_nested_set      7.913 (±12.6%) i/s  (126.37 ms/i) -     39.000 in   5.035606s
        closure_tree      9.631 (±10.4%) i/s  (103.83 ms/i) -     48.000 in   5.032850s
---------------------------------
benchmark:descendants
            ancestry      6.721 (±14.9%) i/s  (148.79 ms/i) -     33.000 in   5.057038s
  awesome_nested_set      5.415 (± 0.0%) i/s  (184.69 ms/i) -     28.000 in   5.176816s
        closure_tree      1.003 (± 0.0%) i/s  (997.09 ms/i) -      5.000 in   5.013623s
---------------------------------
benchmark:siblings
            ancestry     12.053 (± 8.3%) i/s   (82.97 ms/i) -     61.000 in   5.083198s
  awesome_nested_set      7.683 (± 0.0%) i/s  (130.16 ms/i) -     39.000 in   5.093565s
        closure_tree      9.630 (±10.4%) i/s  (103.84 ms/i) -     48.000 in   5.006542s
---------------------------------
benchmark:ancestors
            ancestry      6.866 (± 0.0%) i/s  (145.64 ms/i) -     35.000 in   5.107056s
  awesome_nested_set      5.957 (± 0.0%) i/s  (167.88 ms/i) -     30.000 in   5.043287s
        closure_tree      0.895 (± 0.0%) i/s     (1.12 s/i) -      5.000 in   5.593123s
---------------------------------

Although ancestry generally performs better in most cases, its most commonly used feature, children_of (retrieving child nodes by id), is actually the slowest. The official default implementation is about 20 times slower than awesome_nested_set. This is because when executing:

1
Model.children_of(1)

Its implementation is:

1
Model.find(1).children

It executes two queries. The similar class methods work this way. I implemented a single-query version as follows:

1
2
3
def self.children_of_by_id(id)
  where(ancestry: Node.where(id: id).select(sanitize_sql_array([ "CONCAT(ancestry, ?)", "#{id}/" ])))
end

The performance improved by about 10 times, but it is still relatively slow.

Conclusions

We compare in a table:

Itemancestryawesome_nested_setclosure_tree
FeaturesOO△
Easy to useOO△
PerformanceOO△
Ransack SupportOOO

A comprehensive comparison shows that both ancestry and awesome_nested_set have their strengths. ancestry uses less storage space for data (but node moves are slower since all child nodes need to be loaded and updated). awesome_nested_set generally offers better query performance. However, during my testing, I encountered a bug with ancestry that caused data corruption. This happened when model records were loaded into memory and nodes were moved multiple times to different positions.

Additionally, awesome_nested_set works more seamlessly with Ransack, allowing direct queries using parent_id, which is more straightforward. Therefore, I think awesome_nested_set might be the better choice.