在 Rails 中處理樹狀結構有一些套件可用，本篇文章將比較下面幾種解決方案：

  1. ancestry
  2. awesome_nested_set
  3. closure_tree

情境

假設有個 model：Node，可以樹狀加入子節點。

功能

ancestry

設定

使用新的規則，config/initializers/ancestry.rb 加入

1
Ancestry.default_ancestry_format = :materialized_path2

需要使用樹狀結構的資料表要增加一些專用欄位

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

  # 必要欄位
  t.string :ancestry, collation: 'C', null: false

  # 擴充功能
  t.integer :ancestry_depth, default: 0
  t.integer :children_count, default: 0

  t.timestamps

  t.index :ancestry
end

然後在 Model 加入 has_ancestry

1
2
3
4
5
6
7
class Node < ApplicationRecord
  # 基本功能只需要
  # has_ancestry

  # 這邊使用擴充功能
  has_ancestry counter_cache: true, cache_depth: true
end

基本功能

列出常用的 instance methods

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

# 包含自己
node.siblings

列出常用的 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)

Ransack 搜索

利用 class methods 和 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

就可以

1
Node.ransack(children_of: 10)

但要搜索 roots 則要查詢 ancestry

1
Node.ransack(ancestry: '/')

awesome_nested_set

設定

需要使用樹狀結構的資料表要增加一些專用欄位

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

  # 必要欄位
  t.integer :parent_id, null: true, index: true
  t.integer :lft, null: false, index: true
  t.integer :rgt, null: false, index: true

  # 擴充功能
  t.integer :depth, null: false, default: 0
  t.integer :children_count, null: false, default: 0

  t.timestamps
end

然後在 Model 加入 acts_as_nested_set

1
2
3
4
5
6
7
class Node < ActiveRecord::Base
  # 基本功能只需要
  # acts_as_nested_set

  # 這邊使用擴充功能
  acts_as_nested_set counter_cache: :children_count
end

基本功能

列出常用的 instance methods

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

如果要包含自己，採用比較明確的命名

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

class methods 主要只有 roots 可以用

1
Node.roots

Ransack 搜索

可以直接利用 parent_id 搜索

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

然後

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

# roots
Node.ransack(parent_id: nil)

如果需要其他類型的搜索，可以自己定義 scope 來使用。

closure_tree

設定

和其他套件不同，設定方式相對複雜，要照著官方文件的步驟進行。最後會有一個額外的表來紀錄樹狀結構，以上面的 Node 為例，會生成另一個 node_hierarchies 的表。

基本功能

和 awesome_nested_set 差不多，這邊就不重複了。不過和前兩個套件比，資料庫沒有存 children_count 和 depth，是即時算的，有需要這方面的功能的話，可能不適合使用。

Ransack 搜索

和 awesome_nested_set 差不多，這邊就不重複了。

效能

接著來測試一下效能，這邊我建立了一個測試專案，跑出來的結果大概是這樣 (下面整理過排版)：

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

ancestry 大部分情況雖然效能較好，但是最常用的 children_of (依照 id 取得子節點) 的功能卻最慢。官方預設的實作方式慢了 awesome_nested_set 20 倍左右。這是因為當執行：

1
Model.children_of(1)

他實作方式是執行

1
Model.find(1).children

會執行兩次 query。ancestry 提供類似的 class methods 都是這樣。我另外實作了一次 query 的寫法：

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

效能提升 10 倍左右，但還是比較慢。

總結

做成表格進行比較

項目ancestryawesome_nested_setclosure_tree
功能完整OO△
使用方便OO△
效能OO△
Ransack 支援OOO

綜合比較 ancestry 和 awesome_nested_set 較爲優秀，ancestry 在儲存資料使用的空間較小 (但移動節點時速度較慢，要把子節點全部撈出來修改。)，awesome_nested_set 平均查詢效能較好。但我在測試的過程 ancestry 有遇到 bug 造成資料錯誤的情況。發生的情況是將 model record 載入到記憶體中，然後進行了多次的移動節點到不同位置。另外 awesome_nested_set 在 ransack 可以直接用 parent_id 查詢，也比較直接。所以我覺得 awesome_nested_set 可能會是比較好的選擇。