0. はじめに

最近、動画投稿サイトYouTubeの盛り上がりを受け（いまさら）、YouTubeまとめサイトSuperYouTuber.COM（すでに閉鎖済みです）というサイトを作っていました。
その中で、カテゴリを実装する際にツリー構造（木構造）を用いた実装を行いました。
リレーショナルデータベースにおいては、ツリー構造の実装は例えば以下のようなモデルが考案されています。
- 隣接リストモデル
- 経路列挙モデル
- 入れ子集合モデル
- 閉包テーブルモデル
それぞれ、メリット・デメリットがあるのですが（後述）、個人的には、実装がシンプルな隣接リストモデルが好みです。
SQLアンチパターンでは、今回実装する隣接リストモデルについては、2章 Naive Trees(素朴な木)にアンチパターンとして紹介されています。
しかし、参考にあげたRDBでツリー構造でも、「再帰クエリが使えるなら即採用」とあり、PostgreSQLを用いればWITH RECURSIVEを用いれば再帰クエリは問題ないですし、そもそもRailsであればアプリケーションレイヤーで再帰処理を記述できるので、問題がないように思います。
Railsでは、ツリー構造を実装したgemとしてancestryというgemが有名ですが、このgemは系列列挙モデルを採用しており、個人的には、ancestryカラムに1/2/3/と記述されており、次の観点から抵抗があります。いずれも、系列列挙モデルのデメリットとしてよく挙げられることです。
- ジェイウォーク（信号無視）になってしまっている
- 節点の親を変えるだけなのに節点の子のレコードも更新される
- ancestry経由で更新しているうちは問題ないと思うが、DBの値を直接書き換えたときなどに整合性が取りにくい
そこで、こういう感じに書けば良いというプラクティスをまとめておけば、わざわざ今後もメンテナンスされ続けられるかわからないgemを使うよりも、柔軟に実装できて長い目で見て良いのではなかと思い、実際に隣接リストモデルでツリー構造を実装してみました。
本記事の流れとしては、隣接リストモデルに置ける問題点を述べ、次に、その問題点をどう解決したかについて具体的な実装例を示しながら説明します。最後に、今回の実装でのancestrygemとの対応について表形式で示します。
再帰処理に関してはまだまだ勉強中の身ですので、間違いや改善点がある場合は優しくご教授いただけますと幸いです。
改めて、隣接リストモデルのテーブルの例はこのような感じです。各カテゴリが親カテゴリのidを持つ形になります。

id	name	parent_id
1	科目	0
2	数学	1
3	物理	1
4	力学	3
5	波動	3
6	熱力学	3
7	微分	2
8	積分	2

1. 隣接リストモデルの問題点

1-1. 子カテゴリをもつカテゴリを安易に削除できない

子カテゴリには、親カテゴリへのリレーションがはられているため、子カテゴリを持つカテゴリを容易に削除できません。

1-2. 再帰クエリを用いずにサブツリー（子孫）を取得しにくい

深さの最大値が決まっていれば外部結合などを利用して、深さの数分だけ自己結合を行えば取得できますが、深さの最大値がわからない時に困ります。

SELECT
  c1.id AS cat1_id, c2.id AS cat2_id, c3.id AS cat3_id
FROM
  categories c1
LEFT OUTER JOIN categories c2 ON c2.parent_id = c1.id
LEFT OUTER JOIN categories c3 ON c3.parent_id = c2.id
WHERE c1.id = 473 -- サブツリー（子孫）を取得したい節点のid
;

ただし、再帰クエリを書けるデータベースであれば、例えば次のようなクエリを実行することで取得できます。

WITH RECURSIVE children(id, parent_id) as (
  SELECT categories.id, categories.parent_id
  FROM   categories
  WHERE  categories.id = 473 -- サブツリー（子孫）を取得したい節点のid
  UNION ALL
  SELECT categories.id, categories.parent_id
  FROM   categories,    children
  WHERE  children.id = categories.parent_id
)
SELECT id FROM children
;

同様に、対象となるノードの祖先も取得できます。

