Railsで木構造を扱うには

はじめに

「SQLアンチパターン」という本をご存知でしょうか。有名な本なので、エンジニアのほとんどは一度は耳or目にしているかと思いますが、その名の通りSQLのアンチパターンをたくさん紹介している本です。
その本の「ナイーブツリー（素朴な木）」という章では、木構造を隣接リストで実装することがアンチパターンとして紹介されています。またその解決として、いくつかの代替ツリーモデルが紹介されています。SQLの一般論としては理解できたのですが、特にRuby on Railsにおいてはどうしているのかが気になったので調べてまとめました。

環境

• Ruby 2.5.0
• Rails 5.1.5
• SQLite3

扱うもの

本に倣い、スレッド形式のコメントを実装します。
あくまで、主題は木構造なので、木構造を表すためのカラム以外は、主キーであるidと内容のcontentだけとします。
また、シンプルにcontentはstring型にしておきます。
ここに、木構造を表すためのカラムを足していって木構造を実現していきます。

目次

• 隣接リスト
• 経路列挙モデル
• 入れ子集合モデル
• 閉包テーブルモデル

隣接リスト

まずは、アンチパターンとされる隣接リストから。
acts_as_treeというgemがあります。もともとはrails/acts_as_treeであったようですが、何かの事情によって変わったようです。

migrationとモデル定義

class CreateComments < ActiveRecord::Migration[5.1]
  def change
    create_table :comments do |t|
      t.string :content, null: false
      t.integer :parent_id, index: true
    end
  end
end

class Comment < ApplicationRecord
  acts_as_tree

  def inspect
    "[#{content}]" # 出力をシンプルにするため
  end
end

コード例

root = Comment.create(content: '隣接リスト最高！')
root.children.create(content: 'シンプルでいいですよね')
child = root.children.create(content: 'アンチパターンですよ、経路列挙モデル使いましょう')
child.children.create(content: '入れ子集合モデルの方が良いですよ')
Comment.create(content: 'こんにちは')

と普通のActiveRecordと同じようにデータを作っていけます。

id	content	parent_id
1	隣接リスト最高！	NULL
2	シンプルでいいですよね	1
3	アンチパターンですよ、経路列挙モデル使いましょう	1
4	入れ子集合モデルの方が良いですよ	3
5	こんにちは	NULL

また以下のような、根ノード（親を持たないノード）や葉ノード（子を持たないノード）や世代をキーとしたmapを取得するクラスメソッドが使えるようになります。

Comment.roots
# => [[隣接リスト最高！],[こんにちは]]
Comment.root # Comment.roots.first と同じ
# => [隣接リスト最高！]
Comment.leaves
# => [[シンプルでいいですよね],[入れ子集合モデルの方が良いですよ], [こんにちは。]]
Comment.generations
# => {0=>[[隣接リスト最高！],[こんにちは]],
# 1=>[[シンプルでいいですよね],[アンチパターンですよ、経路列挙モデル使いましょう]],
# 2=>[[入れ子集合モデルの方が良いですよ]]}

またインスタンスメソッドでいえば、#parentで親ノード、#ancestorsで先祖ノード、#childrenで子ノード、#descendantsで子孫ノード、#siblingsで兄弟ノードが取得できます。
他にも、#root?や#leaf?で根や葉であるかが確かめられたり、木構造を扱うのに必要そうなメソッドは一通り揃っているように見えます。（詳細: acts_as_tree.rb）

さらに、クラス定義で、extend ActsAsTree::TreeViewをしておくと、以下のようなコードで、

Comment.tree_view(:content)

次のように木構造を可視化できます。

root
 |_ 隣接リスト最高！
 |    |_ シンプルでいいですよね
 |    |_ アンチパターンですよ、経路列挙モデル使いましょう
 |        |_ 入れ子集合モデルの方が良いですよ
 |_ こんにちは

これでも十分便利なようですが、本にも書かれているように、再帰クエリが使えない場合にクエリが非効率になるという欠点があり、より効率的なものとしていくつかの代替ツリーモデルが考案されてきました。ということで、それらを見ていきます。

経路列挙モデル

まずは経路列挙モデル。根ノードからのpathを持つことで、データ構造を表します。
（正直1章でアンチパターンとして挙げられている、ジェイウォーク（配列をカンマ区切りの文字列で持つようなこと）に見えます。）

