階層構造の設計パターン：隣接リスト、経路列挙、閉包テーブルの使い分け【Laravel対応】

はじめに

何年かWEBシステム開発をしているほとんどの方は階層構造に触れたことがあるのではないでしょうか。そして、階層構造の要件を表現する際に頭を悩ませた経験がある方も少なくないでしょう。
最近私が関わった案件で階層構造を利用することになり、設計チームが頭を悩ませていたので本記事を執筆することにしました。
いざ自分が階層構造を設計する立場になったとき適切な階層構造を選択できるよう、本記事では主要な階層構造モデルの紹介と、それぞれの利点と欠点を比較します。
さらに、具体的なユースケースに基づいて最適な階層構造を選択するためのガイドラインを提供します。

階層構造の基本概念

階層構造とは、データが親子関係を持つツリー状の構造を指します。
一般的なユースケースには、組織の部門構造、ファイルシステムのディレクトリ構造、カテゴリとサブカテゴリの関係などがあります。

主要な階層構造モデルの紹介

以下の表に、主要な階層構造モデルとその概要を示します。

他にもネストセットモデル、束縛モデル、祖先カラムモデルや再帰的共通テーブル式などありますが、頻出度を理由に絞ってあります。
例えばネストセットモデルは初見だと理解と実装の難易度が高めなので、保守性的な意味でほぼ採用することはありません。（私が関わってきたプロジェクトでは）
ちなみにほぼ変更がないとか、変更があっても1年に1回とかで、かつ、大規模な階層構造はJSONでDBかファイルに保持しとけばいいと思ってます。

隣接リストモデル (Adjacency List Model)

概要

隣接リストモデルでは、各ノードが親ノードのIDを持ちます。このモデルは非常にシンプルで直感的にも理解しやすいです。
tableA.parent_id = tableB.id と連結を表現でき、体感ではWEBシステム開発で最も頻出の階層構造です。

図

1
├── 2 (parent_id = 1)
└── 3 (parent_id = 1)
           ├── 4 (parent_id = 3)
           └── 5 (parent_id = 3)

利点

• シンプルで理解しやすい: データベース設計が簡単で、ノードの追加や削除も容易です。
• クエリが簡単: 直接の親子関係を取得するクエリが簡単です。

欠点

• 階層全体の取得が複雑: 再帰的なクエリを利用するため、パフォーマンス低下の可能性があります。

ユースケース

• 小規模な階層構造: 階層の深さが浅く、ノード数が少ない場合に適しています。
• 頻繁な更新が必要な場合: ノードの追加や削除が頻繁に行われる場合に有効です。
• 単一階層の取得: 子要素をAPIで問い合わせて開くタイプのUIにおいて実装が手軽です。

実際のWEBシステムでの利用例

• ブログのコメントシステム: コメントとその返信の関係を管理するのに適しています。
• フォーラムのスレッド管理: スレッドとその返信の階層構造を管理するのに適しています。
• 組織の部門構造: 部門とその下位部門の関係を管理するのに適しています。

ORMで表現（Laravel Eloquentの場合）

モデルの定義

まず、Categoryモデルに親子関係を定義するメソッドを追加します。

class Category extends Model
{
    public function parent()
    {
        return $this->belongsTo(Category::class, 'parent_id');
    }

    public function children()
    {
        return $this->hasMany(Category::class, 'parent_id');
    }

    public function childrenRecursive()
    {
        return $this->children()->with('childrenRecursive');
    }
}

特定のノードの親要素を取得

$parent = Category::find($categoryId)->parent;

特定のノードの子要素を取得

$children = Category::where('parent_id', $categoryId)->get();

特定のノードから3階層分取得

$categories = Category::with(['children.children.children'])
    ->where('id', $categoryId)
    ->get();

全階層を取得

$categories = Category::with('childrenRecursive')->where('id', $categoryId)->get();

特定のノードを別のノードに紐づくよう更新

$category = Category::find($categoryId);
$category->parent_id = $newParentId;
$category->save();

