2021年12月11日

プログラミング

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

目次

  1. はじめに
  2. 背景
  3. RDBでツリー構造を表現する方法
  4. Railsで閉包テーブルモデルを使ってツリー構造を表現する方法
  5. まとめ

はじめに

この記事は新しい技術にチャレンジし続けるpalanのアドベントカレンダーDay11の記事です!
昨日は「Dockerで作成したRailsアプリケーションをHerokuにデプロイする」についての記事でした。

Dockerで作成したRailsアプリケーションをHerokuにデプロイする

今回はRailsでSlackのスレッドコメントのようなツリー構造アプリを作ってみた話です。

背景

現在、私はプラハチャレンジという外部サービスで学習をしています。その中で学んだことを社内でも共有したいと思い、今回記事を書くことにしました。

その課題の中で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_idNULLになります。
しかし、調べてみると上記は隣接リストモデルというアンチパターンであり下記の問題があります。

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

上記の例の場合、親コメント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の孫コメント1parent_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 Childparent_idnilになります。

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

tag.destroy will destroy a node and do something to its children, which is determined by the :dependent option passed to has_closure_tree.

まとめ

プラハチャレンジのメンターの方から実際の運用しているサービスで閉包テーブルモデルを使ってツリー構造を扱っている話を聞きました。特に問題が発生していないという話も聞けたので仕様にもよりますが、ツリー構造を表現する際は閉包テーブルモデルは有りだと思いました。

閉包テーブルモデルをRailsのclosure_treeで使って表現してみましたが、閉包テーブルモデルなのにparent_idを持つ隣接リストっぽくなりますが、複雑になりがちな検索や削除が簡単に行えるのはありがたいと思いました。

Rubyのお仕事に関するご相談

Bageleeの運営会社、palanではRubyに関するお仕事のご相談を無料で承っております。
zoomなどのオンラインミーティング、お電話、貴社への訪問、いずれも可能です。
ぜひお気軽にご相談ください。

無料相談フォームへ

0

0

AUTHOR

kainuma

Kainuma

サーバーサイドエンジニア Ruby on Railsを使った開発を行なっています

アプリでもっと便利に!気になる記事をチェック!

記事のお気に入り登録やランキングが表示される昨日に対応!毎日の情報収集や調べ物にもっと身近なメディアになりました。

簡単に自分で作れるWebAR

「palanAR」はオンラインで簡単に作れるWebAR作成ツールです。WebARとはアプリを使用せずに、Webサイト上でARを体験できる新しい技術です。

palanARへ
palanar

palanはWebARの開発を
行っています

弊社では企画からサービスの公開終了まで一緒に関わらせていただきます。 企画からシステム開発、3DCG、デザインまで一貫して承ります。

webar_waterpark

palanでは一緒に働く仲間を募集しています

正社員や業務委託、アルバイトやインターンなど雇用形態にこだわらず、
ベテランの方から業界未経験の方まで様々なかたのお力をお借りしたいと考えております。

話を聞いてみたい

運営メンバー

eishis

Eishi Saito 総務

SIerやスタートアップ、フリーランスを経て2016年11月にpalan(旧eishis)を設立。 マーケター・ディレクター・エンジニアなど何でも屋。 COBOLからReactまで色んなことやります。

sasakki デザイナー

アメリカの大学を卒業後、日本、シンガポールでデザイナーとして活動。

yamakawa

やまかわたかし デザイナー

フロントエンドデザイナー。デザインからHTML / CSS、JSの実装を担当しています。最近はReactやReact Nativeをよく触っています。

Sayaka Osanai デザイナー

Sketchだいすきプロダクトデザイナー。シンプルだけどちょっとかわいいデザインが得意。 好きな食べものは生ハムとお寿司とカレーです。

はらた

はらた エンジニア

サーバーサイドエンジニア Ruby on Railsを使った開発を行なっています

kobori

こぼり ともろう エンジニア

サーバーサイドエンジニア。SIerを経て2019年7月に入社。日々学習しながらRuby on Railsを使った開発を行っています。

sasai

ささい エンジニア

フロントエンドエンジニア WebGLとReactが強みと言えるように頑張ってます。

damien

Damien

WebAR/VRの企画・開発をやっています。森に住んでいます。

ゲスト bagelee

ゲスト bagelee

かっきー

かっきー

まりな

まりな

suzuki

suzuki

miyagi

ogawa

ogawa

雑食デザイナー。UI/UXデザインやコーディング、時々フロントエンドやってます。最近はARも。

いわもと

いわもと

デザイナーをしています。 好きな食べ物はラーメンです。

kobari

taishi kobari

フロントエンドの開発を主に担当してます。Blitz.js好きです。

shogokubota

kubota shogo

サーバーサイドエンジニア。Ruby on Railsを使った開発を行いつつ月500kmほど走っています!

nishi tomoya

aihara

aihara

グラフィックデザイナーから、フロントエンドエンジニアになりました。最近はWebAR/VRの開発や、Blender、Unityを触っています。モノづくりとワンコが好きです。

nagao

SIerを経てアプリのエンジニアに。xR業界に興味があり、unityを使って開発をしたりしています。

kainuma

Kainuma

サーバーサイドエンジニア Ruby on Railsを使った開発を行なっています

sugimoto

sugimoto

asama

ando

CONTACT PAGE TOP