ネストセット（Nested Set）徹底解説：階層データを高速に読み取る設計と実装ガイド

ネストセット（Nested Set）とは

ネストセット（Nested Set、または「修正前順序木走査（Modified Preorder Tree Traversal）」）は、階層データ（ツリー構造）をリレーショナルデータベースで効率的に読み出すためのデータモデルの一つです。各ノードに「left（lft）」「right（rgt）」という2つの整数値を割り当て、ツリー全体の親子・祖先関係をこの数値の範囲比較で表現します。読み取り（特にサブツリーの取得や祖先・子孫の一括取得）に優れる一方で、挿入・削除・移動などの書き込み操作には範囲更新が必要になるためコストがかかります。

基本概念と番号付けのルール

• ツリーを深さ優先で走査し、訪問した順に連続した整数を割り当てます。各ノードは訪問時にlftを、サブツリーをすべて訪問し終えて戻る時にrgtを持ちます。
• 親ノードのlftは子ノードのlftより小さく、親のrgtは子のrgtより大きくなります。よって「ノードAがノードBの祖先である」 ⇔ (B.lft BETWEEN A.lft AND A.rgt)
• 葉（子を持たないノード）は通常 rgt = lft + 1 を持ちます。
• ノード数nに対し、lft/rgtは1から2nまでの連続値が割り当てられるのが典型です（ただしギャップを持たせることもあります）。

典型的なテーブル設計

シンプルな例：

CREATE TABLE tree (
  id INT PRIMARY KEY,
  name VARCHAR(255),
  lft INT NOT NULL,
  rgt INT NOT NULL,
  /* 必要に応じて他の属性 */
  INDEX(lft),
  INDEX(rgt)
);

よく使うクエリ例（読み取り）

ネストセットの強みは読み取りクエリが単純で高速に書けることです。以下は代表的なSQL。

• あるノードのサブツリー（自身を含むすべての子孫）を取得：

  
  SELECT * 
  FROM tree 
  WHERE lft BETWEEN :parent_lft AND :parent_rgt 
  ORDER BY lft;
      

• あるノードの祖先一覧（ルートから直上の親へ）を取得：

  
  SELECT parent.* 
  FROM tree AS parent 
  WHERE :node_lft BETWEEN parent.lft AND parent.rgt 
  ORDER BY parent.lft;
      

• ノードの深さ（階層レベル）を取得（自己を含む祖先数から算出）：

  
  SELECT node.id, node.name, (COUNT(parent.id) - 1) AS depth
  FROM tree AS node
  JOIN tree AS parent
    ON node.lft BETWEEN parent.lft AND parent.rgt
  GROUP BY node.id
  ORDER BY node.lft;
      

• 子孫ノードの個数（自身を除く）：

  
  SELECT (rgt - lft - 1) / 2 AS descendant_count
  FROM tree
  WHERE id = :node_id;
      

挿入・削除・移動の基本アルゴリズム（書き込み操作）

書き込みは既存のlft/rgt値をシフトする必要があるため複数のUPDATEを伴います。トランザクションと適切なロックが必須です。

• ノードを親の最後の子として挿入する（親のrgtを挿入位置とする）：

  
  BEGIN;
  -- 挿入位置 p = parent.rgt
  UPDATE tree SET rgt = rgt + 2 WHERE rgt >= p;
  UPDATE tree SET lft = lft + 2 WHERE lft > p;
  INSERT INTO tree (name, lft, rgt) VALUES ('new', p, p + 1);
  COMMIT;
      

  注意：同時実行がある場合、rgt/lftの更新範囲で競合するためロックや適切な隔離レベルが必要です。

• サブツリー削除：

  
  BEGIN;
  SET @width = :node_rgt - :node_lft + 1;
  DELETE FROM tree WHERE lft BETWEEN :node_lft AND :node_rgt;
  UPDATE tree SET lft = lft - @width WHERE lft > :node_rgt;
  UPDATE tree SET rgt = rgt - @width WHERE rgt > :node_rgt;
  COMMIT;
      

• サブツリーの移動は最も複雑です。一般的には、
  1. 移動元の幅（width）を計算
  2. 一時的に負の値を利用して衝突を回避しながらlft/rgtを更新
  3. 移動先の空きを作る（rgt/lftをシフト）
  4. 負の値を正に戻す

  具体的実装はバグが生じやすく、テストとトランザクションが必須です。大規模な移動は一度エクスポート→再構築する方が確実な場合もあります。

長所と短所（実運用での判断材料）

• 長所
  • 一回のクエリでサブツリー全体や祖先一括を取得でき、高速（インデックスを効かせやすい）
  • 表示系（ツリー全展開、順序付き出力）に強い
