ネスト集合モデル（Nested Set Model）とは？SQL実例・挿入・削除・移動のアルゴリズムと運用上の注意点
エバープレイ編集部ネスト集合モデル（Nested Set Model）とは
ネスト集合モデル（Nested Set Model）は、リレーショナルデータベース上で階層構造（木構造）を効率的に検索するためのデータ表現方法の一つです。Joe Celko が提唱・普及させた「Modified Preorder Tree Traversal（修正版前順走査）」として知られる手法で、各ノードに「左（lft）」「右（rgt）」という数値を付与し、これらの値の大小関係で親子関係・部分木を表現します。
基本概念と仕組み
ネスト集合モデルでは、ツリーを前順（preorder）で走査して、訪問順に連続する整数を割り当てます。各ノードは訪問時に「lft」を、戻るときに「rgt」を割り当てられます。例：
- ルートノードに lft=1, rgt=全体サイズ
- 任意ノードの部分木に含まれる全ノードは、その親ノードの lft と rgt の間に入る（親.lft < 子.lft && 子.rgt < 親.rgt）
この性質により、単一のレンジ条件（BETWEEN）で部分木の抽出や祖先の取得が高速に行えます。
テーブル設計の例
典型的なテーブル構造（カテゴリなど）：
CREATE TABLE categories (
id INT PRIMARY KEY AUTO_INCREMENT,
name VARCHAR(255),
lft INT NOT NULL,
rgt INT NOT NULL,
depth INT DEFAULT 0,
INDEX (lft),
INDEX (rgt)
);lft/rgt にインデックスを張ることで範囲検索が速くなります。depth（深さ）はクエリ負荷軽減のために保持することが多いですが、更新時に整合性を取る必要があります。
よく使うクエリ例
次のような操作が簡潔に書けます。
- 部分木（あるノードとその子孫）を取得：
SELECT * FROM categories WHERE lft BETWEEN @lft AND @rgt ORDER BY lft; - 祖先（親からルートまで）を取得：
SELECT * FROM categories WHERE lft < @node_lft AND rgt > @node_rgt ORDER BY lft; - 葉ノード（子を持たない）を取得：
SELECT * FROM categories WHERE rgt = lft + 1; - 部分木のノード数・子孫数：
-- ノード数（部分木に含まれるノード数） SELECT (rgt - lft + 1) / 2 AS node_count FROM categories WHERE id = @id; -- 子孫の数（自身を除く） SELECT (rgt - lft - 1) / 2 AS descendant_count FROM categories WHERE id = @id; - 深さを動的に計算（重いが一例）：
SELECT COUNT(parent.id) AS depth FROM categories AS node JOIN categories AS parent ON parent.lft < node.lft AND parent.rgt > node.rgt WHERE node.id = @id GROUP BY node.id;
挿入・削除・移動のアルゴリズム（原理）
ネスト集合モデルの欠点は、ノードの挿入・削除・移動で他の多くの行の lft/rgt 値を更新する必要がある点です。基本操作の流れは次のとおりです。
- 挿入（ある親の直下に新しい子を追加）：
- 親の rgt 位置を取得（親_rgt）
- 親_rgt 以上の rgt を持つ行を +2 する（空間を作る）
- 親_rgt より大きい lft を持つ行を +2 する
- 新しいノードを lft=親_rgt, rgt=親_rgt+1 で挿入
UPDATE categories SET rgt = rgt + 2 WHERE rgt >= @parent_rgt; UPDATE categories SET lft = lft + 2 WHERE lft > @parent_rgt; INSERT INTO categories (name, lft, rgt) VALUES ('New', @parent_rgt, @parent_rgt + 1); - 削除（部分木を削除）：
- 削除対象ノードの lft,rgt を取得し、幅 = rgt - lft + 1 を計算
- そのレンジ内の行を削除
- rgt > 削除範囲の行は rgt = rgt - 幅、lft > 削除範囲の行は lft = lft - 幅
DELETE FROM categories WHERE lft BETWEEN @lft AND @rgt; UPDATE categories SET lft = lft - @width WHERE lft > @rgt; UPDATE categories SET rgt = rgt - @width WHERE rgt > @rgt; - 移動（部分木を別の位置に移す）：
移動は「一旦切り取って別位置に挿入する」操作の組合せで、幅の計算、既存行のシフト、深さの差分補正など複数ステップを安全に行う必要があります。実装は複雑で、トランザクションとロックが必須です。
性能面と運用上の注意
- 読み取り（特に部分木の取得や祖先の取得）は高速で、単一のインデックス付き範囲検索で済むため多くの読み取り中心の用途に向きます。
- 挿入・削除・移動は多数の行の更新を伴うため、ノード数が多いとコストが高くなります。大量更新が頻繁に発生するアプリケーションには不向きです。
- 更新の整合性を保つため、必ずトランザクションで包み、必要に応じて適切なロック（テーブルロックや行ロック、アプリケーションレベルのミューテックス）を使用してください。特に並行挿入で競合すると lft/rgt の不整合が起きやすいです。
- lft/rgt に整数型を用いますが、ノード数が増えると値が大きくなるため型選定（INT/ BIGINT）には注意が必要です。
- 頻繁に深さ（depth）を参照するなら、depth を列として保持して更新時にメンテナンスすることでクエリを軽くできますが、これも更新コストの増加を意味します。
利点と欠点のまとめ
- 利点
- 部分木・祖先の検索が非常に高速で単純なSQLで済む。
- 木全体の順序（前順）が自然に保たれるため、ツリーを順序付きで出すのが容易。
- 欠点
- 挿入・削除・移動が多いケースでパフォーマンスが悪く、実装もやや複雑。
- 並列更新で整合性維持が難しい（トランザクション/ロックが必須）。
代替モデル（いつ使い分けるか）
用途や更新頻度によって他のモデルが適していることがあります。
- 隣接リスト（Adjacency List）: 各行が parent_id を持つ最も単純なモデル。ツリーが浅い／少数の再帰クエリしか行わない場合に便利。SQLで再帰が使えるDB（CTE）なら探索も可能。
- マテリアライズドパス（Materialized Path）: パス文字列（例: "1/4/7"）を保存する。移動は文字列操作だが、LIKE検索で部分木を探せる。文字列長管理が必要。
- クロージャテーブル（Closure Table）: すべての祖先-子孫ペアを保持する別テーブル。空間は多く取るが、挿入・削除の局所化が可能で検索も高速。更新は関係数次第で扱いやすい。
読み取り多めで木構造が比較的静的ならネスト集合モデルは有力な選択肢です。頻繁にノード移動・挿入削除が発生するならクロージャテーブルやマテリアライズドパスの方が保守性が高い場合があります。
ベストプラクティス
- lft/rgt にインデックスを張る。
- 更新処理（挿入・削除・移動）は必ずトランザクション内で行う。
- 高頻度の更新がある場合はアプリケーションレベルで更新シリアライズ（ミューテックス）するか、代替モデルの採用を検討する。
- 深さ（depth）を頻繁に参照するなら列として持つ。ただし更新時に全子孫の depth を更新する必要がある。
- 大規模データでは整数型（BIGINT 等）や適切な分割設計を検討する。
まとめ
ネスト集合モデルは「読み取りが高速」「単純なSQLで部分木や祖先を取得できる」ことが大きな利点ですが、「更新が重い」「並列更新の整合性確保が難しい」といったトレードオフがあります。用途（読み取り中心か更新中心か）、ツリーの大きさ、更新頻度を踏まえて選択するのが重要です。実装する場合はトランザクションと適切なロック、インデックス設計を徹底してください。
参考文献
- Nested set model — Wikipedia
- Managing Hierarchical Data in MySQL — Mike Hillyer
- Closure table — Wikipedia（代替モデルの紹介）
- Joe Celko, "SQL for Smarties"（Modified Preorder Tree Traversal の解説で知られる）
投稿者プロフィール
