隣接リストではなく閉包テーブルで組織表作ってみた

はじめに

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

サンプルデータ

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

閉包テーブルモデル

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

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;

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

パフォーマンス比較

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

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

運用面での考慮点

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

まとめ

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

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

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

参考資料

• Closure Table Pattern
• SQL Antipatterns