MySQL でツリー構造 by 閉包テーブルモデル
備忘録。
SQL アンチパターンに載っていた木構造を RDB で表現するためのモデルの1つ、閉包テーブルモデルの MySQL による実装について。
今回は以下の制約をかける。
- 簡略のため、各ノードは id のみを持つ
- ノードの削除はサポートしない
- ノードの追加は葉のみ
以下の5つのインタフェースを実装することを考える。
- ノードを追加する
addNode(id, parentId)
- 子孫ノードを全て返す
getDescendantsOf(id)
- 先祖ノードを全て返す
getAncestorsOf(id)
- 直接の子ノードを全て返す
getChildrenOf(id)
- 直接の親ノードを返す
getParentOf(id)
スキーマは以下のようになる:
CREATE TABLE tree ( id INTEGER NOT NULL PRIMARY KEY ); CREATE TABLE tree_path ( ancestor INTEGER NOT NULL, descendant INTEGER NOT NULL, PRIMARY KEY(ancestor, descendant), FOREIGN KEY(ancestor) REFERENCES tree (id), FOREIGN KEY(descendant) REFERENCES tree (id) );
addNode(idm parentId)
INSERT INTO tree (id) VALUES (#{id}); INSERT INTO tree_path (ancestor, descendant) SELECT other.ancestor, #{id} FROM tree_path AS other WHERE other.descendant = #{parentId} UNION ALL SELECT #{id}, #{id};
tree
テーブルに加えて、tree_path
テーブルに挿入する必要がある。
getDescendantsOf(id)
SELECT descendant FROM tree_path WHERE ancestor = #{id} AND descendant != #{id};
見ての通り。
getAncestorsOf(id)
SELECT ancestor FROM tree_path WHERE descendant = #{id} AND ancestor != #{id};
こちらも見ての通り。
getParentOf(id)
SELECT ancestor FROM tree_path WHERE descendant IN ( SELECT ancestor FROM tree_path WHERE descendant = #{id} AND ancestor != #{id} ) GROUP BY ancestor ORDER BY COUNT(*) LIMIT 1;
サブクエリは getAncestorsOf
と同じ。あるノードの先祖の ID の中で、親ノード側として登録されているパスが一番少ないのが、直接の親ノードになる。