2021年12月11日

プログラミング

Railsでツリー構造アプリを作ってみた

その課題の中でRDBでSlackのスレッドコメントのようなツリー構造をどう表現するか？というような課題がありました。その課題でツリー構造を表現する様々な方法を学びましたが、Railsにおいてはどうしているのかが気になったので調べてまとめました。

RDBでツリー構造を表現する方法

私はツリー構造を下記のように表現しようと思いました。

Commentsテーブル

id	content	parent_id
1	親コメント1	NULL
2	子コメント1	1
3	子コメント2	1
4	孫コメント1	3
5	親コメント2	NULL

自分の親のコメントさえわかれば表現はできるだろうと思い、parent_idに自分の親のコメントのIDを保存します。親がいないコメントはparent_idがNULLになります。
しかし、調べてみると上記は隣接リストモデルというアンチパターンであり下記の問題があります。

ツリー全体、もしくはある要素のサブツリーが取得しづらい。

上記の例の場合、親コメント1に対するコメント（子コメント1, 2）は下記のSQLで取得できそうです。


SELECT
  c1.*,
  c2.*
FROM
  comments c1
LEFT OUTER JOIN comments c2
  ON c1.id = c2.parent_id
WHERE
  c1.id = 1;

では、子コメントに対するコメント（孫コメント1）も取得しようとするとどうなるでしょうか。


SELECT
  c1.*,
  c2.*,
  c3.*
FROM
  comments c1
LEFT OUTER JOIN comments c2
  ON c1.id = c2.parent_id
LEFT OUTER JOIN comments c3
  ON c2.id = c3.parent_id
WHERE
  c1.id = 1;

階層が1段下がる毎に結合しなければ取得できません。
コメントの階層の深さは動的に変わるので、あるコメントに対するコメントを全て取得することができません。（再帰クエリが使用できれば取得は可能らしい）

親子関係があるレコードを削除した際に整合性を取りづらい。

上記の例の場合にID3の子コメント2を削除するとどうなるでしょうか？
ID3の子コメント2を削除すると孫コメント1の親が存在しないことになります。

id	content	parent_id
1	親コメント1	NULL
2	子コメント1	1
4	孫コメント1	3 ※親が存在しない状態になる
5	親コメント2	NULL

そこで子コメント2を削除する場合は下記の手順になります。
まずは削除したいコメントの子要素の親を更新します。今回の場合はID4の孫コメント1のparent_idを1に更新します。

id	content	parent_id
1	親コメント1	NULL
2	子コメント1	1
3	子コメント2	1
4	孫コメント1	1 ※親を1に変更
5	親コメント2	NULL

そして削除するコメントとの親子関係のデータが無くなってから、削除したいデータを削除します。

id	content	parent_id
1	親コメント1	NULL
2	子コメント1	1
4	孫コメント1	1
5	親コメント2	NULL

この設計だと整合性を取るために削除する時に更新が必要になります。（論理削除なら更新のみでも可能）

RDBでツリー構造を表現する方法

RDBでツリー構造を表現する方法を調べてみると下記の4つがありました。

設計	子へのクエリ実行	ツリーへのクエリ実行	挿入	削除	参照整合性維持
隣接リスト	簡単	難しい	難しい	簡単	可能
経路列挙モデル	簡単	簡単	簡単	簡単	不可
入れ子集合モデル	難しい	難しい	難しい	難しい	不可
閉包テーブルモデル	簡単	簡単	簡単	簡単	可能

SQLアンチパターン

そこで今回はすべての項目が簡単・可能な閉包テーブルモデルを使用してツリー構造を表現してみました。

閉包テーブルモデル

閉包テーブルモデルとは別テーブルにてコメント同士の関係性を定義するためのテーブルを追加して管理するモデルです。
直近の親子関係のみではなく離れたコメントの親子関係と自身を参照するパスも含めます。

Commentsテーブル

id	content
1	親コメント1
2	子コメント1（親コメント1に対するコメント）
3	子コメント2（親コメント1に対するコメント）
4	孫コメント1（子コメント2に対するコメント）
5	親コメント2

TreePathsテーブル

ancestor_id	descendant_id
1	1
1	2
1	3
1	4
2	2
3	3
3	4
4	4
5	5

検索

親コメント1に対する全てのコメントは下記で取得できます。
コメントの深度がどれだけ深くなっても全ての祖先のIDがわかるので全てを一括で取得できます。


SELECT
  c.*
FROM
  Comments c
INNER JOIN TreePaths t
  ON c.id = t.descendant_id
WHERE
  t.ancestor_id = 1;

削除

