rails でRDBにツリー構造を持たせるには

rails

参考

概要

railsでデータにツリー構造を持たせたい必要がでたので調べてみた。RDBでツリー構造を表現する方法は

  1. 隣接リストモデル
  2. 経路列挙モデル
  3. 入れ子集合モデル
  4. 閉包テーブルモデル

など、いくつかメジャーな方法があるようです。

今回は入れ子集合モデルを持つawesome_nested_setというgemを使いました。

入れ子集合モデルとは、あえてすごい簡略化して説明すると、ツリー構造の図を一筆書きで反時計回りに囲うようになぞった時に各要素の左端と右端に出会った順番に番号を振っていくことでツリー構造をテーブル上に表現する方法のことです。この説明は適当すぎですが、SQLで木と階層構造のデータを扱う（１）―― 入れ子集合モデルでわかりやすく説明されています。

model

class PostIt < ApplicationRecord
  acts_as_nested_set counter_cache: :children_count
end

DB

class ChangePostIts < ActiveRecord::Migration[5.2]
  def change
    change_table :post_its do |t|
      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

It is highly recommended that you add an index to the rgt column on your models. Every insertion requires finding the next rgt value to use and this can be slow for large tables without an index. It is probably best to index the other fields as well (parent_id, lft, depth). awesome_nested_setより

なぜindexをつけると速くなるのかはよくわからない。また今度調べてみたいと思う。

method

@root  = PostIt.new(memo: '親'）
@root.save
@child = @root.children.new(memo: '子')
@child.save

こんな感じで children メソッドというのが使えるようになる。saveの時に上記で説明した一筆書きを計算するためのたくさんのSQLが生成されるのがわかります。要素が増えるほど大量のSQLが必要になるのでこの計算の際にindexをつけておくことが推奨されているのだと思う。