• 短所
  • 挿入・削除・移動が範囲更新になるため書き込み性能が悪く、頻繁な変更に不向き
  • 同時更新の競合が発生しやすく、アプリケーション側でロック制御やトランザクション設計が必要
  • ノード数が非常に大きいと数値が溢れる可能性がある（bigintが必要になることも）

代替手法と比較

ネストセット以外にも階層データを扱う方法があり、用途に応じて選びます。

• 隣接リスト（Adjacency List）: 各ノードが parent_id を持つ最も素朴な方法。書き込みは簡単だが、子孫全取得は再帰クエリが必要。近年のDB（WITH RECURSIVE）で実用性が高まっている。
• クロージャテーブル（Closure Table）: すべての祖先-子孫ペアを別テーブルに保存する方式。読み取りは非常に高速で柔軟。書き込みはクロージャテーブルの更新が必要だが、部分更新に留められる場合が多い。
• マテリアライズドパス（Materialized Path）: パスを文字列（/root/parent/child）として保存。プレフィックス検索でサブツリー取得が可能。実装が簡単だが、文字列長の考慮やLIKE検索の効率化が課題。
• ネスト間隔モデル（Nested Intervals）: 有理数や文字列で間隔を表し、挿入時に再番号付け不要にする手法（実装はやや高度）。

実装時の注意点と運用のコツ

• トランザクションと適切な隔離レベル（例：SERIALIZABLEや行レベルロック）を用いる。MySQLではInnoDBのトランザクションを使い、更新範囲をロックする方針を検討する。
• 頻繁に更新がある場合はネストセットは避けるか、更新頻度をバッチ化して夜間に一括反映するなど工夫する。
• lft/rgt にインデックスを張る。範囲検索（BETWEEN）で有効に働くため、複合インデックス（lft,rgt）や個別インデックスを検討する。
• 大規模ツリーでは整数の上限に注意。深いツリーや多数ノードを扱うなら BIGINT を使う。
• 移動や再構築中に読み取りが必要なら、読み取り用のスナップショット（ビューやコピー）を用意する戦略を検討する。
• テストデータで大量の挿入・削除・移動を試し、パフォーマンスを計測する。最悪ケース（根に近い位置への挿入で全テーブル更新が走る）を想定する。

いつネストセットを選ぶべきか

次のような場合にネストセットは有用です。

• ツリー構造は比較的静的で、読み取り（ツリー表示、サブツリー取得、祖先列挙）が圧倒的に多いアプリケーション。
• 表示レイヤーでツリー全体や大きなサブツリーを頻繁に取得する必要があり、少ないクエリで大量の階層情報を取りたい場合。

逆に、頻繁にノードの移動や挿入削除が発生するシステム（コメントの頻繁な並び替えなど）には不向きです。

参考的な実装例（簡単なワークフロー）

実用的な流れの例：

• 読み取り重視：ネストセットで運用。lft/rgtに索引、読み取りクエリを最適化。
• 書き込みはAPIでシリアライズ（キューに入れる／排他ロック）して一括反映。
• 大量更新や移動が必要な場合は一時的に「隣接リスト」に切り替え、バッチでネストセットを再構築する運用も検討する（ツリーをエクスポート→DFSで再番号付け→インポート）。

まとめ

ネストセットは「読み取り最適化」のために優れた方法です。ルールは単純（lft/rgtの範囲比較）でクエリが直感的になるため、ツリー表示系では高い効果を発揮します。ただし、書き込み操作はコストが高く、並列更新や頻繁な変更を伴うケースでは別手法（隣接リスト＋再帰クエリ、クロージャテーブル、マテリアライズドパスなど）を検討すべきです。設計時には想定される読み書き比率、同時実行性、ツリーの最大サイズを踏まえて、最適な方式を選んでください。

参考文献

• Nested set model - Wikipedia
• Managing Hierarchical Data in MySQL — Mike Hillyer
• Closure table - Wikipedia
• Joe Celko, "Trees and Hierarchies in SQL for Smarties"（O'Reilly）
• MySQL Reference Manual — WITH (RECURSIVE)
• PostgreSQL Documentation — WITH Queries (Common Table Expressions)

投稿者プロフィール

エバープレイ編集部

最新の投稿

• IT2025.11.20MLP（多層パーセプトロン）完全解説：基礎構造・活性化関数・学習アルゴリズム・正則化・現代の役割と実践ガイド
• IT2025.11.20多層パーセプトロン（MLP）入門から実務まで：構造・学習・正則化・普遍近似定理を徹底解説
• IT2025.11.20人工ニューラルネットワーク（ANN）完全ガイド：基礎から応用まで、構造・学習・アーキテクチャ・評価・実践を網羅
• IT2025.11.20機械学習データラベリングの実務ガイド：手法・ツール・品質管理・コストと課題を網羅