ID3の子コメント2を削除する場合は3は中間の要素なので、自身を子孫にもつレコードと自身を祖先に持つレコードを削除する。


DELETE FROM
  TreePaths
WHERE
  descendant_id IN 3;

DELETE FROM
  TreePaths
WHERE
  ancestor_id IN 3;

Commentsテーブル

id	content
1	親コメント1
2	子コメント1（親コメント1に対するコメント）
4	孫コメント1（子コメント2に対するコメント）
5	親コメント2

TreePathsテーブル

ancestor_id	descendant_id
1	1
1	2
1	4
2	2
4	4
5	5

デメリット

直近の親や子に絞って取得するのは難しくなります。
解決策として、パスの長さを保存するというのがあります。しかし、ツリーの更新のたびに長さも一緒に更新しないといけなくなります。

データ量が増える。直近の親子関係だけではなく、全ての親子関係と自分自身も保存する必要があるのでどうしても大量のレコード数になります。

Railsで閉包テーブルモデルを使ってツリー構造を表現する方法

gem closure_tree

Railsで閉包テーブルモデルを表現する方法を調べてみるとclosure_treeというgemがあったので使用してみました。

導入

環境

Ruby: 2.6.6
Rails: 6.0.3
Closure Tree: 7.4.0

Gemfileにgem 'closure_tree'を追加して、bundle installを実行します。

次にCommentモデルを作成します。コメントにparent_idを持たせます。閉包テーブルモデルはparent_idを持つ必要はないのですが、検索速度を上げるためと思われます。NULLが入る可能性があるのでNOT_NULL制約はつけずにrails db:migrateを実行します。

$  rails g model Comment content:string parent_id:integer


class CreateComments < ActiveRecord::Migration[6.0]
  def change
    create_table :comments do |t|
      t.string :content
      t.integer :parent_id
    end
  end
end

Commentモデルにhas_closure_treeを追加します。


class Comment < ApplicationRecord
  has_closure_tree
end

次に関係性のテーブルを作成します。下記のコマンドで作成できます。

$ rails g closure_tree:migration comment

上記のコマンドを実行すると下記のマイグレーションファイルが作成されます。


class CreateCommentHierarchies < ActiveRecord::Migration[6.0]
  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

上記のファイルが作成されていることが確認できたら、rails db:migrateを実行します。これで導入は完了です。

使用方法

作成

親コメントの作成

parent = Comment.create(content: 'Parent')
=> #<comment:0x0000aaaaeda33e80 id:="" 1,="" content:="" "parent",="" parent_id:="" nil="">

子コメントの作成

child1 = parent.children.create(content: 'Farst Child')
=> #<comment:0x0000aaaaedc0afb0 id:="" 2,="" content:="" "farst="" child",="" parent_id:="" 1="">

子コメントの追加①

child2 = Comment.new(content: 'Second Child')
=> #<comment:0x0000ffffb0fb1c50 id:="" nil,="" content:="" "second="" child",="" parent_id:="" nil=""></comment:0x0000ffffb0fb1c50>

