ネストされたセット、Closure Table、Adjacency List：MySQLで階層構造データを扱う3つの手法

2024-04-02

MySQLで階層構造データを扱うための再帰的なクエリの実装方法と実用例

この解説では、MySQLにおける再帰的なクエリの仕組みと実装方法を、具体的な例を用いて分かりやすく解説します。また、実用的なユースケースもいくつか紹介します。

再帰的なクエリは、自身を呼び出すことで、階層構造データを再帰的に処理するクエリです。具体的には、以下の2つの要素で構成されます。

共通テーブル式 (CTE): 再帰的なクエリを記述するための構文
UNION ALL: 複数の結果セットを結合するための演算子

実装方法

共通テーブル式の定義

まず、CTEを使って再帰的なクエリを定義します。CTEには、以下の要素を記述する必要があります。

CTEの名前: 任意の名前を指定できます
列名: 取得する列を指定します
SELECT句: 再帰的に処理するクエリを記述します

UNION ALLによる結果セットの結合

次に、UNION ALLを使って、CTEの最初の行と、再帰的に呼び出された結果セットを結合します。

アンカー条件

再帰的な処理を終了するための条件を指定する必要があります。これは、WHERE句で記述します。

実用例

親子関係を持つデータの取得

以下の例では、categoriesテーブルという親子関係を持つテーブルがあると仮定します。このテーブルには、id、parent_id、nameという列があります。

WITH RECURSIVE cte (id, parent_id, name, depth) AS (
  SELECT
    id,
    parent_id,
    name,
    0 AS depth
  FROM
    categories
  WHERE
    parent_id IS NULL
  UNION ALL
  SELECT
    c.id,
    c.parent_id,
    c.name,
    cte.depth + 1
  FROM
    categories c
  INNER JOIN
    cte ON c.parent_id = cte.id
)
SELECT
  *
FROM
  cte

このクエリは、以下の処理を行います。

categoriesテーブルから、parent_idがNULLである行を取得する (根ノード)
取得した行に対して、id、parent_id、name、depth (階層深度)という列を返す
再帰的に、cteテーブルとcategoriesテーブルをINNER JOINし、parent_idが一致する行を取得する
取得した行に対して、depthを1加算して、cteテーブルに追加する
1～4の手順を、parent_idがNULLになるまで繰り返す

上記のクエリを実行すると、categoriesテーブルの全データが、階層構造に従って取得されます。

以下の例では、上記のクエリ結果を階層的に表示する例です。

SELECT
  CONCAT(REPEAT(' - ', depth), name) AS name
FROM
  cte
ORDER BY
  depth,
  name

depthの数だけ'-'を連結して、階層を表す文字列を作成する
name列と作成した文字列を結合して、新しい列を作成する
depthとnameの順序で結果をソートする

その他の実用的なユースケース

特定の階層にあるデータの取得

MySQLにおける再帰的なクエリは、階層構造データを扱うための強力なツールです。この機能を使いこなすことで、複雑なデータ構造を効率的に処理することができます。

WITH RECURSIVE cte (id, parent_id, name, depth) AS (
  SELECT
    id,
    parent_id,
    name,
    0 AS depth
  FROM
    categories
  WHERE
    parent_id IS NULL
  UNION ALL
  SELECT
    c.id,
    c.parent_id,
    c.name,
    cte.depth + 1
  FROM
    categories c
  INNER JOIN
    cte ON c.parent_id = cte.id
)
SELECT
  *
FROM
  cte

SELECT
  CONCAT(REPEAT(' - ', depth), name) AS name
FROM
  cte
ORDER BY
  depth,
  name

WITH RECURSIVE cte (id, parent_id, name, depth) AS (
  SELECT
    id,
    parent_id,
    name,
    0 AS depth
  FROM
    categories
  WHERE
    parent_id IS NULL
  UNION ALL
  SELECT
    c.id,
    c.parent_id,
    c.name,
    cte.depth + 1
  FROM
    categories c
  INNER JOIN
    cte ON c.parent_id = cte.id
)
SELECT
  *
FROM
  cte
WHERE
  depth = 2

WITH RECURSIVE cte (id, parent_id, name, depth) AS (
  SELECT
    id,
    parent_id,
    name,
    0 AS depth
  FROM
    categories
  WHERE
    parent_id IS NULL
  UNION ALL
  SELECT
    c.id,
    c.parent_id,
    c.name,
    cte.depth + 1
  FROM
    categories c
  INNER JOIN
    cte ON c.parent_id = cte.id
)
SELECT
  depth,
  COUNT(*) AS count
FROM
  cte
GROUP BY
  depth

UPDATE categories c
INNER JOIN cte ON c.id = cte.id
SET c.name = '新しい名前'
WHERE
  cte.depth = 2

DELETE c
FROM categories c
INNER JOIN cte ON c.id = cte.id
WHERE
  cte.depth = 2

補足

上記のサンプルコードは、あくまでも基本的な例です。実際のユースケースに合わせて、コードを修正する必要があります。

また、再帰的なクエリは、複雑な処理を行うため、パフォーマンスに注意する必要があります。必要に応じて、インデックスを張ったり、クエリを最適化したりする必要があります。

MySQLで階層構造データを扱うための他の方法

ネストされたセット (Nested Set)

ネストされたセットは、親子関係を表現するために、2つの列 (lft と rght) を使用する手法です。この手法は、階層構造のデータの挿入、更新、削除が比較的簡単に行えます。

Closure Tableは、親子関係を表現するために、parent_id と ancestor_id という2つの列を使用する手法です。この手法は、任意の祖先の情報に簡単にアクセスできるというメリットがあります。

Adjacency Listは、親子関係を表現するために、parent_id という列を使用する手法です。この手法は、データ構造がシンプルで、理解しやすいというメリットがあります。

それぞれの方法のメリットとデメリット

方法	メリット	デメリット
再帰的なクエリ	複雑な階層構造を表現できる	パフォーマンスが低下する可能性がある
ネストされたセット	挿入、更新、削除が簡単	インデックスの管理が複雑になる
Closure Table	祖先の情報にアクセスしやすい	テーブル構造が複雑になる
Adjacency List	データ構造がシンプル	親子関係の取得が複雑になる