特定のノードを削除

ノードを削除する際には、そのノードに紐づく子ノードも一緒に削除する必要があります。

$category = Category::find($categoryId);


if ($category) {
    // 子ノードを再帰的に削除
    $category->childrenRecursive()->each(function ($child) {
        $child->delete();
    });


    // 自身を削除
    $category->delete();
}

上記のコードでは、childrenRecursiveメソッドを使用して子ノードを再帰的に取得し、それらを削除しています。その後、対象のノード自身を削除します。

経路列挙モデル (Path Enumeration Model)

概要

経路列挙モデルでは、各ノードがルートからそのノードまでのパスを保持します。パスは通常、文字列として保存されます。

図

1
├── 1/2
└── 1/3
             ├── 1/3/4
             └── 1/3/5

利点

• 階層全体の取得が容易: LIKE演算子を使用して部分木（特定のノードをルートとするサブツリー）を簡単に取得できます。
• クエリが効率的: 部分木の取得が非常に効率的です。

欠点

• パスの更新が必要: ノードの追加や削除時にパスの更新が必要です。図で言うところの 1/3 が 1/3_ に変更された場合、子要素は 1/3_/4, 1/3_/5 に更新される必要があります。

ユースケース

• 読み取りが多い場合: 階層全体や部分木の読み取りが頻繁に行われる場合に適しています。
• 階層が深い場合: 階層の深さが深い場合でも効率的にクエリを実行できます。

実際のWEBシステムでの利用例

• カテゴリ管理システム: 商品カテゴリなどフォルダ構造の管理に適しています。
• ファイルシステムのディレクトリ構造: ディレクトリとそのサブディレクトリの関係を管理するのに適しています。
• メニュー管理システム: ウェブサイトのメニューとサブメニューの階層構造を管理するのに適しています。

ORMで表現（Laravel Eloquentの場合）

特定のノードの親要素を取得

$category = Category::find($categoryId);
$pathParts = explode('/', $category->path);  // '/'で分割した配列の数=階層の要素数
$parentId = $pathParts[count($pathParts) - 2];  // 階層の要素数-1が$category。階層の要素数-2が$categoryの親要素
$parent = Category::find($parentId);

特定のノードの子要素を取得

$children = Category::where('path', 'LIKE', "$path/%")->get();

特定のノードから3階層分取得

$categories = Category::where('path', 'LIKE', "$path/%")
    ->whereRaw('LENGTH(path) - LENGTH(REPLACE(path, "/", "")) <= 3')
    ->get();

全階層を取得

$categories = Category::where('path', 'LIKE', "%")->get();

特定のノードを別のノードに紐づくよう更新

$oldPath = $oldParent->path;
$newPath = $newParent->path;
Category::where('path', 'LIKE', "$oldPath/%")
    ->update(['path' => DB::raw("REPLACE(path, '$oldPath', '$newPath')")]);

特定のノードを削除

ノードを削除する際には、そのノードに紐づく子ノードも一緒に削除する必要があります。

$category = Category::find($categoryId);


if ($category) {
    // 子ノードを再帰的に削除
    Category::where('path', 'LIKE', "$category->path/%")->delete();


    // 自身を削除
    $category->delete();
}

閉包テーブルモデル (Closure Table Model)

概要

閉包テーブルモデルでは、全てのノード間の親子関係を別のテーブルで管理します。このテーブルには、各ノードの祖先と子孫の関係が保存されます。

図

1
├── 2
└── 3
            ├── 4
            └── 5

閉包テーブルモデルのレコード

Closure Table:

ancestor | descendant | depth

------------|----------------|------

1              | 1                  | 0

1              | 2                  | 1

1              | 3                  | 1

1              | 4                  | 2

1              | 5                  | 2

2              | 2                  | 0

3              | 3                  | 0

3              | 4                  | 1

3              | 5                  | 1

4              | 4                  | 0

5              | 5                  | 0

ancestorは先祖、descendantは子孫、depthは深さという意味です。

