Posted inMySQL

MySQLにおける階層データ管理：「カテゴリツリー」でサーバーをダウンさせないために

MySQL tutorial - IT technology blog
MySQL tutorial - IT technology blog

カテゴリツリーがシステムリソースを「食いつぶす」とき

午前2時、アラートが鳴り止みませんでした。監視ダッシュボードを見ると、データベースのCPU使用率が100%に跳ね上がり、そのまま固まっていました。調査したところ、製品カテゴリを取得するクエリが「無限に」実行されていることが判明しました。

当時、システムはAdjacency List（単純な親子モデル）を採用していました。カテゴリツリーが15階層、レコード数が2万件を超えたとき、再帰クエリ（Recursive CTE）がサーバーの限界を使い果たしてしまったのです。これは、初期段階でデータ構造の選択を誤ったことによる手痛い教訓となりました。

以下に、実際のトラブル対応から学んだ、MySQLでツリー形式のデータを管理するための3つの一般的な手法を紹介します。

1. Adjacency List（隣接リスト）：シンプルだが限界が早い

これは、多くの開発者が最も直感的に思いつく方法です。親レコードのIDを指す parent_id カラムを追加するだけです。

構成例

CREATE TABLE categories (
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(255) NOT NULL,
    parent_id INT DEFAULT NULL,
    INDEX (parent_id),
    FOREIGN KEY (parent_id) REFERENCES categories(id)
);

実務的な評価

  • メリット: ノードの追加や移動が非常に高速です。parent_id を1つ更新するだけで済みます。
  • デメリット: ツリー全体を取得するクエリのコストが非常に高いです。MySQL 8.0未満では、アプリケーション側で再帰処理を行う必要があります。MySQL 8.0以降はCTE（共通テーブル式）でサポートされていますが、ツリーが深くなるとパフォーマンスは急激に低下します。

CTEを使用したクエリ例 (MySQL 8.0+)

WITH RECURSIVE category_path (id, name, path) AS (
    -- 基本ケース：ルートノードの取得
    SELECT id, name, name as path
    FROM categories
    WHERE parent_id IS NULL
    UNION ALL
    -- 再帰ステップ：子ノードの結合
    SELECT c.id, c.name, CONCAT(cp.path, ' > ', c.name)
    FROM category_path cp JOIN categories c
    ON cp.id = c.parent_id
)
SELECT * FROM category_path;

2. Nested Set Model（入れ子集合モデル）：読み込みに最適、書き込みは「悪夢」

このモデルは parent_id を使いません。代わりに、lft (left) と rgt (right) という2つの値で子ノードを包含します。各ノードを「箱」に見立て、子ノードは大きな箱の中に収まる小さな箱だと想像してください。

仕組み

あるノードの子孫をすべて取得するのに再帰は不要です。シンプルな BETWEEN 句だけで取得できます。

SELECT * FROM nested_categories 
WHERE lft BETWEEN 10 AND 25 
ORDER BY lft ASC;

メリットとデメリット

  • メリット: 読み込み速度が驚異的に速いです。ニュースサイトのカテゴリや、あまり変更されない製品カタログなどに非常に適しています。
  • デメリット: 書き込み操作が非常に重いです。途中にノードを1つ挿入するだけで、MySQLはテーブルの半分近くの lft および rgt 値を更新しなければならないことがあります。10万行規模のテーブルでは、1回の挿入で数秒間テーブル全体がロックされる可能性があります。

3. Closure Table（閉包テーブル）：バランスの取れたモダンな解決策

これは私が大規模プロジェクトで優先的に採用する手法です。メインテーブルに関係性を保存するのではなく、ノード間のすべての経路（パス）を保存するための別テーブルを切り出します。

構成例

CREATE TABLE category_hierarchy (
    ancestor INT NOT NULL, -- 先祖ノードのID
    descendant INT NOT NULL, -- 子孫ノードのID
    path_length INT NOT NULL, -- 階層の深さ
    PRIMARY KEY (ancestor, descendant)
);

なぜ Closure Table を使うのか？

読み込みの速さと、書き込みの許容できるパフォーマンスを両立させています。ノード1のすべての子孫を見つけるには、関連テーブルを結合するだけです。ツリーの枝ごと移動させるのも、関連テーブルに対して数行の DELETE と INSERT を実行するだけで完了します。

  • メリット: 最も柔軟性が高く、1つのノードが複数の親を持つ（多重階層）構造もサポート可能です。
  • デメリット: ストレージ容量を消費します。10階層の深さを持つツリーの場合、1つの新規レコード作成で関連テーブルに11行のデータが生成される可能性があります。

パフォーマンス比較表

評価項目 Adjacency List Nested Set Closure Table
ノードの追加 O(1) – 非常に速い O(n) – 非常に遅い O(log n) – 速い
サブツリーの取得 遅い（再帰が必要） 非常に速い 非常に速い
実装の複雑さ 低い 高い 中程度

実践的なアドバイス

完璧なモデルを探すのではなく、用途に最適なモデルを選んでください。シンプルなToDoアプリなら Adjacency List で十分です。毎日数百万ビューがあるEコマースシステムなら、枕を高くして眠るために Closure Table が最も安全な選択肢です。

あの午前2時のトラブルの際、私はサーバーを救うためにRedisを使ってツリー全体を一時的にキャッシュしました。その後、チームで3日かけて Closure Table へ完全に移行しました。結果は驚くべきものでした。CPU負荷は90%から10%以下に下がり、何より夜中に叩き起こされることがなくなったのです。

Share:
Tags: