what is this?
テーブル設計の際に、木構造のデータを表現する方法をメモとしてまとめたもの
assumption
- Mysql 5.7.37
木構造とは?
こんなやつ
- ノード 木の結節点
- ルートノード 木の始点となるノード(treeはルートノードを一つしか持たない)
- リーフノード 自分よりも下位のノードを持たない「終着点」のノード
- 内部ノード 中間に位置するノード
- 経路(path) ノードからノードへの道筋
隣接リストモデル(ナイーブツリー)
入れ子集合モデル
- ノードを点ではなく、円として捉える
- 座標を持たせる
- 座標の絶対値が重要ではなく、包含関係であるという相対的な関係性が表現されていればよい
- 検索が得意
- 更新が苦手
検索
- ルートノードを取得するクエリ
SELECT * FROM role_relation AS rr WHERE rr.left_end = 1 ;
- リーフノードを取得するクエリ
SELECT * FROM role_relation AS nleaf WHERE NOT EXISTS (SELECT * FROM role_relation AS leaf WHERE leaf.left_end > nleaf.left_end AND leaf.right_end < nleaf.right_end ) ;
- ツリーの深さを求めるクエリ
SELECT children.`role`, COUNT(parent.`role`) AS 深さ FROM role_relation AS parent INNER JOIN role_relation AS children ON children.left_end BETWEEN parent.left_end AND parent.right_end GROUP BY children.`role` ;
更新
- 円の数が増えれば増えるほど、更新する機会が多ければ多いほど負荷が高まる
- 削除する場合はデータが歯抜けになっていても、包含関係が表現されていれば良いので比較的楽
- 座標の値を実数まで含めれば更新の際に座標をずらす必要がなくなる(入れ子区間モデル)
上記画像の問題は、下記画像のように実数を用いることで整数と整数の間に無限にノードを追加することができる。 つまり、ノードを追加するたびに隣接するノードの座標をずらす必要がなくなる。
ただし、DBの制約上無限ではないため、いづれリソースは枯渇する。
DBの性能向上によってこの制約を過度に意識する必要がなくなれば、入れ子区間モデルを採用するのが木構造をRDBで表現するのに最も良いのでは?
閉包テーブルモデル(クロージャーテーブルモデル)
pending...
経路列挙モデル
pending....