経路列挙モデル（マテリアライズドパス）でカテゴリツリーを扱う

RDB でツリー構造（カテゴリ、組織図、コメントのスレッド）を持つときの定番のひとつ。「根からその行までの経路を、1本の文字列カラムに焼き込んでおく」 だけの素朴なモデルで、parent_id だけでは重い「子孫を全部取る」が 前方一致 1 発になる。

結論

• 経路列挙モデル＝ path カラムに祖先の ID を区切り文字で並べる（/1/4/9/）。増えるカラムは 1 本だけ
• 強いのは読み。子孫の全取得・サブツリー削除が LIKE '/1/4/%' の 1 クエリで済む
• 弱いのは移動。サブツリーを付け替えると、配下全行の path を書き換える必要がある
• 整合性を DB 側で守れない（path と parent_id がズレても DB は気づかない）。ここは自前で閉じ込める

出発点 — 隣接リストだけだと何が困るか

まずは素直な parent_id（隣接リストモデル）から。書店の商品カテゴリを題材にする。

flowchart TD
    C1["1 本"] --> C2["2 技術書"]
    C1 --> C3["3 小説"]
    C2 --> C4["4 プログラミング"]
    C2 --> C5["5 デザイン"]
    C4 --> C6["6 Ruby"]
    C4 --> C7["7 SQL"]

categories（隣接リスト）

親子 1 段は簡単。困るのは「技術書（id=2）配下のカテゴリを全部」のような、段数が不定の問い合わせ。

# 深さが分からないので、ループでたどるしかない
ids = [2]
current = [2]
until current.empty?
  current = Category.where(parent_id: current).pluck(:id)
  ids.concat(current)
end

深さの分だけクエリが飛ぶ。 再帰 CTE（WITH RECURSIVE）で 1 クエリにはできるが、今度は素の ActiveRecord から外れて生 SQL になる。

経路列挙モデル — 経路そのものを列に持つ

「根からその行までの ID の並び」を、区切り文字つきの文字列としてカラムに保存する。

categories（経路列挙）

ファイルシステムのフルパスとまったく同じ発想。ここから先の操作は、全部この文字列に対する前方一致で書ける。

-- 技術書(id=2, path='/1/2/')の子孫（自分自身も含む）
SELECT * FROM categories WHERE path LIKE '/1/2/%';

なぜ ORDER BY path でツリー順になるのか。 ある行の子孫の path は、必ずその行の path を接頭辞に持つ。辞書順に並べれば、親の直後にその子孫がまとまって並ぶ（＝深さ優先の並び）。

Rails での実装

マイグレーション

class CreateCategories < ActiveRecord::Migration[7.1]
  def change
    create_table :categories do |t|
      t.string     :name,   null: false
      t.references :parent, foreign_key: { to_table: :categories }
      t.string     :path,   null: false, default: ""
      t.timestamps
    end

    # 経路は一意（同じ経路の行が2つ存在してはいけない）
    add_index :categories, :path, unique: true

    # 前方一致 LIKE をインデックスに乗せるための opclass（PostgreSQL）
    add_index :categories, :path, opclass: :varchar_pattern_ops,
                                  name: "index_categories_on_path_pattern"
  end
end

PostgreSQL の落とし穴。 DB のロケールが C 以外（日本語環境だとほぼ ja_JP.UTF-8 や en_US.UTF-8）だと、通常の B-tree インデックスは LIKE 'prefix%' に使われない。varchar_pattern_ops / text_pattern_ops を指定したインデックスを別に張る必要がある。MySQL では通常のインデックスで前方一致が効くのでこの対応は不要。

モデル

class Category < ApplicationRecord
  SEPARATOR = "/".freeze

  belongs_to :parent, class_name: "Category", optional: true
  has_many :children, class_name: "Category", foreign_key: :parent_id,
                      dependent: :restrict_with_error

  after_create :assign_path

  scope :roots, -> { where(parent_id: nil) }
  scope :in_tree_order, -> { order(:path) }

  # 自分を含むサブツリー
  def subtree
    self.class.where("path LIKE ?", "#{path}%")
  end

  # 自分を除く子孫
  def descendants
    self.class.where("path LIKE ?", "#{path}_%")
  end

  # 祖先（根に近い順）
  def ancestors
    return self.class.none if ancestor_ids.empty?

    self.class.where(id: ancestor_ids).in_tree_order
  end

  def ancestor_ids
    path.split(SEPARATOR).reject(&:empty?).map(&:to_i) - [id]
  end

  # 根を 0 とした深さ。"/1/2/4/" なら区切り 4 個 → 2
  def depth
    path.count(SEPARATOR) - 2
  end

  def root?
    parent_id.nil?
  end

  private

  def assign_path
    update_column(:path, build_path(parent))
  end

  def build_path(new_parent)
    prefix = new_parent ? new_parent.path : SEPARATOR
    "#{prefix}#{id}#{SEPARATOR}"
  end
end

