親子テーブルと階層データ設計の実装パターン徹底解説：隣接リスト/ネストドセット/マテリアライズドパス/クロージャーテーブルの比較
エバープレイ編集部親子テーブルとは
親子テーブル（おやこテーブル）とは、データベースで「階層構造」を表現するためのテーブル設計全般を指す言葉です。典型的には「親（parent）」と「子（child）」の関係をテーブル内の外部キーで表現します。カテゴリ階層、スレッド状コメント、組織図、部品表（BOM）など、階層データを扱う場面で用いられます。
基本概念と用語
- 主キー（PK）：各行を一意に識別する列（例: id）。
- 外部キー（FK）：親を参照する列（例: parent_id）。同一テーブルを参照することが多い（自己参照）。
- 参照整合性：外部キー制約により、親が削除されたときの動作を制御（CASCADE, SET NULL, RESTRICT/NO ACTION など）。
よく使われる実装パターン（長所・短所）
1) 隣接リスト（Adjacency List）
テーブルに parent_id を持たせる最もシンプルな方法。
CREATE TABLE items (
id INT PRIMARY KEY,
parent_id INT NULL REFERENCES items(id),
name TEXT
);- 長所：設計がシンプルでCRUDが直感的。挿入・削除が容易。
- 短所：再帰的な階層取得（すべての子孫を取る等）が複雑で、再帰クエリ（WITH RECURSIVE）が必要。
2) ネストドセット（Nested Sets）
各ノードに left/right（lft/rgt）番号を付与し、部分木をレンジ検索で取得する手法（Joe Celko の提案）。
CREATE TABLE nested (
id INT PRIMARY KEY,
lft INT,
rgt INT,
name TEXT
);- 長所：読取り（部分木全体取得）が高速（単一レンジ検索）。ツリーの列挙が効率的。
- 短所：挿入・移動で多数行の更新が必要。実装・理解がやや難しい。
3) マテリアライズドパス（Materialized Path）
各ノードにルートからのパス（例: '/1/4/7/'）を保存する手法。
CREATE TABLE mp (
id INT PRIMARY KEY,
path TEXT, -- '/1/4/7/'
name TEXT
);- 長所：部分木の検索はLIKEやプレフィックス検索で容易。移動は影響範囲のパス書換えのみ。
- 短所：パス文字列操作やパフォーマンス（文字列検索）が問題になる場合がある。階層深度の制御がやや曖昧。
4) クロージャーテーブル（Closure Table）
祖先と子孫の全組み合わせ（祖先→子孫）を別テーブルで保持する手法。通常、距離（depth）情報も格納する。
CREATE TABLE nodes (
id INT PRIMARY KEY, name TEXT
);
CREATE TABLE closure (
ancestor INT,
descendant INT,
depth INT,
PRIMARY KEY (ancestor, descendant),
FOREIGN KEY (ancestor) REFERENCES nodes(id),
FOREIGN KEY (descendant) REFERENCES nodes(id)
);- 長所：任意の階層クエリが高速（JOIN 一発）。部分木の移動・切り出しも制御しやすい。
- 短所：ノード数が増えるとテーブルが大きくなる（ノードごとに祖先数分の行が増える）。書き込みコストは高め。
再帰クエリの例（WITH RECURSIVE）
PostgreSQL / MySQL 8.0+ / SQL Server などは再帰CTEをサポートしています。隣接リストから全子孫を取得する例：
WITH RECURSIVE subtree AS (
SELECT id, parent_id, name, 0 AS depth FROM items WHERE id = 2
UNION ALL
SELECT i.id, i.parent_id, i.name, s.depth + 1
FROM items i
JOIN subtree s ON i.parent_id = s.id
)
SELECT * FROM subtree ORDER BY depth;注意：MySQLは8.0で再帰CTEをサポート。古いバージョンや一部DBは代替手段（ストアドプロシージャ、アプリ側再帰）を用いる必要があります。
インデックスとパフォーマンス考慮
- 隣接リスト：parent_id にインデックスを貼るのは必須（再帰ジョイン時の性能向上）。
- ネストドセット：lft, rgt に対する範囲検索が主なので、これらのインデックス設計が重要。
- マテリアライズドパス：LIKE '%/4/%' のようなパターンはインデックスが効きにくい。プレフィックス検索を使える設計にする（例: path を接頭辞検索可能にする）。
- クロージャーテーブル：ancestor, descendant の複合PKや個別インデックスを用意する。
参照整合性と削除ポリシー
外部キー制約には ON DELETE CASCADE、SET NULL、RESTRICT/NO ACTION などのオプションがあります。標準SQLでは NO ACTION は遅延可能な設定があり得ますが、実装ごとに動作が異なります（例：MySQLでは NO ACTION は RESTRICT と同様に即時チェック）。運用時は使用するDBの仕様を確認してください。
運用上の注意点
- 循環（AがBの親、BがAの親になる等）を禁止するためのチェックが必要（アプリ側またはトリガー/制約で）。
- 部分木の移動・削除は実装方式によってコストが大きく異なる（ネストドセットやクロージャーは更新が高コストになる場合が多い）。
- 大量データでの深い再帰はスタック/パフォーマンス問題を起こす場合がある。深さ制限やバッチ処理を検討する。
- UIで表示する際は、階層の展開・ページネーションなどを工夫し、必要なノードだけを取得する（遅延読み込み）。
アプリケーション（ORM等）での扱い
多くのORM（例：Laravel Eloquent, Django ORM, ActiveRecord 等）は自己参照リレーション（hasMany/belongsTo）をサポートしており、隣接リストの操作は比較的扱いやすいです。一方、ネストドセットやクロージャーテーブル向けのプラグイン/ライブラリ（例：lft/rgtを扱うパッケージやclosure table 拡張）があるので、要件に応じて活用すると実装工数を減らせます。
まとめ
「親子テーブル」は単に parent_id を持つテーブルから、ネストドセットやクロージャーテーブルのような高度な実装まで含む概念です。選択肢ごとに読み取り性能・書き込み性能・実装の複雑さが異なるため、利用シナリオ（読み取りが多いのか、頻繁に更新が発生するのか、階層の深さやノード数の想定）を元に適切な方式を選ぶことが重要です。また、再帰クエリ・インデックス・トランザクションの扱いについて使うDBの仕様を確認して実装してください。
参考文献
- PostgreSQL: WITH (Common Table Expressions)
- MySQL 8.0: WITH (Common Table Expressions)
- Wikipedia: Tree (data structure)
- Wikipedia: Nested set model
- Bill Karwin: Models for Hierarchical Data (overview of patterns)
- Joe Celko（ネストドセット等の著名な解説者）
投稿者プロフィール