利点

• 階層全体の取得が効率的: 階層全体や部分木の取得が非常に効率的です。
• 柔軟なクエリ: 任意のノード間の関係を簡単にクエリできます。

欠点

• 挿入や削除が複雑: ノードの追加や削除時に閉包テーブルモデルの更新が必要です。

ユースケース

• 大規模な階層構造: ノード数が多く、階層が深い場合に適しています。
• 複雑なクエリが必要な場合: 任意のノード間の関係を頻繁にクエリする場合に有効です。

実際のWEBシステムでの利用例

• アクセス制御リスト（ACL）: ユーザーと権限の階層構造を管理するのに適しています。
• 製品カテゴリの管理: 大規模な製品カテゴリの階層構造を管理するのに適しています。
• 組織の階層構造: 大規模な組織の部門やチームの階層構造を管理するのに適しています。

ORMで表現（Laravel Eloquentの場合）

モデルの定義

まずはCategoryモデルとCategoryClosureモデルの定義を示します。

class Category extends Model
{
    public function ancestors()
    {
        return $this->belongsToMany(Category::class, 'category_closure', 'descendant', 'ancestor')
                             ->withPivot('depth');
    }


    public function descendants()
    {
        return $this->belongsToMany(Category::class, 'category_closure', 'ancestor', 'descendant')
                             ->withPivot('depth');
    }
}

class CategoryClosure extends Model
{
     protected $fillable = ['ancestor', 'descendant', 'depth']; // この名前のカラムがある、という理解でOK
}

特定のノードの親要素を取得

$parent = Category::whereHas('ancestors', function ($query) use ($categoryId) {
    $query->where('descendant', $categoryId)->where('depth', 1);
})->first();

特定のノードの子要素を取得

$children = Category::whereHas('descendants', function ($query) use ($categoryId) {
    $query->where('ancestor', $categoryId)->where('depth', 1);
})->get();

特定のノードから3階層分取得

$categories = Category::whereHas('descendants', function ($query) use ($ancestorId) {
    $query->where('ancestor', $ancestorId)->where('depth', '<=', 3);
})->get();

全階層を取得

$category = Category::find($categoryId);

$categories = $category->descendants;

特定のノードを別のノードに紐づくよう更新

// まず、古い関係を削除

CategoryClosure::where('descendant', $descendantId)->delete();



// 次に、新しい関係を挿入

$supertree = CategoryClosure::where('descendant', $newAncestorId)->get();

$subtree = CategoryClosure::where('ancestor', $descendantId)->get();



foreach ($supertree as $super) {

    foreach ($subtree as $sub) {

        CategoryClosure::create([

            'ancestor' => $super->ancestor,

            'descendant' => $sub->descendant,

            'depth' => $super->depth + $sub->depth + 1
        ]);
    }
}

特定のノードを削除

$category = Category::find($categoryId);


if ($category) {
    // 子孫ノードを再帰的に削除
    $descendants = Category::whereHas('ancestors', function ($query) use ($categoryId) {
        $query->where('ancestor', $categoryId);
    })->get();


    
    foreach ($descendants as $descendant) {

        $descendant->delete();
    }



    // 自身を削除
    $category->delete();
    CategoryClosure::where('descendant', $categoryId)->delete();
}

エッジケースの考慮

隣接リストモデル

• 非常に深い階層: 再帰的なクエリを利用するため、パフォーマンス低下の可能性があります。データベースの再帰的クエリの最適化が必要です。
• 大量のノード: ノード数が多い場合、クエリのパフォーマンス低下の可能性があります。

経路列挙モデル

• パスの長さ: 階層が深くなるとパスの長さが増加し、インデックスのサイズが大きくなります。これにより、インデックスのメモリ使用量が増加し、クエリのパフォーマンスに影響を与えることがあります。
• パスの更新: ノードの移動や削除時にパスの更新が必要で、これが頻繁に発生する場合はパフォーマンスが低下します。

閉包テーブルモデル

