Tech Hotoke Blog

IT観音とは私のことです。

【DB】木構造

what is this?

テーブル設計の際に、木構造のデータを表現する方法をメモとしてまとめたもの

assumption

木構造とは?

こんなやつ

  • ノード 木の結節点
  • ルートノード 木の始点となるノード(treeはルートノードを一つしか持たない)
  • リーフノード 自分よりも下位のノードを持たない「終着点」のノード
  • 内部ノード 中間に位置するノード
  • 経路(path) ノードからノードへの道筋

隣接リストモデル(ナイーブツリー)

  • ノードのレコードに親ノードの情報(ポインタ)を持たせようとするもの
  • SQL木構造を表現する最も古くポピュラー
  • 更新・検索のクエリが複雑になりパフォーマンスが悪化する 例)

入れ子集合モデル

  • ノードを点ではなく、円として捉える
  • 座標を持たせる
  • 座標の絶対値が重要ではなく、包含関係であるという相対的な関係性が表現されていればよい
  • 検索が得意
  • 更新が苦手

検索

  • ルートノードを取得するクエリ
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....

参考