RDBで木構造を扱う4つのモデル ── 「parent_id を1列足す」の先にあるもの

はじめに

カテゴリの親カテゴリ、フォルダの親フォルダ、コメントの返信先。
こうした親子関係は、parent_id を1列持たせればひとまず表せます。

ただ、「ある枝の下にあるものを全部取りたい」となると、単純な parent_id だけではSQLが書きにくくなります。

この記事では、RDBで木構造を扱う4つのモデルを整理します。

TL;DR

• RDBで木を表現する主要モデルは4つ。隣接リスト／経路列挙／入れ子集合／閉包テーブル
• 違いは「階層情報をどこに持たせるか」。読み取りを楽にすると更新が重くなり、更新を軽くすると検索側にしわ寄せが来る
• 再帰CTEや階層問い合わせが使える現在、まずは隣接リストから考える。サブツリー操作が多く、性能やクエリ単純化を重視するなら閉包テーブルを検討する

1. 「親IDだけ」で詰まる場面

階層を持たせたいとき、いちばん最初に思いつくのが「親IDを1列持たせる」設計です。
自然で素直なやり方ですが、扱う操作によっては素直なSQLが書けなくなります。
具体的に何が詰まるのか、典型的な場面から見ていきます。

1-1. parent_id を1列足す設計

身近な例として、ファイルシステムのフォルダ階層で考えます。
Documents の下に Work と Private がある。
Work の下にはさらに 2026 と Projects がぶら下がる、というよくある形です。

これをRDBで表すなら、各行に「自分の直近の親」を1列持たせるのが素直です。
階層の各点を ノード、最上位を ルート、ある点から下の枝全体を サブツリー と呼びます。

id	name	parent_id
1	Documents	NULL
2	Work	1
3	Private	1
4	2026	2
5	Projects	2
6	Client-A	5

parent_id で直近の親を指すだけ。ルートは parent_id = NULL。テーブルは1つ、外部キーは自己参照1本。シンプルです。

1-2. 「ある枝の下にあるもの全部」が取れない

問題は、Work 配下のフォルダを全部取りたい、というようなクエリです。
Work の直近の子なら1回の JOIN で取れます。
孫まで欲しいなら2回。
ひ孫まで欲しいなら3回。

-- Workから3階層下まで取得する例(深さが事前にわかる前提)
SELECT c1.*, c2.*, c3.*
FROM folders c1
  LEFT JOIN folders c2 ON c2.parent_id = c1.id
  LEFT JOIN folders c3 ON c3.parent_id = c2.id
WHERE c1.id = 2;

この例では階層ごとに列が増えるため、深さが変わるとSQL自体を書き換える必要があります。
ところが、木の深さは事前に決まっていないことのほうが多いはずです。
フォルダもカテゴリツリーもコメントスレッドも、深さに上限を引きたくない。
JOIN の段数を固定する以上、想定より深い枝が出てきた瞬間に取りこぼします。

1-3. アプリ側でツリーを組み直すのも重い

別案として「全件取得してアプリ側でツリーに組み直す」やり方もあります。SQL自体は単純です。

SELECT * FROM folders;

ただ、ノードが数千・数万になるとDBからアプリへ全件転送するコストが効いてきます。
本当に欲しいのは1サブツリーだけなのに、毎回テーブル全体を往復することになります。
ピンポイントで子孫だけを引きたい。そう思った瞬間、単純なJOINだけでは扱いづらいことに気づきます。

2. なぜ詰まるのか: 木をフラットな表で持つということ

3つの場面で詰まったのは偶然ではありません。フラットな表に階層を埋め込むやり方そのものに、構造的な向き不向きが生まれます。

2-1. 木の操作は「隣接」だけでは足りない

木に対してやりたい操作は、直近の親子だけではありません。

