クロージャテーブルで実現する階層データ設計と高速クエリ — 実装例と運用ベストプラクティス
エバープレイ編集部はじめに — クロージャテーブルとは何か
クロージャテーブル（closure table）は、リレーショナルデータベースでツリーや有向非循環グラフ（DAG）の階層関係を効率良く扱うための設計パターンの一つです。親子関係の「推移的な閉包（transitive closure）」を明示的に格納することで、あるノードの全ての祖先や子孫を簡単かつ高速に取得できる点が特徴です。
基本アイデアとデータモデル
基本的な考え方は単純で、ノードを格納するテーブル（例：nodes）とは別に、ノード間のすべての祖先→子孫ペアを格納するクロージャテーブルを持ちます。典型的には次のような列を持ちます：
- ancestor（祖先ノードのID）
- descendant（子孫ノードのID）
- depth（距離。0は同一ノード）
例：同一ノード（A→A）は depth = 0、直の親子関係は depth = 1、親の親は depth = 2 といった具合です。
スキーマの例（SQL）
CREATE TABLE node (
id INT PRIMARY KEY,
name VARCHAR(255)
);
CREATE TABLE closure (
ancestor INT NOT NULL,
descendant INT NOT NULL,
depth INT NOT NULL,
PRIMARY KEY (ancestor, descendant),
FOREIGN KEY (ancestor) REFERENCES node(id) ON DELETE CASCADE,
FOREIGN KEY (descendant) REFERENCES node(id) ON DELETE CASCADE
);インデックス設計としては (ancestor, descendant) を主キーにし、必要に応じて descendant を単独で検索するためのインデックス（例：INDEX(descendant, ancestor) や INDEX(descendant)）を追加します。
なぜ使うか — メリット
- 読み取りクエリが非常に単純で高速：全子孫、直子、すべての祖先などを単一のSELECTで取得できる。
- 再帰（CTE）を使わずに階層を扱える環境でも有用（古いDBやオブジェクトレイヤーでの互換性）。
- 複雑な階層クエリ（例：あるノードの全ての子孫＋各子孫までの深さを同時に取得）が簡潔に書ける。
- ノードの権限継承や集約など、祖先ベース／子孫ベースの集計が容易。
デメリットと注意点
- 書き込みコストが高め：ノードの追加、削除、移動でクロージャテーブルに複数行の追加・削除が必要。更新頻度が高い場合は負担になる。
- 空間コスト：クロージャテーブルの行数はツリー構造に依存し、最悪ケース（長い鎖）では O(n^2) に近い数の行になる可能性がある。
- トランザクション管理が重要：更新操作は複数クエリにまたがるため、一貫性確保にトランザクションやロックが必須。
他のパターンとの比較
- 隣接リスト（Adjacency List）: 単純で書き込みが軽いが、全子孫・全祖先の取得に再帰（CTE）や複雑なロジックが必要。
- ネストセット（Nested Set）: 読み取り（サブツリー取得）に優れるが、ノードの挿入・移動が広範な更新を伴いコストが高い。
- マテリアライズドパス（Materialized Path）: パス文字列を格納するアプローチで、移動時に子孫のパス更新が必要。文字列操作で柔軟だがパスの長さやインデックス性に注意。
- クロージャテーブル: 読み取りと複雑クエリに強く、移動は手間だがロジックが一貫している。
代表的な操作の実装例（SQL）
前提：nodeテーブルとclosure(ancestor, descendant, depth)があるものとする。以下は概念的かつ一般的なSQL例です（DBMSによりLAST_INSERT_ID()やWITH句の扱いが異なるため、適宜調整してください）。
ノード追加（新しいノード n を親 p の下に挿入）
-- まず node テーブルに行を挿入して id を得る（ここでは :n が新しいID、:p は親ID）
INSERT INTO node (id, name) VALUES (:n, 'New Node');
-- 親 p のすべての祖先から新ノードへのパスを追加（距離を +1）
INSERT INTO closure (ancestor, descendant, depth)
SELECT ancestor, :n, depth + 1 FROM closure WHERE descendant = :p
UNION ALL
-- 新ノード自身のセルフ参照（depth = 0）
SELECT :n, :n, 0;親が NULL（ルートに挿入）なら、単に自己参照行だけを挿入します。
サブツリー削除（ノード t とその子孫すべてを削除）
-- 1) 削除対象の descendant を一時テーブルに格納
CREATE TEMPORARY TABLE to_delete AS
SELECT descendant FROM closure WHERE ancestor = :t;
-- 2) ノード本体を削除（closure側は外部キーのON DELETE CASCADEで消えるか、明示的に削除）
DELETE FROM node WHERE id IN (SELECT descendant FROM to_delete);
DROP TABLE to_delete;直接 closure を削除する場合は、同様にサブクエリで対象 descendant を取得して DELETE できます。複雑な DB では一時テーブルを使うのが安全です。
サブツリー移動（ノード m（とその子孫）を新しい親 np の下へ移動）
移動は最も注意が必要な操作です。大まかな手順：
- 移動するサブツリーの全 descendant を取得（D）。
- 移動するサブツリーの外部の祖先（移動前の祖先で、サブツリー内でないもの）から、サブツリーの descendant への closure 行を削除する。
- 新しい親 np の祖先（A）と、サブツリーの descendant（D）を組み合わせて、新しい祖先→子孫組を挿入する。新しい depth = depth(A→np) + 1 + depth(m→descendant) を計算。
SQL（概念例、MySQL 8 / PostgreSQL の WITH を使える場合）：
WITH
ancestors AS (
SELECT ancestor, depth FROM closure WHERE descendant = :np
),
descendants AS (
SELECT descendant, depth FROM closure WHERE ancestor = :m
)
-- 1) 古い祖先→移動対象子孫の結合行を削除
DELETE FROM closure
WHERE (ancestor, descendant) IN (
SELECT c.ancestor, d.descendant
FROM closure c
JOIN descendants d ON 1=1
WHERE c.descendant = :m AND c.ancestor NOT IN (SELECT descendant FROM descendants)
);
-- 2) 新しい祖先と子孫の直列結合を挿入
INSERT INTO closure (ancestor, descendant, depth)
SELECT a.ancestor, d.descendant, a.depth + d.depth + 1
FROM ancestors a CROSS JOIN descendants d;実運用では、上記をトランザクション内で行いロックや一時テーブルを使って整合性を保つのが安全です。
インデックスとパフォーマンスチューニング
- 主キー（ancestor, descendant）により一意性と高速検索を確保。追加で (descendant) 単体インデックスを張ると「あるノードの祖先を全部取る」クエリが速くなる。
- depth の型は SMALLINT/INT を状況に応じて選ぶ。極端に深いツリーでない限り SMALLINT で十分なことが多い。
- 大量更新が発生する場合、バッチ化して一時テーブルに差分を作りまとめて INSERT/DELETE することでトランザクションコストを下げられる。
- クロージャテーブル自体が膨らむ場合はパーティショニングや古い履歴の切り捨てを検討。
実用上のベストプラクティス
- 更新（挿入・移動・削除）は必ずトランザクションで囲む。
- 複雑な移動・削除は一時テーブルまたは WITH 句で対象集合を明示的に作成してから操作する。
- 外部キーの ON DELETE CASCADE をうまく使えばノード削除時の closure の掃除が容易になるが、意図しない削除に注意。
- 読み取り頻度が高く更新が少ないワークロードに特に向く。逆に更新頻度が極めて高ければ別パターン（隣接リスト＋CTE 等）を検討。
- アプリケーション側でキャッシュ（Redis 等）を併用し、ホットな階層クエリをキャッシュすると応答性が改善する。
実用例・ユースケース
- カテゴリツリー（ECサイトの商品カテゴリ）
- 組織図（従業員の上長／部下構造）
- フォーラムのスレッドツリー
- 権限（ACL）や設定の継承ルール（祖先からの権限継承を容易に判定）
拡張・派生アイデア
- direct フラグ（ancestor と descendant が直結か否か）を持たせると、直子取得が速くなるが冗長。
- パス文字列（例：「/1/4/23」）を併用することで、人間可読なパスをすぐに得られる。ただし移動時の更新コストを考慮。
- エッジに重み（weight）や種類（relation_type）カラムを追加すれば、単なるツリー以上の表現（タグ付きグラフ等）に拡張可能。
いつクロージャテーブルを選ぶか
次の条件に当てはまる場合、クロージャテーブルは有力な選択肢です：
- 読み取り（祖先や子孫の取得）頻度が高い
- ツリー移動は稀か、移動時に少し重い処理を許容できる
- DBで再帰クエリ（CTE）を使いたくない、あるいは使えない環境である
まとめ
クロージャテーブルは、階層データの読み取り（祖先や子孫の取得）を極めて効率よく行える強力な設計パターンです。一方で書き込み（特に移動や大量の更新）でのコスト増や、テーブルサイズの増加といったトレードオフがあります。読み込み重視で階層が安定しているシステム（カテゴリ、組織図、権限継承など）では非常に有用です。実装時はトランザクション、インデックス設計、一時テーブルを用いた安全な更新操作を心がけてください。
参考文献
- Managing Hierarchical Data in MySQL — Mike Hillyer
- Storing Hierarchical Data in a Database — Bill Karwin
- Transitive closure — Wikipedia
- Modeling tree data in relational databases — Vertabelo
- Stack Overflow: What is the best database design to store hierarchical data?
投稿者プロフィール