WITH RECURSIVE ancestor(id, parent_id) as (
  SELECT categories.id, categories.parent_id
  FROM   categories
  WHERE  categories.id = 473 -- 祖先を取得したい節点のid
  UNION ALL
  SELECT categories.id, categories.parent_id
  FROM   ancestor, categories
  WHERE  ancestor.parent_id = categories.id
)
SELECT id FROM ancestor
;

2. 対応策

2-1. 「子カテゴリをもつカテゴリを安易に削除できない」の対応策

Railsなので、before_destroyなどでチェックをしてあげると良いと思います。

before_destroy do
  return unless children.present?
  errors.add(:base, '紐づいている子カテゴリを削除してください')
  throw :abort
end

移行作業を行ってもらってから、削除してもらうというように制限をかけることになります。
面倒だという声があるばあいは、一括で別のカテゴリに紐付け直しができるようなUIを提供しても良いかもしれません。
子カテゴリの他にも、紐づいているアイテムがある場合は削除できないようにするなどの条件をつけても良いでしょう。

2-2. 「再帰クエリを用いずにサブツリー（子孫）を取得しにくい」の対応策

Railsなので、再帰関数を実装してしまえば良いと思います。
例えば、サブツリー（子孫）を取得したい場合、次のようなインスタンスメソッドを実装してみました。

def descendants(category = self, array = [], include_self: true, only_id: true)
  array << (only_id ? self.id : self) if include_self && id == category.id
  return array + [only_id ? category.id : category] if category.children.blank?
  category.children.eager_load(:children).each do |cat|
    array << (only_id ? cat.id : cat)
    descendants(cat, array, include_self: include_self, only_id: only_id)
  end
  array
end

ただし、上記だとActiveRecordのeager_loadが深いところまで効かないので、深さの最大値がわかっている場合は、次のようにしても良いかもしれません。（もし、再帰関数にした場合でも上手にeager_loadを使える実装方法があれば教えていただけますと幸いです。）

def descendants(include_self: true, only_id: true)
  [].tap do |a|
    a << (only_id ? self.id : self) if include_self
    children.eager_load(children: :childen).each do |cat2| # ・・・(1)
      a << (only_id ? cat2.id : cat2)
      cat2.children.each do |cat3|
        a << (only_id ? cat3.id : cat3)
        cat3.children.each do |cat4|
          a << (only_id ? cat4.id : cat4)
        end
      end
    end
  end
end

また、(1)のところは階層数に合わせて

children.eager_load(children: { childen: :children }).each do |cat2|

などとしていけば良いでしょう。１クエリだと辛くなってきた場合は、クエリを増えるのを許容してeager_loadではなくincludesを使うことも考えた方が良い場合があります。

この方法の問題点としては、返り値の型がActiveRecordのCollectionでないということです。本来ならば、Category::ActiveRecord_Relationで返ってきてほしいところなのです。
そういう場合は、少し二度手間になりますが、

category = Category.first
Category.where(id: category.descendants(only_id: true))

のように再度取得すれば良いですが、実際にはグルーピングしたものがほしいことが多いと思うので、あまり使わないかもしれません。
この辺りについては、4. 補足においてSQLのWITH RECURSIVEを用いた方法を記載していますのでそちらもご覧ください。

2. Categoryモデルの実装

重要な再帰関数を実装したCategoryモデルの例を示します。

class Category < ApplicationRecord
  belongs_to :parent, class_name: 'Category', foreign_key: :parent_id
  has_many :children, class_name: 'Category', foreign_key: :parent_id

  def ancestors(category = self, result = [], include_self: true, only_id: true)
    return result + [only_id ? category.id : category] if category.root?
    ancestors(category.parent, result, only_id: only_id) +
      (!include_self && id == category.id ? [] : [only_id ? category.id : category])
  end

  def descendants(category = self, array = [], include_self: true, only_id: true)
    array << (only_id ? self.id : self) if include_self && id == category.id
    return array + [only_id ? category.id : category] if category.children.blank?
    category.children.eager_load(:children).each do |cat|
      array << (only_id ? cat.id : cat)
      descendants(cat, array)
    end
    array
  end
end

3. `ancestry`gemのインスタンスメソッドとの対応