• 直近の親子（隣接）: 「Workの直接の子は？」
• 子孫全体: 「Work配下にあるフォルダ全部」
• 先祖全体: 「Client-Aから根までのパス」
• 区間・範囲: 「ある枝の合計サイズ」「あるカテゴリ配下の商品数」

「隣接」だけを持つ parent_id 設計では、子孫や先祖をたどるには 木の深さの分だけ クエリやJOINを重ねる必要があります。
深さが事前にわからないと、これが書けません。

2-2. 表に階層を「埋め込む」設計判断

RDBは行と列が並んだ平らな世界です。
木は階層を持った立体的な構造です。
両者をつなぐには、階層情報を どこかの列・テーブルに埋め込む 必要があります。

どこに埋め込むかで、得意な操作が変わります。
よく使われる形は、だいたい次の4つです。

3. 4つのモデル: 階層情報をどこに埋め込むか

「階層情報を何の形で、どこに持つか」の選択肢を、横一列に並べてみます。

モデル	持つ情報	持つ場所
隣接リスト	直近の親のID	同じテーブルの1列
経路列挙	根からの経路（文字列）	同じテーブルの1列
入れ子集合	子孫を含む数値区間（左右値）	同じテーブルの2列
閉包テーブル	先祖と子孫の全組	別テーブル

• 隣接リスト: 各行に「直近の親」を1つだけ持つ。最も馴染みのある形
• 経路列挙: 各行に「自分までの経路」を文字列で1つ持つ。/Documents/Work/2026 のようなイメージ
• 入れ子集合: 各行に「自分の子孫全部を含む数値の区間」を持つ。左右の2つの値で区間を表す
• 閉包テーブル: 「先祖と子孫の全組」を別テーブルに切り出して持つ

それぞれの構造・読み取り・更新・整合性を、次章から1つずつ掘っていきます。

4. 隣接リスト: 親IDを1列持つ

最も馴染みのある形です。parent_id を1列持たせるだけのシンプルな設計から始めます。

4-1. 構造

自分の親のIDを 自己参照外部キー（同じテーブルの主キーを参照する外部キー）で1列持ちます。

CREATE TABLE categories (
  id        SERIAL PRIMARY KEY,
  name      VARCHAR(64) NOT NULL,
  parent_id INTEGER REFERENCES categories(id)
);

カテゴリツリーをこのテーブルで表すと、1章のフォルダ階層の例と同じ形になります。各行は自分の親しか知らず、子孫の情報は持ちません。

4-2. 読み取り: 再帰CTEで子孫全部を取る

かつて隣接リストの弱点は、DBやバージョンによって「深さ不定の子孫取得」を素直に書きにくいことでした。
これを変えたのが 再帰共通表式（再帰CTE） という、WITH 句を自己参照する書き方です。

WITH RECURSIVE tree AS (
  SELECT id, name, parent_id, 1 AS depth
  FROM categories
  WHERE id = 2  -- Workを起点にする
  UNION ALL
  SELECT c.id, c.name, c.parent_id, t.depth + 1
  FROM categories c
  JOIN tree t ON c.parent_id = t.id
)
SELECT * FROM tree;

起点となるノードから、自己参照を繰り返してたどっていきます。
事前に木の深さがわからなくても、1本のクエリで子孫全部（ある行から見て下流の全ノード）が取れます。
Oracle・SQL Server・PostgreSQL・MySQL 8.0以降（2017年〜）・SQLite などの主要DBはほぼ対応済みです。

再帰CTEやDB固有の階層問い合わせが使えない環境では、隣接リストで「深さ不定の子孫全部」をSQLだけで扱うのはつらい問題でした。SQLアンチパターン 系の書籍で「ナイーブツリー」と呼ばれていた時期もあります。現在は主要DBで再帰的な問い合わせ手段が整ってきたため、隣接リストは実用的な第一候補に戻っています。

DBごとに構文差はありますが、PostgreSQL/MySQL/SQLiteの WITH RECURSIVE、SQL Serverの再帰CTE、Oracleの CONNECT BY など、主要DBには再帰的に階層をたどる手段があります。

