はじめに

組織表やカテゴリなどの階層構造を持つデータをデータベースで管理する方法として、隣接リストモデルが使われることが多いです。しかし、階層構造が多くなったりすると隣接リストではなく、閉包テーブルを使った方が保守しやすいかもしれません。

サンプルデータ

以下のような組織構造を例として使用します：

閉包テーブルモデル

閉包テーブルは、可能な全てのパスを別テーブルで管理する方法です：

CREATE TABLE departments (id SERIAL PRIMARY KEY, name VARCHAR(255) NOT NULL);

CREATE TABLE department_paths (
  ancestor_id INTEGER REFERENCES departments (id),
  descendant_id INTEGER REFERENCES departments (id),
  path_length INTEGER NOT NULL,
  PRIMARY KEY (ancestor_id, descendant_id)
);

メリット

階層の深さに関係なく一定のパフォーマンス
全ての先祖・子孫の取得が容易
複数の親を持つ構造も表現可能

デメリット

実装が比較的複雑
パス情報の管理が必要
ストレージ容量を多く使用

departmentsテーブルのデータ

INSERT INTO
  departments (id, name)
VALUES
  (1, '会社全体'),
  (2, '営業部'),
  (3, '技術部'),
  (4, '管理部'),
  (5, '営業1課'),
  (6, '営業2課'),
  (7, '開発1課'),
  (8, '開発2課');

department_pathsテーブルのデータ

INSERT INTO
  department_paths (ancestor_id, descendant_id, path_length)
VALUES
  -- 自己参照（必須）
  (1, 1, 0), -- 会社全体
  (2, 2, 0), -- 営業部
  (3, 3, 0), -- 技術部
  (4, 4, 0), -- 管理部
  (5, 5, 0), -- 営業1課
  (6, 6, 0), -- 営業2課
  (7, 7, 0), -- 開発1課
  (8, 8, 0), -- 開発2課
  -- 第1階層（直接の親子関係）
  (1, 2, 1), -- 会社全体 -> 営業部
  (1, 3, 1), -- 会社全体 -> 技術部
  (1, 4, 1), -- 会社全体 -> 管理部
  (2, 5, 1), -- 営業部 -> 営業1課
  (2, 6, 1), -- 営業部 -> 営業2課
  (3, 7, 1), -- 技術部 -> 開発1課
  (3, 8, 1), -- 技術部 -> 開発2課
  -- 第2階層（祖父-孫関係）
  (1, 5, 2), -- 会社全体 -> 営業部 -> 営業1課
  (1, 6, 2), -- 会社全体 -> 営業部 -> 営業2課
  (1, 7, 2), -- 会社全体 -> 技術部 -> 開発1課
  (1, 8, 2) -- 会社全体 -> 技術部 -> 開発2課

この構造を使用すると、以下のような検索が可能になります：

-- 営業部の直接の子部署を取得
SELECT
  d.*
FROM
  departments d
  JOIN department_paths dp ON d.id = dp.descendant_id
WHERE
  dp.ancestor_id = 2
  AND dp.path_length = 1;

-- 会社全体の全ての子部署を取得（階層に関係なく）
SELECT
  d.*
FROM
  departments d
  JOIN department_paths dp ON d.id = dp.descendant_id
WHERE
  dp.ancestor_id = 1
  AND dp.path_length > 0;

-- 営業1課の全ての親部署を取得
SELECT
  d.*
FROM
  departments d
  JOIN department_paths dp ON d.id = dp.ancestor_id
WHERE
  dp.descendant_id = 5
  AND dp.path_length > 0;

隣接リストと閉包テーブルの比較

隣接リストモデル

隣接リストモデルは、各ノードが直接の親への参照を持つ最も単純な実装方法です：

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

メリット

実装がシンプル
データの挿入・更新が容易
直接の親子関係の取得が高速

デメリット

再帰的なクエリが必要で、深い階層の取得が複雑
特定のノードの全ての子孫や先祖を取得するのが難しい
パフォーマンスが階層の深さに依存する

実装例

基本的な操作

部署の追加

-- 部署の追加（自己参照も含める）
INSERT INTO
  departments (name)
VALUES
  ('営業部');

INSERT INTO
  department_paths (ancestor_id, descendant_id, path_length)
VALUES
  (1, 1, 0);

-- 子部署の追加
INSERT INTO
  departments (name)
VALUES
  ('営業1課');

INSERT INTO
  department_paths (ancestor_id, descendant_id, path_length)
SELECT
  t.ancestor_id,
  2,
  t.path_length + 1
FROM
  department_paths t
WHERE
  t.descendant_id = 1
UNION ALL
SELECT
  2,
  2,
  0;

階層構造の取得

-- 特定部署の全ての子部署を取得
SELECT
  d.*
FROM
  departments d
  JOIN department_paths dp ON d.id = dp.descendant_id
WHERE
  dp.ancestor_id = 1;

-- 特定部署の全ての親部署を取得
SELECT
  d.*
FROM
  departments d
  JOIN department_paths dp ON d.id = dp.ancestor_id
WHERE
  dp.descendant_id = 2;

パフォーマンスと運用面での考察

パフォーマンス比較

閉包テーブルの主なメリットは、深い階層構造を持つデータに対する検索性能です：

検索性能
- 隣接リスト: O(n) where n = depth
- 閉包テーブル: O(1)
ストレージ要件
- 隣接リスト: O(n) where n = nodes
- 閉包テーブル: O(n²) worst case

運用面での考慮点

データ整合性の維持
- トリガーやストアドプロシージャを使用してパス情報を自動管理
- トランザクション管理の重要性
バックアップと復元
- パス情報の整合性確認が重要
- 復元時の順序考慮
パフォーマンスチューニング
- インデックス戦略の重要性
- キャッシュの活用

まとめ

閉包テーブルは、以下のような場合に特に有効です：

深い階層構造を持つデータを扱う
階層の全パスを頻繁に取得する必要がある
パフォーマンスが重要な要件である

一方で、実装の複雑さやストレージ要件の増加というトレードオフがあります。プロジェクトの要件や規模に応じて、適切なモデルを選択することが重要です。

参考資料