こんにちは。トレタでサーバーサイドを担当している川村です。
この記事はトレタアドベントカレンダーの11日目に大遅刻したものです。
今回は私が担当している権限管理システムで採用したデータ構造について紹介したいと思います。

背景

現在開発している権限管理システムでは「誰が」「何を」「どこで」できるかを表現できるようにしたく、また、今後作成するプロダクトの権限管理に汎用的に使えるようにしたいと考えていました。
データの持ち方を考えるにあたって、この3要素がそれぞれ何のデータと対応しているかを考えると以下のようになります。

「誰が」＝アカウント
「何を」＝パーミッション
「どこで」＝法人、管理単位（エリアなど）、店舗、店舗備品など

この先も汎用的に使っていくために「どこで」の対象が多岐に渡っているため、法人を頂点として管理階層を段々と店舗方向に下っていくような内容、つまりツリー構造が表現できると良いのではという結論になりました。

ツリーの保存方法

調べてみるとツリー構造をRDBで表現するためのデータ構造は現在までに色々考案されているようでした。
「達人に学ぶDB設計」¹と「SQLアンチパターン」²を見てみると５つの方式が紹介されています。

隣接リストモデル（アンチパターン）
- あるノードを親とした時の親子を１レコードとして上から１ノードずつ保存
入れ子集合モデル
- 親子関係を集合の包含関係で表現する（子は親に内包されている）
- 集合の幅を整数の数直線で表現し、各ノードが数直線上のどの範囲に居るのか、左端と右端の数字を保存する
入れ子区間モデル
- 入れ子集合の数直線を実数にしたもの。実数なので少数が使え、更新処理の煩雑さを緩和できる
経路列挙モデル
- 各ノードについて、そのノードまでの親からの経路を保存する（ディレクトリのパスと同じ）
閉包テーブル
- 各ノードを起点に、そのノード以下の全てのノードへの経路を保存する

今回開発するシステムでは閉包テーブルにノードまでの距離の情報を追加したモデルを採用しました。
採用した理由としてはツリーの更新が（他のモデルに比べて）比較的単純に思えたことと、CTOからもおすすめがあったことです。

閉包テーブル（ClousureTable）

ここから今回採用した深さ付き閉包テーブルの構造やクエリ例について記載します。

テーブル構成/構造

閉包テーブル方式では２つのテーブルが必要になります。

ノード自体の情報テーブル(Nodes)
各ノードのデータを保存するテーブルです。
例えばノードに名前と状態、登録日時の情報が必要だとしたら以下のようなテーブルになるでしょう。

カラム名	型	内容
id	文字列 or 数値	識別子の文字列か自動採番の数値
name	文字列	リソースの名前
status	数値	リソースの状態
created_at	タイムスタンプ	作成日時

ツリー構造を保存するテーブル（NodePaths）
各ノード間の経路の情報をそれぞれ保存するテーブルです。
こちらは基本的にノード自体の情報に関係なく以下のような構造になります。

カラム名型内容

ancestor 文字列 or 数値経路の起点のノードのid

descendant 文字列 or 数値終点のノードのid

path_length 数値起点からの深さ

カラム名	型	内容
ancestor	文字列 or 数値	経路の起点のノードのid
descendant	文字列 or 数値	終点のノードのid
path_length	数値	起点からの深さ

ツリーの表現の仕方

ツリー構造の保存テーブルにどうデータを保存するかを例を挙げて説明します。
今回は例としてトレタという会社の下にレストランが３店舗、内２店舗にPOSシステムが１台づつある状態を表現することを考えてみたいと思います。

経路（ancestor, descendant）

この構造の内、例えばトレタからの経路を抜き出すとこのようになり、この内容を ancestor → descendantとしてテーブルに保存します。

株式会社トレタ → 株式会社トレタ
株式会社トレタ → レストラン五反田
株式会社トレタ → レストラン渋谷
株式会社トレタ → レストラン恵比寿
株式会社トレタ → POS@五反田
株式会社トレタ → POS@渋谷

一番目にトレタ→トレタが経路として出てきますが、間違いではなく、閉包テーブルではこのように起点のノード自身への経路も保存することになっていて、これがあることでツリーの更新の際に助かったりします。
今回トレタからの経路を見たのと同じように、他の各ノードを起点にして経路を列挙しテーブルに保存することでツリーが表現できます。

深さ（path_length）

上記でancestorとdescendantに何を入れるかが分かりましたが、path_lengthについてはどう考えるのでしょうか。
path_lengthは起点のノードを0として、そこから１段辿るごとに１づつ増えていきます。（この図の点線を超えるごとに１増えるわけですね）

なので、トレタ→トレタは０、トレタ→レストラン（五反田/渋谷/恵比寿）は１、トレタ→POS（五反田/渋谷）は２となります。

まとめ

以上をまとめて記載した画像がこちらです。点線の箱１つ１つを閉包テーブルにレコードとして保存してツリー構造を表現します。
＊図中の「anc」「des」はそれぞれ「ancestor」「descendant」の略、矢印の色はpath_lengthの違いを表しています。

ですので、テーブルの内容としてはこのような形になります。

ancestor	descendant	path_length
株式会社トレタ	株式会社トレタ	0
株式会社トレタ	レストラン五反田	1
株式会社トレタ	POS@五反田	2
株式会社トレタ	レストラン渋谷	1
株式会社トレタ	POS@渋谷	2
株式会社トレタ	レストラン恵比寿	1
レストラン五反田	レストラン五反田	0
レストラン五反田	POS@五反田	1
レストラン渋谷	レストラン渋谷	0
レストラン渋谷	POS@渋谷	1
レストラン恵比寿	レストラン恵比寿	0
POS@五反田	POS@五反田	0
POS@渋谷	POS@渋谷	0

