【SQLアンチパターン】「素朴ツリー」の落とし穴とスマートな解決策

Posted at 2025-03-21

ツリー構造を管理するために `parent_id` を使っていませんか？

データベースで カテゴリや組織のツリー構造 を管理する場合、
よく parent_id を使った 「素朴ツリー（Naïve Trees）」 という設計が採用されます。

しかし、この方法には 検索・更新・削除のパフォーマンスが悪くなる問題 があります！
本記事では、「素朴ツリー」の問題点と、より効率的な代替手法を紹介します。

素朴ツリーの構造

ツリー構造を表現するための典型的なテーブル設計。

CREATE TABLE categories (
    id SERIAL PRIMARY KEY,
    name TEXT NOT NULL,
    parent_id INTEGER REFERENCES categories(id)  -- 親カテゴリのID
);

データの例

id	name	parent_id
1	家電	NULL
2	テレビ	1
3	冷蔵庫	1
4	4Kテレビ	2

このように、parent_id を使ってツリー構造を表現する。

素朴ツリーの問題点

階層の深い検索が難しい

例えば、「家電」カテゴリ以下の全ての子カテゴリを取得したい場合、通常のSQLでは1回のクエリでは取得できない。

良くない方法（親→子を1段ずつ取得）

SELECT * FROM categories WHERE parent_id = 1;  -- "家電" の子カテゴリ（テレビ, 冷蔵庫）
SELECT * FROM categories WHERE parent_id = 2;  -- "テレビ" の子カテゴリ（4Kテレビ）

この方法では、ループを回して何度もクエリを発行しなければならず、パフォーマンスが悪い。

更新・削除が面倒

例えば、「テレビ」カテゴリを削除する場合、子カテゴリである「4Kテレビ」も削除しないと整合性が取れない。

良くない削除処理

DELETE FROM categories WHERE id = 2;  -- "テレビ" を削除
DELETE FROM categories WHERE parent_id = 2;  -- "4Kテレビ" も削除

この方法では、以下の問題が発生する。

子カテゴリの削除を手動で行う必要がある
データの不整合が発生する可能性がある
ツリーが深くなると削除処理が複雑になる

素朴ツリーの代替案

経路列挙モデル（Path Enumeration）

各ノードにツリーのパスを文字列として保存する方法。

CREATE TABLE categories (
    id SERIAL PRIMARY KEY,
    name TEXT NOT NULL,
    path TEXT NOT NULL  -- 例: "1/2/4"
);

例として、「4Kテレビ」の path は "1/2/4" となる。

この方法のメリットとデメリットは以下の通り。

メリット:

SQLの LIKE を使って簡単にツリー全体を検索できる（例: LIKE '1/%' で家電以下を取得可能）

デメリット:

path を更新する際、すべての子ノードの path も更新しなければならない

閉包テーブルモデル（Closure Table）

すべての親子関係を別テーブルで管理する方法。

CREATE TABLE category_hierarchy (
    ancestor INTEGER NOT NULL,
    descendant INTEGER NOT NULL,
    PRIMARY KEY (ancestor, descendant)
);