4-3. 更新: サブツリー移動も親IDの付け替え1回

更新は、関係するノードだけを変更すれば済みます。
Work を Private の配下に移したい、というサブツリー移動も、ルートの parent_id を1回書き換えるだけです。

UPDATE categories SET parent_id = 3 WHERE id = 2;

Work の下にぶら下がっている子孫は、自分の parent_id が変わらないので、勝手についてきます。
サブツリー移動が1回のUPDATEで終わる のは隣接リストの大きな強みです。
この点はあとで他のモデルと対比します。

4-4. 整合性

自己参照外部キーが効いているので、存在しない親を指す子は作れません。「親のいない孤児ノード」が生まれない、というRDBらしい守りができます。

ただし、外部キーだけでは循環は防げません。たとえば自分の子孫を親に付け替える操作は、アプリ側・トリガー・制約設計などで別途防ぐ必要があります。

4-5. 残る弱点

弱点は性能です。
再帰CTEは深さが大きい木や、ノード数の多い木で性能特性が読みにくい部分があります。
CPU使用率は控えめでもメモリが膨らんでいく、という観測例もあります。
日々ノードが増えるツリーや、深さに制限のない用途では、本番投入前に実データで負荷を確認しておくのが安心です。

5. 経路列挙: パス文字列を持つ

親IDではなく「経路そのもの」を文字列で持つ、というアプローチもあります。
UNIXのファイルパス /usr/local/lib を見ればわかるように、文字列でも階層は十分表せます。

5-1. 構造

path 列に、区切り文字つきで根からの経路を入れます。

id	path	name
1	/1/	Documents
2	/1/2/	Work
3	/1/3/	Private
4	/1/2/4/	2026
5	/1/2/5/	Projects
6	/1/2/5/6/	Client-A

path を見れば、そのノードがどこにいるかが一目でわかります。
実装では名前ではなくIDを並べることが多いです。名前は変更される可能性があるためです。

5-2. 読み取り: LIKEで先祖も子孫も一発

文字列のパターンマッチで、先祖も子孫も1本のSQLで取れます。

-- Work(/1/2/)の子孫を全部取る
SELECT * FROM categories
WHERE path LIKE '/1/2/%';

-- Client-A(/1/2/5/6/)の先祖を全部取る
SELECT * FROM categories
WHERE '/1/2/5/6/' LIKE path || '%';

再帰CTEを書かずに済むので、SQLはかなり短くなります。「パンくずリスト」（現在地まで先祖を順に並べたUI）にも向きます。

5-3. 更新

葉ノードの追加は、親の path に自分のIDを足すだけで終わります。
一方、サブツリー移動は重くなります。
Work を Private の配下に動かすと、Work 配下の子孫すべての path を書き換える必要があります。

5-4. 弱点: 整合性をDBで守れない

path が文字列である以上、DB側で「経路の正しさ」を保証できません。
/1/2/999/ のような存在しないIDを含む path を入れても、外部キーでは止められない。
アプリ側でパスを管理する責任が出てきます。

長さの制限もあります。VARCHAR で持つ以上、現実的な上限は決まります。深さが本当に無制限のツリーには向きません。

また、LIKE の書き方や照合順序によってはインデックスが効きにくくなるため、実データ量が多い場合は実行計画を確認します。

6. 入れ子集合: 左右値で区間を持つ

経路列挙は読み取りが軽い代わりに、整合性をDBで守れませんでした。ならば数値で範囲を表せばどうか、という発想が 入れ子集合 です。

6-1. 構造

各ノードに nsleft / nsright という2つの数値を持たせ、「自分の子孫全部を含む数値区間」を表現します。

6-2. 直感: 木の周りを深さ優先で番号付け

左右値は、木の周りをぐるっと深さ優先でなぞって、訪れた順に番号を振っていくと自然に決まります。
各ノードについて、下に降りるときに nsleft、戻ってくるときに nsright を割り当てます。

