MySQL でツリー構造 by 経路列挙モデル

備忘録 MySQL

備忘録。

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,
  path TEXT NOT NULL
);

path には / を区切り文字として id を元にした経路を列挙することとする。（例: ID1のノードの下にID2のノードがある場合、ID2のノードの path は 1/2/ となる）

以降、MyBatis で実装することを前提に、各操作の SQL がどうなるかを見ていく。

addNode(idm parentId)

INSERT INTO tree (id, path)
  SELECT #{id}, CONCAT(parent.path, '/', #{id}) FROM tree AS parent
  WHERE parent.id = #{parentId};

見ての通り。

getDescendantsOf(id)

SELECT other.id FROM tree AS other
  INNER JOIN tree AS own ON own.id = #{id}
  WHERE other.path LIKE CONCAT(own.path, '%') AND other.id != #{id};

パスが 1/2/ のノードの子孫を取る場合、それらは全て 1/2/ から始まる。したがってパスが 1/2/% とマッチする（自分以外の）レコードを SELECT すればよい。

getAncestorsOf(id)

SELECT other.id FROM tree AS other
  INNER JOIN tree AS own ON own.id = #{id}
  WHERE own.path LIKE CONCAT(other.path, '%') AND other.id != #{id};

1/2/3/ のノードに対して 1 と 2 を返したい。この場合は getDescendantsOf とは逆に、先祖ノードのパスが対象のノードに対して前方一致することを利用することになる。1/% や 1/2/% は 1/2/3/ とマッチするため対象となるが、一方で 1/2/3/4/% は 1/2/3/ とはマッチしない。

getParentOf(id)

SELECT other.id FROM tree AS other
  INNER JOIN tree AS own ON own.id = #{id}
  WHERE other.path = LEFT(own.path, LOCATE(CONCAT('/', own.id, '/'), own.path));

パスに対してごちゃごちゃと関数を適用しているが、やっていることはパスが 1/2/3/ のノードの場合に、1/2/ のパスのノードを引き当てているだけ。

getChildrenOf(id)

SELECT other.id FROM tree AS other
  INNER JOIN tree AS own ON own.id = #{id}
  WHERE other.path LIKE CONCAT(own.path, '%') AND other.id != #{id}
  AND LENGTH(other.path) - LENGTH(REPLACE(other.path, '/', '')) = LENGTH(own.path) - LENGTH(REPLACE(own.path, '/', '')) + 1;

getDescendantsOf での絞り込みに加えて、木の深さがちょうど1多いことを条件に加えればいい。ノードの深さはパスに含まれる区切り文字の数なので、文字数ベースで計算できる。