parent.children << child2
=> [#<comment:0x0000aaaaedc0afb0 id:="" 2,="" content:="" "farst="" child",="" parent_id:="" 1="">, #<comment:0x0000ffffb0fb1c50 id:="" 3,="" content:="" "second="" child",="" parent_id:="" 1="">]

子コメントの追加②add_childメソッドを使用

child3 = Comment.new(content: 'Third Child')
=> #<comment:0x0000ffffb10e7890 id:="" nil,="" content:="" "third="" child",="" parent_id:="" nil=""></comment:0x0000ffffb10e7890>

parent.add_child child3
=> #<comment:0x0000ffffb10e7890 id:="" 4,="" content:="" "third="" child",="" parent_id:="" 1="">

親を指定して子コメントを作成

Comment.create(content: 'Fourth Child', parent: parent)
=> #<comment:0x0000ffffb21d4040 id:="" 5,="" content:="" "fourth="" child",="" parent_id:="" 1="">

検索

自分自身と子孫を全てを取得

parent.self_and_descendants.collect(&:content)
=> ["Parent", "Farst Child", "Second Child", "Third Child"]

親子関係の取得

# "Grand parent"と"Grand Child"を追加してあります。
grand_child.ancestry_path(:content)
=> ["Grand Parent", "Parent", "Farst Child", "Grand Child"]

全てのツリー構造の取得

Comment.hash_tree
=> {#<comment:0x0000ffffb2462dc0 id:="" 6,="" content:="" "grand="" parent",="" parent_id:="" nil="">=>
{#<comment:0x0000ffffb2462cf8 id:="" 1,="" content:="" "parent",="" parent_id:="" 6="">=>
{#<comment:0x0000ffffb2462be0 id:="" 5,="" content:="" "fourth="" child",="" parent_id:="" 1="">=>{},
#<comment:0x0000ffffb2462b18 id:="" 2,="" content:="" "farst="" child",="" parent_id:="" 1="">=>{#<comment:0x0000ffffb24628c0 id:="" 7,="" content:="" "grand="" child",="" parent_id:="" 2="">=>{}},
#<comment:0x0000ffffb2462a50 id:="" 3,="" content:="" "second="" child",="" parent_id:="" 1="">=>{},
#<comment:0x0000ffffb2462988 id:="" 4,="" content:="" "third="" child",="" parent_id:="" 1="">=>{}}}}

削除

中間要素の削除。中間要素の削除を行うと、関連する要素も更新してくれます。

Comment.find(2).destroy # content: "Farst Child",
Comment Load (2.3ms)  SELECT `comments`.* FROM `comments` WHERE `comments`.`id` = 2 LIMIT 1
(1.4ms)  SAVEPOINT active_record_1
(1.0ms)  SELECT version()
(1.7ms)  SELECT GET_LOCK('251cf318163722b0cd9a662a58099ba93', 0) AS t31377cd68f8b8d64468b1691150bc5a7
(0.7ms)  SELECT version()
(22.2ms)  DELETE FROM `comment_hierarchies` WHERE descendant_id IN ( SELECT DISTINCT descendant_id FROM (SELECT descendant_id FROM `comment_hierarchies` WHERE ancestor_id = 2 OR descendant_id = 2 ) AS x )
Comment Load (2.0ms)  SELECT `comments`.* FROM `comments` WHERE `comments`.`id` = 2 LIMIT 1
Comment Load (1.2ms)  SELECT `comments`.* FROM `comments` WHERE `comments`.`parent_id` = 2 ORDER BY `comments`.`id` ASC LIMIT 1000
(0.7ms)  SELECT version()
(0.9ms)  SELECT version()
(2.8ms)  DELETE FROM `comment_hierarchies` WHERE descendant_id IN ( SELECT DISTINCT descendant_id FROM (SELECT descendant_id FROM `comment_hierarchies` WHERE ancestor_id = 7 OR descendant_id = 7 ) AS x )
CommentHierarchy Create (0.9ms)  INSERT INTO `comment_hierarchies` (`ancestor_id`, `descendant_id`, `generations`) VALUES (7, 7, 0)
(1.6ms)  INSERT INTO `comment_hierarchies` (ancestor_id, descendant_id, generations) SELECT x.ancestor_id, 7, x.generations + 1 FROM `comment_hierarchies` x WHERE x.descendant_id = 2
Comment Load (2.2ms)  SELECT `comments`.* FROM `comments` WHERE `comments`.`parent_id` = 7 ORDER BY `comments`.`id` ASC LIMIT 1000
(11.2ms)  SELECT RELEASE_LOCK('251cf318163722b0cd9a662a58099ba93') AS t30dbc607f000d6fe9a9cdcae1b94058a
Comment Update All (12.8ms)  UPDATE `comments` SET `comments`.`parent_id` = NULL WHERE `comments`.`parent_id` = 2
Comment Destroy (0.9ms)  DELETE FROM `comments` WHERE `comments`.`id` = 2
(0.4ms)  RELEASE SAVEPOINT active_record_1
=&gt; #<comment:0x0000ffffb2e1ac28 id:="" 2,="" content:="" "farst="" child",="" parent_id:="" 1="">

Comment.hash_tree
=> {#<comment:0x0000ffffb2eae798 id:="" 6,="" content:="" "grandparent",="" parent_id:="" nil="">=>
{#<comment:0x0000ffffb2eae0e0 id:="" 1,="" content:="" "parent",="" parent_id:="" 6="">=>
{#<comment:0x0000ffffb2eadfa0 id:="" 3,="" content:="" "second="" child",="" parent_id:="" 1="">=>{},
#<comment:0x0000ffffb2eadcf8 id:="" 4,="" content:="" "third="" child",="" parent_id:="" 1="">=>{},
#<comment:0x0000ffffb2eadc30 id:="" 5,="" content:="" "fourth="" child",="" parent_id:="" 1="">=>{}}},
#<comment:0x0000ffffb2eae4f0 id:="" 7,="" content:="" "grand="" child",="" parent_id:="" nil="">=>{}}

通常の削除を行うと、削除された要素の子要素の親はいない状態になります。今回の例でいうと、Farst Childを親に持っていた、Grand Childのparent_idはnilになります。

削除時にもオプションを渡せるようで親を変更したり、子要素も全て削除などもできそうです。