ポイントは、子孫の左右値はすべて、自分の左右値の区間に収まる ことです。
Work は (2, 9)。
Projects は (5, 8)、Client-A は (6, 7)。
どちらも 2〜9 の中にきれいに収まっています。

id	name	nsleft	nsright
1	Documents	1	12
2	Work	2	9
3	Private	10	11
4	2026	3	4
5	Projects	5	8
6	Client-A	6	7

6-3. 読み取り: BETWEEN で子孫が取れる

子孫の判定は、区間に含まれるかどうかを見るだけ。BETWEEN で書けます。

SELECT child.*
FROM categories parent
JOIN categories child
  ON child.nsleft BETWEEN parent.nsleft AND parent.nsright
WHERE parent.id = 2;  -- Work自身を含むサブツリーを取得

再帰CTE不要で、サブツリー集計が単純な集約クエリになります。検索中心の用途では強力です。
本記事では「サブツリー」を、起点ノード自身を含む全子孫の意味で使います。BETWEEN の境界条件は両端を含むため、上のクエリには Work 自身も含まれます。

6-4. 更新の重さ

更新コストは高めです。
1つノードを挿入すると、それより右側にあるノード すべて の左右値をズラす必要があります。
新しいノードのために番号の幅を空けないといけないからです。

-- 新しいノードのために左右値 8, 9 を空ける
UPDATE categories
SET nsleft  = CASE WHEN nsleft  >= 8 THEN nsleft + 2 ELSE nsleft END,
    nsright = nsright + 2
WHERE nsright >= 8;

更新の影響範囲が、挿入位置から右側のノード全体に広がります。木の形が頻繁に変わる用途では、これがそのままコストになります。

6-5. 弱点

左右値の正しさは、外部キーでは表現できません。
誤って値を壊してもDBは止めてくれない。
アプリが入れ子集合のルールを破ると、検索結果が静かに狂います。
検索中心で、ほとんど更新が発生しない木にだけ向くモデルと考えるのが現実的です。

7. 閉包テーブル: 先祖子孫の全組を別表に持つ

ここまでの3モデルは1テーブルで完結していました。最後はあえてテーブルを分けるアプローチです。

7-1. 構造: 2つのテーブルに分ける

本体テーブルからは階層情報を抜きます。代わりに「先祖と子孫の全組」を保持する別テーブルを置きます。

CREATE TABLE categories (
  id   SERIAL PRIMARY KEY,
  name VARCHAR(64) NOT NULL
);

CREATE TABLE tree_paths (
  ancestor   INTEGER NOT NULL REFERENCES categories(id),
  descendant INTEGER NOT NULL REFERENCES categories(id),
  PRIMARY KEY (ancestor, descendant)
);

tree_paths には、自分自身を含む すべての先祖・子孫の組を入れます。
Work なら自分自身 (2, 2) に加えて、子孫として (2, 4) (2, 5) (2, 6)。
さらに先祖との関係で (1, 2) も入ります。

ancestor	descendant
1	1
1	2
1	3
1	4
1	5
1	6
2	2
2	4
2	5
2	6
...	...

ノード数より行数がずっと多くなります。

7-2. 読み取り: 再帰なしで一発

子孫の取得は、tree_paths を引くだけです。再帰CTEは不要。

SELECT c.*
FROM categories c
JOIN tree_paths t ON c.id = t.descendant
WHERE t.ancestor = 2;  -- Work自身を含むサブツリー

先祖の取得も同じ形で書けます。読み取りクエリが短く済むのが、閉包テーブルの強みです。

7-3. 更新: シンプルだが「漏らすと壊れる」

新しいノードを挿入するときは、tree_paths に「自分の先祖たち→自分」のレコードを まとめて 追加します。