• 大量のノード: ノード数が多い場合、閉包テーブルモデルのサイズが大きくなり、挿入や削除においてパフォーマンス低下の可能性があります。
• 複雑なクエリ: 非常に複雑なクエリが必要な場合、クエリの最適化が難しくなります。例えば、特定のノードのすべての兄弟ノードを取得するクエリや、特定の深さのノードのみを取得するクエリなどが挙げられます。

例: 特定のノードのすべての兄弟ノードを取得するクエリ

SELECT sibling.*

FROM categories AS sibling

JOIN category_closure AS parent_closure ON sibling.id = parent_closure.descendant

JOIN category_closure AS target_closure ON parent_closure.ancestor = target_closure.ancestor

WHERE target_closure.descendant = :targetId

  AND parent_closure.depth = 1

  AND sibling.id != :targetId;

このクエリは、特定のノードのすべての兄弟ノードを取得するために、閉包テーブルモデルを2回結合しています。このようなクエリは、閉包テーブルモデルのサイズが大きくなるとパフォーマンス低下の可能性があります。

補足

Eager LoadとLazy Loadについて

一般的なORMフレームワークには、関連データを効率的に取得するための2つの主要な手法があります。
それが「Eager Load」と「Lazy Load」です。

Eager Load

概要

Eager Loadは、最初のクエリで関連データを一括して取得する手法です。これにより、N+1問題を回避できます。
N+1問題はリレーション先のレコードを複数表示する場合に頻出する問題で、「この大量のSQLログはなんだろう」という経験をした方も多いのではないでしょうか。
N+1問題についての詳しい解説はこの記事の題材と少しずれるので、他の記事におまかせします。

例

// Eager Loadを使用して親カテゴリとその子カテゴリを一括取得


$categories = Category::with('children')->get();

利点

• パフォーマンス向上: 関連データを一括して取得するため、データベースへのクエリ回数が減少し、パフォーマンスが向上します。
• N+1問題の回避: N+1問題を回避することで、データベースへの過剰なクエリを防ぎます。

欠点

• メモリ使用量の増加: 一度に大量のデータを取得するため、メモリ使用量増加の可能性があります。

用途

• 関連データが必要な場合: 関連データを一度に取得する必要がある場合に適しています。
• パフォーマンスが重要な場合: クエリ回数を減らしてパフォーマンスを向上させたい場合に有効です。

Lazy Load

概要

Lazy Loadは、関連データが実際にアクセスされたときに初めて取得する手法です。これにより、必要なデータだけを取得できます。

例

// Lazy Loadを使用して親カテゴリを取得し、その後に子カテゴリを取得
$category = Category::find($categoryId);
$children = $category->children; // このタイミングで子要素を取得するSQLが実行される

利点

• メモリ効率: 必要なデータだけを取得するため、メモリ使用量が抑えられます。
• 柔軟性: 必要なときに必要なデータだけを取得できるため、柔軟なデータ取得が可能です。

欠点

• N+1問題の発生: 関連データを個別に取得するため、N+1問題が発生しやすいです。
• パフォーマンス低下: 多数の関連データを個別に取得する場合、クエリ回数が増加し、パフォーマンス低下の可能性があります。

用途

• 関連データが不要な場合: 関連データを利用しない場合もあるパターンに適しています。
• メモリ使用量を抑えたい場合: メモリ効率を重視する場合に有効です。

用途に対する適正のマトリクス表

以下のマトリクス表に、各階層構造モデルが特定の操作に対してどれだけ適しているかを示します。

• ◎: 非常に適している
• ○: 適している
• △: あまり適していない

まとめ

例えば、頻繁な更新が必要な場合は隣接リストモデルが適しており、読み取りが多い場合は経路列挙モデルが適しています。閉包テーブルモデルは大規模な階層構造や複雑なクエリが必要な場合に有効です。
それぞれのモデルには利点と欠点があります。
具体的なユースケースや要件に応じて適切なモデルを選択する際の助けになれば幸いです。