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


## はじめに

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

## サンプルデータ

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

```mermaid
graph TD
    A[会社全体] --> B[営業部]
    A --> C[技術部]
    A --> D[管理部]
    B --> E[営業1課]
    B --> F[営業2課]
    C --> G[開発1課]
    C --> H[開発2課]

```

### 閉包テーブルモデル

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

```sql
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テーブルのデータ

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

```

### department_pathsテーブルのデータ

```sql
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課

```

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

```sql
-- 営業部の直接の子部署を取得
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;

```

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

### 隣接リストモデル

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

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

```

### メリット

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

### デメリット

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

## 実装例

### 基本的な操作

### 部署の追加

```sql
-- 部署の追加（自己参照も含める）
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;

```

### 階層構造の取得

```sql
-- 特定部署の全ての子部署を取得
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](https://www.slideshare.net/billkarwin/models-for-hierarchical-data)
- [SQL Antipatterns](https://pragprog.com/titles/bksqla/sql-antipatterns/)