ツリー構造を管理するために `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
);

データの例

このように、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テレビ" も削除

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

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

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

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

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

メリット:

デメリット:

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

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

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

メリット:

デメリット:

モデル	特徴	メリット	デメリット
素朴ツリー	`parent_id` を使う	シンプルで直感的	階層検索や削除が大変
経路列挙	`path` にツリー構造を保存	`LIKE` で検索しやすい	更新時に`path`を変更する必要がある
閉包テーブル	別テーブルで親子関係を管理	階層の検索・削除が簡単	データ追加時に複数の挿入が必要

小規模なデータなら素朴ツリーでも問題ないが、大規模なツリー構造を扱う場合は 経路列挙 や 閉包テーブル を検討すべき。

データの用途に応じて適切な設計を選ぶことが重要。