RDBで階層構造
今後も探してしまいそうなのでメモ。
代表的なところで、以下の3モデルがあるが、MySQLなら経路列挙モデルが良いらしい。以下、コピペ。
- 隣接リストモデル
- 入れ子集合モデル
- 経路列挙モデル
それぞれのノード(階層データを構成する個々の要素)が親を保存しておきツリー構造をたどることによりデータ構造を表現します。
Oracleの階層問い合わせのようにSQL拡張がない場合(MySQLにはありません)は、別途プログラム等でループを組む必要がある場合があり、パフォーマンスが良くありません。
比較的理解しやすいですがMySQLで利用するには用途が限られます。
ノードを円と見なし親子関係を左右の番号を使用し円の包含関係として捉える事によりデータ構造を表現します。
検索に関しては隣接リストモデルと違い圧倒的有利であるが、直接の親・子やツリー構造をたどるのは複雑になります。
また、親子関係を左右の番号が追加、削除を繰り返すことにより歯抜けになります。(歯抜けが気持ち悪ければ正規化が必要)
構造は面白いが理解しづらくパフォーマンスが良くないところが見られますが、MySQLでも利用できます。
各ノードに絶対パスをデータとして保存しデータ構造(UNIXのファイルシステムやURLの構造にそっくり)を表現します。
ノード自身のレコードに親子関係がパスとして含まれているので、SQL文が簡素になります。
また、パスは一意なりますし、MySQLでも正規表現を扱えるようになりましたので、極めて高い親和性と高いパフォーマンスが望めます。
MySQLで利用するには、この経路列挙モデルが一番親和性が高いように思います。
経路列挙モデルでOK
[参考サイト]
RDBで階層構造を扱う方法
MySQLで階層化データを使うには
経路列挙モデル(準備編):MySQLで階層化データを使う
返信
コメントを投稿するにはログインしてください。