クエリについて

なんとなく想像がつくかと思いますが、ツリーの構造を変更する操作はそれなりにややこしいです。
一部の操作のクエリを例として見たあと、どうやってクエリを考えたかという話を載せてみたいと思います。

保険：
※1. このデータモデルは１ノードが複数の親を問題なく持てるようなのですが、現状その使い方は考慮していないため複数親をもたせる場合はこのクエリは使えない可能性があります。
※2. ここに乗せるやり方は一例であり、もっと良いやり方があるかも知れません。

ノードの追加

さきほどのトレタの例をもとに、渋谷と恵比寿の店舗を渋谷エリアとしてまとめたくなった場合を考えます。

流れとしては以下の３ステップで実装しました。

トレタとレストラン渋谷・恵比寿の間に隙間を作る
= 親 → 子孫以下の層のpath_lengthを足す
トレタから渋谷エリアへの経路を追加する
= 祖先から新規ノードへの経路を追加する
渋谷エリアから各子孫への経路を追加する
= 新規ノードから子孫への経路を追加する

1.隙間を開ける

親とその祖先のノードから子にするノード以下の経路のpath_lengthを+1します。

UPDATE node_paths
		SET	path_length = path_length + 1
	WHERE ancestor IN (
		SELECT ancestor
		FROM node_paths
		WHERE descendant = 親のノードid
	) AND descendant IN (
		SELECT descendant
		FROM node_paths
		WHERE ancestor IN (子にするノードid)
	)

今回の例でいうと、トレタからレストラン渋谷・恵比寿の経路のpath_lengthを+1します。
トレタよりも上に他のノードがある場合は、そこからレストラン渋谷・恵比寿以下への経路のpath_lengthも＋１する必要があるので祖先からの経路も含めています。

2. 祖先から新規ノードへの経路を追加

祖先ノードから親に対する経路の子側を新規ノードidに変更、path_lengthを+1したものを追加します。

INSERT INTO node_paths (ancestor, descendant, path_length)
		SELECT np.ancestor, 新規ノードのid, np.path_length + 1
		FROM node_paths np
		WHERE np.descendant = 親ノードのid

3. 新規ノードから子孫宛ての経路を追加

子にするノードを祖先に持つ経路の祖先側を新規ノードidに変更、path_lengthを＋１したものを追加します。

INSERT INTO node_paths (ancestor, descendant, path_length)
		SELECT 新規ノードのid, np.descendant, path_length + 1
		FROM node_paths np
		WHERE np.ancestor IN (子にするノードのid)

以上でノードの追加操作が完了です。

親ノードの変更

もう一つの例としてレストラン五反田をトレタの下からToretaの下に移動、つまりツリーの親ノードを変更することを考えてみます。

流れとしては以下の２ステップです。

トレタからレストラン五反田以下のノードへの経路を削除する（トレタからレストラン五反田以下のツリーを切り離す）
= 移動したいツリーの起点ノードの祖先から起点ノード以下への経路を削除する
Toretaからレストラン五反田以下のノードへの経路を追加する（Toretaの下にレストラン五反田をつなぐ）
= 新しい親とその祖先のノードと、移動するツリーの全ノードを取得し、クロスジョインしたものを経路として保存する

1. トレタからレストラン五反田以下のツリーを切り離す

起点ノード以外からの各ツリーノードへの経路を消します。

DELETE FROM node_paths
WHERE path_length > 0 AND ancestor NOT IN (移動する起点ノードid) AND descendant IN (
        SELECT descendant
        FROM node_paths np
        WHERE np.ancestor IN (移動する起点ノードid)
    )

2. 新しい親の下にツリーを追加する

祖先から新しい親までの経路とツリーの起点ノード以下の経路を合わせて、新しい経路を作ります。

INSERT INTO node_paths (ancestor, descendant, path_length)
SELECT ancester, descendant, path_length + add_length AS path_length
FROM (
    SELECT ancestor, path_length
    FROM node_paths np
    WHERE descendant = 新しい親ノードid
) t1,
(
    SELECT descendant, path_length + 1 AS add_length
    FROM node_paths np
    WHERE ancestor IN (移動する起点ノードid)
) t2

以上で、親の変更作業完了です。

クエリの考え方

ここまで見た２つの操作だけでもどういう操作をすればいいのかぱっと思いつく人は少ないのではないかと思います。
私は頭だけで考えると途中で混乱するので、更新前後の経路を紙やホワイトボードなどに書き出して、消えているべき/追加されているべき経路や深さの増減がどうなるのかを確認して、クエリに落としこんでいました。

更新後にどうなるべきかが目に見えているので、更新前に存在する経路情報との共通点を見て、新しく作る経路をどう生成するかを考えることができとても捗ります。
実際、親追加の際にクロスジョインして経路を作ったりしているのはまさに書き出したおかげで気づいたところだった覚えがあります。

クエリを考えるにあたって大事だと思われることとして、十分に複雑なツリーを例にして考えるということがあります。
開発用にさっと作ったデータだとあっさりとしたツリーであることが多いかと思いますが、祖先は複数世代、子は複数かつ数世代いるようなツリーを考えて経路を書き出して考えた方が漏れのないクエリにできると感じました。

おわりに

将来を考えるとこのデータ構造は必要だと思っているのですが、まだ大きなツリーができるほど本格的な運用はされておらず、どのような壁にぶつかるのか、もしくはぶつからないのか分かりません。もし何か課題が見つかれば、また記事にしていきたいと思います。

トレタではより良い作り方を一緒に考えてくれる人を募集しています。
https://corp.toreta.in/recruit/engineer/

閉包テーブルを使ってツリー構造を保存する

背景