木構造のデータを扱ういつもと違うアプローチ

アイデア自体はかなり昔にどこかのコラムで見たことがあり、頭の隅に置いていたのだが、上記リンクではかなり詳しく説明されていたのでまじめに読んでみた。

今まで、ここでいう「隣接リストモデル」でしか木構造データを扱う術を知らなかったのだが、

のような特性を持つシステムでは、ここで紹介された方法を使うメリットがあるのではないかと思った。

要約すると以下のような感じ。

広く使われている「親項目へのポインタを保持する」方法で木構造を表す方式を「隣接リストモデル」と呼ぶ。
ここで紹介する方法は「入れ子集合モデル」と呼び、要素の包含関係で木構造を表す。
- 各要素は left, right の項目を持ち、right > left の関係を持つ。
- ある要素に着目したとき、left, right の範囲を包含する要素が親に相当する。

　→ 親.left < 子.left < 子.right < 親.right の関係が成立する

ざっと読んでみて、以下の特徴があるみたい。

問い合わせに関する要件は、ほとんどSQL一発で実行可能。
- 隣接リストモデルは、木構造を「たどる」操作が必要なため、Oracleの階層問い合わせのようなSQL拡張がないと、プログラムでループを組む必要がある。
- あるノードに対し、「子が何件あるか」の検索は隣接リストモデルより圧倒的有利。
- ただし、直接の親、子を求めたり、「木をたどる」検索は隣接リストモデルより複雑になる。

ノードの追加・更新・削除は、隣接リストモデルより少し複雑になる。
- 慣れれば大したことないと思うのだが、サンプルで紹介されているSQLが理解するのに少し時間がかかる。
- 追加、削除を繰り返すと left, right の値が歯抜けになってしまうので正規化を行う必要がある。(歯抜けでも支障はないのだけど)