path に自分自身の ID を含めるので、値が確定するのは INSERT 後（採番後）。そのため after_create で update_column している。after_create は save のトランザクション内で走るので、INSERT と UPDATE はアトミックに入る。

主キーが UUID で アプリ側で採番するなら、before_create で self.id ||= SecureRandom.uuid してから path を組み立てられる。追加 UPDATE が消えるので、書き込みが多いなら検討する価値がある。

使う

books  = Category.create!(name: "本")
tech   = Category.create!(name: "技術書", parent: books)
prog   = Category.create!(name: "プログラミング", parent: tech)
ruby   = Category.create!(name: "Ruby", parent: prog)

ruby.path        # => "/1/2/3/4/"
ruby.depth       # => 3
ruby.ancestors   # => [本, 技術書, プログラミング]
tech.descendants # => [プログラミング, Ruby]  ← 1クエリ
tech.subtree     # => [技術書, プログラミング, Ruby]

サブツリーごと 1 クエリで削除

def destroy_subtree!
  subtree.delete_all
end

dependent: :destroy で 1 件ずつ再帰的に消すと、深さ分だけクエリが飛ぶ。経路列挙なら DELETE 1 発。逆にコールバックは走らないので、そこが必要なら素直に destroy_all を使う。

移動 — 経路列挙で唯一しんどいところ

「デザイン（id=5）を、技術書の下から本の直下へ移す」。移動対象だけでなく、配下の全行の path を書き換える必要がある。

flowchart LR
    subgraph Before["移動前"]
        B1["本<br/>/1/"] --> T1["技術書<br/>/1/2/"]
        T1 --> D1["デザイン<br/>/1/2/5/"]
        D1 --> E1["UI<br/>/1/2/5/8/"]
    end
    subgraph After["移動後"]
        B2["本<br/>/1/"] --> D2["デザイン<br/>/1/5/"]
        D2 --> E2["UI<br/>/1/5/8/"]
    end
    D1 -->|"接頭辞 /1/2/5/ を /1/5/ へ差し替え"| D2

class Category < ApplicationRecord
  class CircularMoveError < StandardError; end

  def move_to!(new_parent)
    # 自分自身・自分の子孫の下には移動できない（循環する）
    if new_parent && new_parent.path.start_with?(path)
      raise CircularMoveError, "自分自身または子孫の配下には移動できません"
    end

    old_path = path
    new_path = build_path(new_parent)

    transaction do
      # 子孫の path の接頭辞だけを差し替える
      descendants.update_all([
        "path = ? || substr(path, ?)", new_path, old_path.length + 1
      ])
      update!(parent: new_parent, path: new_path)
    end
  end
end

ポイントは 3 つ。

1. 循環チェックを先にやる。 new_parent.path.start_with?(path) は「新しい親が自分の子孫（または自分自身）」を一発で判定できる。path の接頭辞性がそのまま効く
2. replace() で全置換しない。 replace(path, '/1/2/5/', '/1/5/') は文字列中のどこでもマッチするので、substr で先頭からの長さ分だけを切り落として繋ぎ直す
3. 必ずトランザクションで囲む。 途中で落ちると parent_id と path がズレたまま残る（→ トランザクションと分離レベル）

MySQL では || が文字列連結にならない（デフォルトでは論理 OR）。CONCAT(?, SUBSTR(path, ?)) に書き換える。

移動が「たまにしか起きない」なら UPDATE 1 発で終わるので実用上まったく問題ない。移動が主要ユースケースなら、経路列挙は向いていない（後述の比較表を参照）。

ツリーを 1 クエリで組み立てる

画面にツリーを出すとき、children を再帰的にたどると N+1 になる。経路列挙なら サブツリーを 1 クエリで取って、Ruby 側で組むのが素直。

def self.tree_from(root)
  nodes = root.subtree.in_tree_order.to_a
  by_parent = nodes.group_by(&:parent_id)

  build = lambda do |node|
    { node: node, children: (by_parent[node.id] || []).map(&build) }
  end
  build.call(root)
end

in_tree_order（ORDER BY path）で取れば、そのままインデント表示用のフラットな配列としても使える。

Category.where("path LIKE ?", "#{root.path}%").in_tree_order.each do |c|
  puts "#{'  ' * c.depth}#{c.name}"
end
# 本
#   技術書
#     プログラミング
#       Ruby

Hash 化して引き当てる考え方は preloadとindex_by（N+1回避とHash化） と同じ。

ほかのモデルとの比較

ざっくりの選び方。

• 階層が浅い／親子 1 段しか使わない → 隣接リストのままでいい。無理にツリー用モデルを入れない
• 読みが圧倒的に多く、移動が稀（カテゴリ、組織図、地域マスタ） → 経路列挙
• 移動も検索も多い／深さ指定の問い合わせが多い → 閉包テーブル（closure_tree gem）
• 入れ子集合 は読み性能と引き換えに書き込みが致命的に重い。今から新規に選ぶ理由はほぼない