ancestrygemのREADEMEにあるインスタンスメソッドとの対応を表にしてみました。今回の実装の場合、ancestorsメソッドやdescendantsメソッドはデフォルトはidで返すようにしています。（他の実装をしている時にidで返す方が良く利用したためそうしています。）
また根（ルート）レコードのparent_idにはnullではなく、0をいれていますので、ancestrygemとは少しデータの入れ方が異なっている点にご留意ください。

ancestry	隣接リストモデル
`parent`	`parent`
`parent_id`	`parent_id`
`root`	`ancestors(only_id: false).first`
`root_id`	`ancestors.first`
`root?`	`parent_id == 0`
`ancestors`	`ancestors(include_self: false, only_id: false)`
`ancestors?`	`ancestors.length > 1`
`ancestor_ids`	`ancestors(include_self: false)`
`path`	`ancestors(only_id: false)`
`path_ids`	`ancestors`
`children`	`children`
`child_ids`	`children.pluck(:id)`
`has_parent?`	`parent_id != 0` or `self.class.exists?(id: parent_id)`
`has_children?`	`children.exists?`
`childless?`	`!children.exists?`
`siblings`	parent&.children \|\| self.class.root
`sibling_ids`	`siblings.pluck(:id)`
`has_siblings?`	`siblings.exists?`
`only_child?`	`siblings.count == 1`
`descendants`	`descendants(include_self: false, only_id: false)`
`descendant_ids`	`descendants(include_self: false)`
`subtree`	`descendants(only_id: false)`
`subtree_ids`	`descendants`
`depth`	`ancestors.count - 1`

4. 補足

上記では、rubyを用いて再帰処理を行いましたが、1-2で紹介したように、WITH RECURSIVEを用いて実装することもできます。
この方法だと、返り値の型はCategory::ActiveRecord_Relationのままとなります。やっていることは、find_by_sqlを用いてidを取得し、whereで取得したidで絞り込んでいるわけですが、そのままだと順番が変わってしまうので、orderで並び替えています。特にancestorsの方は順番が大切になってくるので注意が必要です。

4-1. `WITH RECURSIVE`を用いて`ancestors`メソッドを実装する

def ancestors(include_self: true)
  ids = Category.find_by_sql(<<-SQL).map(&:id) - (include_self ? [] : [id])
    WITH RECURSIVE ancestors(id, parent_id) as (
      SELECT
        categories.id,
        categories.parent_id
      FROM
        categories
      WHERE
        categories.id = #{id}
      UNION ALL
      SELECT
        categories.id,
        categories.parent_id
      FROM
        ancestors,
        categories
      WHERE
        ancestors.parent_id = categories.id
    )
    SELECT id FROM ancestors;
  SQL
  self.class.where(id: ids).order(ids.map { |id| "categories.id = #{id} desc" })
end

4-2. `WITH RECURSIVE`を用いて`descendants`メソッドを実装する

def descendants(include_self: true)
  ids = Category.find_by_sql(<<-SQL).map(&:id) - (include_self ? [] : [id])
    WITH RECURSIVE children(id, parent_id) as (
      SELECT
        categories.id,
        categories.parent_id
      FROM
        categories
      WHERE
        categories.id = #{id}
      UNION ALL
      SELECT
        categories.id,
        categories.parent_id
      FROM
        categories,
        children
      WHERE
        children.id = categories.parent_id
    )
    SELECT id FROM children;
  SQL
  self.class.where(id: ids).order(ids.map { |id| "categories.id = #{id} desc" })
end

4-3. ツリー構造の各実装の比較

設計	テーブル数	子孫アクセス	ツリーへのクエリ実行	挿入	削除	参照整合性維持
隣接リスト	1	簡単	難しい ※再帰クエリを使えば簡単	簡単	簡単 ※場合による	可能
経路列挙	1	簡単	簡単	簡単	簡単	不可
入れ子	1	難しい	難しい	難しい	難しい	不可
閉包テーブル	2	簡単	簡単	簡単	簡単	可能

参考

SQLアンチパターン
 達人に学ぶDB設計徹底指南書初級者で終わりたくないあなたへ
 RDBでツリー構造
 [PostgreSQL 8.4+] WITH RECURSIVEの動作を理解する
 木構造の親または子を再帰的に取得する
 SQLアンチパターン - ナイーブツリー