これを扱うためのgemとして、ancestryというものがあります。

migrationとモデル定義

class CreateComments < ActiveRecord::Migration[5.1]
  def change
    create_table :comments do |t|
      t.string :content, null: false
      t.string :ancestry, index: true
    end
  end
end

class Comment < ApplicationRecord
  has_ancestry

  def inspect
    "[#{content}]"
  end
end

コード例

root = Comment.create(content: '隣接リスト最高！')
root.children.create(content: 'シンプルでいいですよね')
# Comment.create(content: 'シンプルでいいですよね', parent: root) でも良い
child = root.children.create(content: 'アンチパターンですよ、経路列挙モデル使いましょう')
grandchild = child.children.create(content: '入れ子集合モデルの方が良いですよ')
hello = Comment.create(content: 'こんにちは')

id	content	ancestry
1	隣接リスト最高！	NULL
2	シンプルでいいですよね	1
3	アンチパターンですよ、経路列挙モデル使いましょう	1
4	入れ子集合モデルの方が良いですよ	1/3
5	こんにちは	NULL

例えば、root.descendantsを実行すると

SELECT "comments".* FROM "comments" 
  WHERE ("comments"."ancestry" LIKE '1/%' OR 
         "comments"."ancestry" = '1')

というSQLが発行され、

=> [[シンプルでいいですよね],[アンチパターンですよ、経路列挙モデル使いましょう],[入れ子集合モデルの方が良いですよ]]

と子孫ノードが返ってきます。

また、grandchild.ancestorsを実行すると、

SELECT "comments".* FROM "comments" 
  WHERE "comments"."id" IN (1, 3) 
  ORDER BY coalesce("comments"."ancestry", '')

というSQLが発行され、

=> [[隣接リスト最高！],[アンチパターンですよ、経路列挙モデル使いましょう]]

と先祖ノードが帰ってきます。コードを見ると

ancestry.split('/').map(&:to_i)

とRubyで計算してから、SQLを組み立てているようです。

また、ノードの付け替えもちゃんとでき、

root.update(parent: hello)

とrootのparentをhelloにすると、

id	content	ancestry
1	隣接リスト最高！	5
2	シンプルでいいですよね	5/1
3	アンチパターンですよ、経路列挙モデル使いましょう	5/1
4	入れ子集合モデルの方が良いですよ	5/1/3
5	こんにちは	NULL

のように子孫ノードにも然るべき変更がなされます。
経路列挙モデルでは、子孫ノードのレコードも更新しなくてはならないため、ロジックが複雑になるという欠点がありますが、そこはうまくgemが隠蔽してくれています。（更新コストが大きいというのは依然としてありますが。）

入れ子集合モデル

入れ子集合モデルでは、木を扱う代わりに、下のような集合を扱います。
（区間と言った方がわかりやすいかもしれませんが、入れ子区間モデルは、left, rightが実数であるような、同様のモデルを指します。）

id	content	left	right
1	隣接リスト最高！	1	8
2	シンプルでいいですよね	2	3
3	アンチパターンですよ、経路列挙モデル使いましょう	4	7
4	入れ子集合モデルの方が良いですよ	5	6
5	こんにちは	9	10

ノードnaがノードnbの子孫ノードであるとき、

nb.left < na.left && na.right < nb.right

が常に成り立つようになっています。
また、葉ノードleafに関しては、

leaf.right - leaf.left == 1

が成り立ちます。

このような入れ子集合モデルを扱うようなgemとして、awesome_nested_setがあります。
migrationファイルは以下のように書きます。デフォルトではleftはlft、rightはrgtというカラム名になっています。入れ子集合モデルにparent_idは、不要なのですが、探索速度を上げるために導入しているようです。

migrationとモデル定義

class CreateComments < ActiveRecord::Migration[5.1]
  def change
    create_table :comments do |t|
      t.string :content, null: false
      t.integer :parent_id, 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
    end
  end
end

class Comment < ApplicationRecord
  acts_as_nested_set counter_cache: :children_count
end

コード例

root = Comment.create(content: '隣接リスト最高！')
root.children.create(content: 'シンプルでいいですよね')
child = root.children.create(content: 'アンチパターンですよ、経路列挙モデル使いましょう')
child.children.create(content: '入れ子集合モデルの方が良いですよ')
hello = Comment.create(content: 'こんにちは')