PostgreSQL なら ltree という選択肢もある。 経路列挙を型として持つ拡張で、GiST インデックスと <@ / ~（パスのパターンマッチ）が使える。ただし Rails からは生 SQL 寄りの扱いになるので、「文字列 + LIKE」で足りるならそれで十分なことが多い。

ハマりどころ

1. 区切り文字を前後に必ず付ける

これを外すと静かにバグる。 path を /1/2 のように末尾の区切りなしで持つと、

-- id=1 の子孫を取りたい
SELECT * FROM categories WHERE path LIKE '/1%';
-- → '/11/'（id=11 のツリー）まで一緒に取れてしまう

前後を区切り文字で挟む（/1/）だけで、LIKE '/1/%' が /11/ にマッチしなくなる。区切りは「ID に絶対現れない文字」を選び、必ず両端に付ける。

2. ORDER BY path は辞書順であって数値順ではない

/10/ は /2/ より前に来る。ツリーの構造（親の直後に子孫が来ること）は壊れないが、兄弟の並び順は ID 順にならない。表示順を制御したいなら、

• path に入れる値をゼロパディングする（format("%08d", id) → /00000001/00000002/）
• 兄弟内の並び順は position カラムを別に持ち、ORDER BY path, position にする

後者のほうが素直。「並び順」は「経路」とは別の関心事なので、混ぜないほうが後で困らない。

3. path と parent_id の二重管理

同じ情報を 2 か所に持っているので、片方だけ更新するコードが 1 か所でもあると壊れる。 DB の外部キーは path の正しさを何も保証してくれない。

• parent_id の更新は move_to! からしか行わない（update!(parent_id: ...) を直接呼ばせない）
• 形式だけでも DB 側で縛っておく（→ CHECK制約について）

# PostgreSQL の正規表現マッチ。「/数字/ の繰り返しで、両端が区切り文字」だけを許可する
add_check_constraint :categories,
  "path ~ '^(/[0-9]+)+/$'",
  name: "categories_path_format"

• 整合性チェックを rake タスクで用意しておくと、事故に気づける

Category.find_each do |c|
  expected = "#{c.parent&.path || '/'}#{c.id}/"
  puts "NG: #{c.id} #{c.path} != #{expected}" if c.path != expected
end

4. 深さの上限を決めておく

path は string（PostgreSQL では varchar(255)）だと、ID が 7 桁で 8 文字消費するので 30 段程度で溢れる。想定より深くなる可能性があるなら t.text :path にするか、アプリ側で最大深さのバリデーションを入れる。

validate :depth_within_limit

MAX_DEPTH = 10

def depth_within_limit
  errors.add(:parent, "の階層が深すぎます") if parent && parent.depth + 1 > MAX_DEPTH
end

5. ID ではなく slug を経路に入れるとき

/books/tech/ruby/ のように人間が読める経路にすると URL にそのまま使えて便利だが、代償がある。

• リネームがサブツリー全体の書き換えになる。 ID なら不変なので起きない
• slug に区切り文字やワイルドカードが混入しうる。 LIKE に渡す前に sanitize_sql_like でエスケープが必要

prefix = ActiveRecord::Base.sanitize_sql_like(node.path)
Category.where("path LIKE ?", "#{prefix}%")

ID 経路と slug 経路を両方持つ（検索は ID 経路、表示は slug 経路）のが落としどころになることが多い。

6. gem に寄せる判断

自前実装は 100 行程度で収まるが、ancestry gem がほぼ同じことをしている（ancestry カラムに祖先 ID を並べる方式）。深さのキャッシュ、孤児レコードの扱い、materialized_path2 フォーマットなど細かい面倒を見てくれるので、要件が標準的なら乗ったほうが早い。自前を選ぶのは、経路のフォーマットや移動時の挙動を握りたいときだけでいい。

まとめ

• 経路列挙モデルは path カラム 1 本。根からの経路を区切り文字つきの文字列で焼き込むだけ
• 子孫取得・サブツリー削除・ツリー順ソートが、すべて前方一致 1 クエリになる
• 代償は 移動時のサブツリー一括 UPDATE と、path の正しさを DB が保証してくれないこと
• 区切り文字は必ず両端に付ける。/1 だと /11/ を巻き込む
• PostgreSQL では varchar_pattern_ops のインデックスを張らないと前方一致がインデックスに乗らない
• 移動が主要ユースケースなら閉包テーブル、親子 1 段で足りるなら隣接リストのままでいい

「読むのは頻繁、動かすのは稀」なツリーなら、まず経路列挙を検討する。 カラム 1 本で済む割に効く場面が広い。

参考

• PostgreSQL: ltree
• PostgreSQL: WITH（再帰 CTE）
• PostgreSQL: Operator Classes（text_pattern_ops）
• ancestry gem
• closure_tree gem
• 関連: トランザクションと分離レベル / CHECK制約について / preloadとindex_by（N+1回避とHash化）