-- Client-A(id=6)の下にid=8のノードを追加する例
INSERT INTO tree_paths (ancestor, descendant)
  SELECT ancestor, 8 FROM tree_paths WHERE descendant = 6
  UNION ALL
  SELECT 8, 8;

サブツリー削除なら、descendant に該当ノードを含む行を一括削除します。
SQLそのものは難しくありませんが、本体テーブルと tree_paths を 常に同期 させる責任があります。
片方だけ更新すると、エラーにならないまま結果が静かに狂う。これが厄介な部分です。
特にサブツリー移動では、古い祖先関係の削除と新しい祖先関係の追加を同じトランザクションで行う必要があります。

7-4. 整合性

tree_paths の2列をそれぞれ本体テーブルへ外部キーで紐づけられるので、「存在しないノードを指す行」はDBレベルで防げます。
整合性の保証という意味では入れ子集合・経路列挙より強いです。

7-5. 強み: ノードが複数の木に属せる

tree_paths は本体から独立しているので、応用として、複数親や多重所属のような構造にも拡張しやすいです。たとえばカテゴリの多重所属（ある商品が「家電」と「キャンペーン」両方の配下に出る）を、本体を増やさず経路の組だけで表せます。
ただしその場合は厳密には単純な木ではなくなるため、循環防止や重複集計の扱いを別途考える必要があります。

7-6. コスト

行数が増えます。
深さ n のノードを1つ追加するたびに、自分を子孫とする組が n 個分必要になります。
木が深く・広くなるほど tree_paths は急速に膨らみます。
読み取りを先に計算して保存しておくぶん、行数で支払うモデルです。

8. 比較と選び方

4モデルを見終わったので、改めて並べて選び方を整理します。

8-1. 3軸での比較

軸 \ モデル	隣接リスト	経路列挙	入れ子集合	閉包テーブル
テーブル数	1	1	1	2
子孫の読み取り	普通（再帰CTE）	楽	楽	楽
直近の親子の取得	楽	楽	重い	楽
サブツリー更新	楽	重い	とても重い	普通
整合性をDBで守れるか	守れる	守れない	守れない	守れる

並べてみると、だいたい同じ話に戻ってきます。読み取りを楽にすると更新が重くなる。DBで守るものを増やすと、そのぶん更新時の手順が増える。1つで全部勝つモデルはありません。

8-2. 操作の重心で選ぶ

判断軸は3つで足ります。

分岐の根は「読み取りの重心がサブツリーにあるか」。
ここで「いいえ」なら隣接リストで十分です。
「はい」のときに初めて、更新頻度と整合性要件の組み合わせで他のモデルに分かれていきます。

主要DBはおおむね再帰CTE対応済みなので、WITH RECURSIVE が使えるかは判断軸として独立させなくて大丈夫です。
古いバージョンに縛られている場合だけ注意します。

8-3. 実務的な落としどころ

順番としては、まず隣接リストから考える で困りません。シンプルで、更新が局所的で、外部キーで整合性も守れる。再帰CTEで子孫取得もそれなりに書けます。

ここから例外的に他のモデルへ動くケースは、

• サブツリー操作が極端に多い／大規模で再帰の性能が読めない → 閉包テーブル
• パンくずなど、経路を文字列としてそのまま使いたい → 経路列挙
• 更新がほぼ発生せず、サブツリー集計が大量に飛んでくる → 入れ子集合

くらいに絞られます。「親IDでサブツリー操作の性能に困ったら、閉包テーブルを検討する」くらいに覚えておけば、実務ではかなり判断しやすくなります。

おわりに

木をフラットな表に押し込む以上、どこかに歪みは出ます。
読み取りを取れば更新が重くなり、更新を取れば整合性が弱くなる。
歪みを どこに集中させるか を選んでいるのが、4モデルの違いです。

parent_id を1列足す前に、「自分はこの木で何を一番頻繁にやるのか」を一度立ち止まって考えてみると、設計の解像度が一段上がります。