id	content	parent_id	lft	rgt	depth	children_count
1	隣接リスト最高！	NULL	1	8	0	2
2	シンプルでいいですよね	1	2	3	1	0
3	アンチパターンですよ、経路列挙モデル使いましょう	1	4	7	1	1
4	入れ子集合モデルの方が良いですよ	3	5	6	2	0
5	こんにちは	NULL	9	10	0	0

こちらも、ノードの付け替えはでき、

root.move_to_child_of(hello)

とすると、（更新箇所を太文字で表しています。）

id	content	parent_id	lft	rgt	depth	children_count
1	隣接リスト最高！	4	2	9	1	2
2	シンプルでいいですよね	1	3	4	2	0
3	アンチパターンですよ、経路列挙モデル使いましょう	1	5	8	2	1
4	入れ子集合モデルの方が良いですよ	3	6	7	3	0
5	こんにちは	NULL	1	10	0	1

と、うまい具合に更新されています。

閉包テーブルモデル

これは、全ての親子関係を別テーブルで持つようなモデルです。
このモデルを扱うgemとして、closure_treeというものがあります。

migrationとモデル定義

class CreateComments < ActiveRecord::Migration[5.1]
  def change
    create_table :comments do |t|
      t.string :content, null: false
      t.integer :parent_id, index: true
    end
  end
end

class Comment < ApplicationRecord
  has_closure_tree

  def inspect
    "[#{content}]"
  end
end

閉包テーブルモデルもparent_idを持つ必要はないのですが、awesome_nested_setと同様に探索速度を上げるためと思われます。
commentsテーブルを作った上で、

rails g closure_tree:migration comment

とすると、

class CreateCommentHierarchies < ActiveRecord::Migration
  def change
    create_table :comment_hierarchies, id: false do |t|
      t.integer :ancestor_id, null: false
      t.integer :descendant_id, null: false
      t.integer :generations, null: false
    end

    add_index :comment_hierarchies, [:ancestor_id, :descendant_id, :generations],
      unique: true,
      name: "comment_anc_desc_idx"

    add_index :comment_hierarchies, [:descendant_id],
      name: "comment_desc_idx"
  end
end

というファイルができるので、ActiveRecord::MigrationをActiveRecord::Migration[5.1]に書き換えて、rake db:migrateします。

コード例

root = Comment.create(content: '隣接リスト最高！')
root.children.create(content: 'シンプルでいいですよね')
child = root.children.create(content: 'アンチパターンですよ、経路列挙モデル使いましょう')
child.children.create(content: '入れ子集合モデルの方が良いですよ')
hello = Comment.create(content: 'こんにちは')

id	content	parent_id
1	隣接リスト最高！	NULL
2	シンプルでいいですよね	1
3	アンチパターンですよ、経路列挙モデル使いましょう	1
4	入れ子集合モデルの方が良いですよ	3
5	こんにちは	NULL

ancestor_id	descendant_id	generations
1	1	0
2	2	0
1	2	1
3	3	0
1	3	1
4	4	0
3	4	1
1	4	2
5	5	0

ancestor_idが親ノードのid、descendant_idは子ノードのid、generationsが世代差となっています。

Comment.hash_tree
# => {[隣接リスト最高！]=>{[シンプルでいいですよね]=>{}, [アンチパターンですよ、経路列挙モデル使いましょう]=>{[入れ子集合モデルの方が良いですよ]=>{}}},[こんにちは]=>{}}

ノードの付け替えも可能で、helloの子ノードにrootを加えるのは以下のようにします。

hello.add_child(root)
Comment.hash_tree
# => {[こんにちは]=>{[隣接リスト最高！]=>{[シンプルでいいですよね]=>{}, [アンチパターンですよ、経路列挙モデル使いましょう]=>{[入れ子集合モデルの方が良いですよ]=>{}}}}}

おわりに

以上アンチパターンとされていた隣接リストと、いくつかの代替ツリーモデルを見ていきました。
まだ、実際にこうしたものを扱った経験はないので、どれがベストとは言えませんが、そちらは各々ご判断いただければと思います。
また、横断的に4つのgemを扱ったため、便利なメソッド等紹介しきれていない箇所がいくつもありますので、気になったgemがあれば、ご自身でより詳しく調べていただければと思います。

関連記事

Rubyのメソッド名でしりとりやってみた