Materialized Path（マテリアライズドパス）で階層データを扱う方法：メリット・欠点・SQL実例（PostgreSQL ltree対応）
エバープレイ編集部Materialized Path とは — 概要
Materialized Path（マテリアライズドパス）は、データベース上でツリー構造（階層構造）を表現する手法の一つです。各ノードにそのノードまでのパス（祖先のIDを連結した文字列）をそのまま保存することで、祖先・子孫の検索や順序付けを容易にします。典型的には「1/4/5」や「/1/4/5/」のような文字列で保存します。
なぜ使うのか（背景）
- Adjacency List（親IDのみを保存）だと全子孫を取得するために再帰クエリ（多段の自己結合や再帰CTE）が必要になる。
- Nested Set（左右番号を振る方式）は読み取りでの部分木抽出が高速だが、挿入・移動・削除時に番号の再計算が必要で実装・保守が複雑。
- Materialized Pathは、読み取り（特に「あるノードの全子孫を取得」）が簡単にでき、実装が比較的単純で可搬性が高い、という利点があります。
表現方法（パスのフォーマット）
一般的な表現例：
- 区切り文字をスラッシュにする： "1/4/5"（IDをスラッシュで繋ぐ）
- 先頭/末尾にスラッシュを付ける：" /1/4/5/ " — LIKE マッチングで衝突を避けやすい
- IDの代わりにUUIDや名前を使うことも可能（ただし長さとエスケープに注意）
重要なのは一貫した区切り文字を使い、IDや区切り文字が衝突しないようにエスケープルールを決めておくことです。
基本的なクエリ例（SQL）
ここではパスを「1/4/5」のようにスラッシュで区切った文字列（先頭・末尾にスラッシュは付けない）として扱った例を示します。
子孫（全階層）の取得：
SELECT * FROM nodes WHERE path LIKE '1/4/%' ORDER BY path;
深さ（ノードの階層レベル）の計算（汎用SQL）：
SELECT id, path, (LENGTH(path) - LENGTH(REPLACE(path, '/', '')) ) + 1 AS depth FROM nodes;
（スラッシュ数 + 1 を深さとする）
直下の子（直系のみ）の取得：
-- 親の深さを計算しておく（parent_path = '1/4'） SELECT * FROM nodes WHERE path LIKE '1/4/%' AND (LENGTH(path) - LENGTH(REPLACE(path, '/', '')) ) + 1 = (<parent_depth> + 1) ORDER BY path;
あるノードの祖先の取得（パスが親のプレフィックスになっているものを探す）：
-- target_path = '1/4/5' SELECT * FROM nodes WHERE '1/4/5' LIKE CONCAT(path, '%') ORDER BY LENGTH(path);
ただしこのクエリはパス列に対する前方一致（column LIKE constant）ではなく、定数に対するLIKEなので通常のインデックスが使われない点に注意する必要があります（後述）。
インデックスとパフォーマンス
Materialized Path のパフォーマンスは、保存方法とクエリの書き方、DBの機能に左右されます。
- 子孫検索（path LIKE 'prefix/%'）：path列が先頭固定のプレフィックス検索であるため、B-treeインデックスで加速できます（MySQL/InnoDB、PostgreSQL）。ただしパスに先頭に余分な文字（先頭スラッシュ）があるとインデックスが効かない場合があるので注意。
- 祖先検索（'target' LIKE CONCAT(path, '%') など）：この形だと通常のB-treeインデックスは使えません。祖先検索を頻繁に行う場合は、親IDを持たせる、または逆順パス（ルートからではなく葉からのパス）や補助列を持つなどの工夫が必要です。
- PostgreSQL の ltree 拡張：ltree 型を使うと階層検索専用の演算子や関数（nlevel、subpath、演算子 <@/@> 等）が利用でき、GIST/GIN インデックスで高速化できます（PostgreSQL ドキュメント参照）。
移動・挿入・削除時の振る舞い（メンテナンスコスト）
- 挿入：新規ノードは親のパス + '/' + 自分のID を作るだけで済むため簡単。
- 削除：ノードを削除するだけで良い場合は簡単。部分木ごと削除する場合は path LIKE の条件で一括削除可能。
- ノードの移動（親を変更する）やノードIDの変更：そのノード配下の全ての子孫ノードの path を更新する必要がある。大量の子孫がいると更新コスト（多量の UPDATE）が発生する。
Nested Set と比較すると、移動時の実装はシンプルですが、更新量が多くなり得る点は共通の課題です。更新頻度が低く読み取りが多いケースに向いています。
利点・欠点まとめ
- 利点
- 実装が比較的容易で可搬性が高い（標準SQLで実現可能）。
- 子孫の一括取得や順序付けが単純なLIKEや文字列ソートで実行できる。
- 階層の深さを文字列の長さや区切り数で容易に計算できる。
- 欠点
- ノード移動で子孫のパス全体を更新する必要があり、更新コストが高い場合がある。
- パス文字列が長くなりやすく、保存領域が増える（特にUUIDや長いラベルを使う場合）。
- 祖先検索や任意の中間ノードでの検索（部分一致ではない柔軟な検索）が非効率になりやすい。
- 区切り文字やIDに特殊文字が含まれるとエスケープ処理が必要。
実運用上の工夫・ハイブリッド運用例
- 親ID（parent_id）も併せて保存する：直近の親や親取得を高速化できる。祖先取得はパスで、親取得はparent_idで行える。
- 深さ（depth）を別カラムで保持する：直下の子の判定や階層表示が速くなる。
- パスを ltree（PostgreSQL）や配列（PostgreSQL の int[]）で保持する：専用演算子や関数で効率的に検索できる。
- ノードの並び順情報をパスに含める（例："1.0001/4.0003/5.0002"）：順序を安定して保持できるが、パス更新がさらに複雑になる。
- 大量の再配置がある場合は Closure Table（祖先・子孫の組を別テーブルで持つ方式）を併用すると、移動の粒度に応じて有利になることがある。
サンプルDDL（MySQL/PostgreSQL）
シンプルな例（VARCHARでパスを保存）：
CREATE TABLE nodes ( id INT PRIMARY KEY AUTO_INCREMENT, parent_id INT NULL, path VARCHAR(1024) NOT NULL, name VARCHAR(255), INDEX idx_path (path) -- prefix検索に効く );
PostgreSQL で ltree を使う例（専用型を利用）：
-- PostgreSQLで ltree 拡張を有効化 CREATE EXTENSION IF NOT EXISTS ltree; CREATE TABLE nodes ( id SERIAL PRIMARY KEY, parent_id INT, path ltree NOT NULL, name TEXT ); -- ltree用のインデックス（GIN/GIST） CREATE INDEX idx_nodes_path_gin ON nodes USING gin(path);
Materialized Path を選ぶべきケース
- 読み取り（特に「あるノード配下の全子孫を取得」）が多く、ツリーの構造変更（移動）が少ない用途。
- シンプルで可搬性の高い実装を望む場合（標準SQLで実装可能）。
- PostgreSQL の ltree 等の機能が使える環境であれば、効率的に実装できる。
注意点（実務での留意点）
- 区切り文字の選定とエスケープルールを明確にする（ID に区切り文字が含まれる可能性があるなら避ける）。
- 検索パターンによってインデックスの効き方が変わる点を理解する（prefix検索は速いが、逆方向の比較は遅い）。
- 移動・一括更新の際のトランザクション設計とロック競合に注意する。大量の UPDATE が発生する場合はバッチ化やオフピークでの処理を検討する。
- パス長が無制限に伸びる設計は避け、VARCHAR長やアプリ側での深さ制限を設けることを検討する。
まとめ
Materialized Path は「パス文字列をそのまま保存する」ことで階層クエリを単純にする手法です。実装は比較的容易で、子孫の取得や順序付けがシンプルに書ける一方、ノードの移動で子孫パスを一括更新する必要があり、祖先検索がインデックスを使いづらいなどのトレードオフがあります。PostgreSQL の ltree のような専用サポートがあればさらに有利に使えるため、利用するDBとクエリパターン（読み書きの比率、移動頻度等）を踏まえて選択するのが良いでしょう。
参考文献
- PostgreSQL ドキュメント: ltree モジュール
- Mike Hillyer: Managing Hierarchical Data in MySQL
- Wikipedia: Tree (data structure)
- Bill Karwin: Adventures in SQL: Hierarchical Data
投稿者プロフィール
