はじめに
少し前に現在開発しているプロダクトに階層構造のあるフォルダ機能を追加したのでそのときの知見をまとめておきます。 DB は PostgreSQL11 を使用しています。
RDB で階層構造を表現する
RDB で階層構造を表現することは難しく、いくつかの対応手法があるがどれも一長一短あります。 ここではそれらのメリット・デメリットだけ簡単にまとめておきます。
| 手法 | 説明 | メリット | デメリット |
|---|---|---|---|
| 隣接リスト | 各レコードに親の id を保存する。頂点のレコードの親の id は NULL | 追加・更新時のレコード数を最小限にできる。外部キーによって矛盾したデータを排除できる。見た目的にわかりやすい | 階層を辿る必要のあるレコード取得では複数のクエリが必要になる可能性がある。※DB によっては再帰クエリで 1 回で書ける |
| 経路列挙 | 各レコードに頂点からのパスを VARCHAR で保存する | 各レコードを見るだけで階層が取得できる | 更新時に複数のレコードの更新が必要になる。矛盾したデータを入れることができる。VARCHAR の長さがパスの限界になる |
| 入れ子集合 | 各レコードの持つ子孫の範囲を左端と右端の整数値により表す | 子孫を持たないレコードを 1 クエリで取得できる。階層の深さを 1 クエリで取得できる。 | 追加・更新・削除時に複数のレコードの更新が必要になる。※左右端を整数値ではなく実数値で持つ入れ子区間モデルであればこの問題を解決できる |
| 閉包テーブル | 直接の親子関係だけでなく、先祖と子孫の関係をすべて持つテーブル作成する | どれだけ深い階層であっても先祖・子孫の対応の取得が 1 クエリでできる。複数の親を持つことができる | 追加・更新・削除時は複数のレコードを更新する必要がある。多くのレコード数が必要になるためスペースが消費される |
それぞれ用途に応じて使い分けるのが理想かと思います。 今回は隣接リストモデルを採用しました。 理由としては、再帰クエリを利用すればデメリットはほぼないこと、また今回のフォルダ機能においては階層の離れた関係を扱うよりも、ある階層のレコードをすべて取得という親子関係の操作を求められることが多いため、それをシンプルに表現できる隣接リストモデルがよいと考えました。 階層の離れた関係を扱うことが多い場合、入れ子集合や閉包テーブルの方がパフォーマンスがよくなる可能性があります。
隣接リストモデルを採用する場合の注意点
親 id には外部キーを貼ること
外部キーを貼ることで存在しないレコードを親に持つなどの矛盾した状態を防げます。 こうした状態はアプリケーション側ではなく、なるべく DB 側の制約で確実にできないようにした方がよいです。
利用している DB に再帰クエリがあるか確認する
再帰クエリがない DB の場合、深い階層へクエリ実行する必要がある場合には少なくとも階層分クエリを実行する必要がありパフォーマンスが悪くなる可能性があります。
-- 次のような隣接リストのテーブルがあるとする
create table tree (id int , parent_id int);
insert into tree values (1, NULL), (2, NULL), (3, 1), (4, 2), (5, 3);
select * from tree;
id | parent_id
----+-----------
1 | NULL
2 | NULL
3 | 1
4 | 2
5 | 3
(5 rows)
-- id=1の子孫を取得する再帰クエリ
with recursive search_tree(id, depth) as (
select tree.id, 1
from tree
where id = 1
union all
select tree.id, search_tree.depth + 1
from tree, search_tree
where tree.parent_id = search_tree.id
)
select * from search_tree;
id | depth
----+-------
1 | 1
3 | 2
5 | 3
(3 rows)フォルダ機能を実装する前に考えること
順番が前後しましたが、RDB の構造を考える前にフォルダ機能を実装する際にポイントとなる仕様についてもまとめておきます。
階層の深さに上限を設けるか
パフォーマンス問題も考えられるため上限を設けるのがベストですが、フォルダ作成時や移動時などに階層の深さを常にチェックするコストもかかるため、サービスによっては性善説にしたがって最初期のリリースでは上限を見送ってもよいと思います。 上限を設けるとしたらアプリケーション側ではなく DB 側のチェック制約で担保するのが良さそう。
フォルダへの入出力を行う箇所を洗い出す
フォルダ機能を作成する画面だけでなく、その画面に対する入出力を行う画面でもフォルダ機能と連携を行う必要があります。 例えば別画面からデータを入力する場合に、すでに存在するフォルダ内に直接データを投入できるようにするのであれば、入力画面にも階層関係を表す UI が必要になります。
フォルダとフォルダ内のデータに対する権限
今回実装で最も苦労したのが権限まわりの問題でした。 階層関係を持つ権限まわりは複雑になりがちです。 最終的には以下のようにシンプルな構成にしました。 Windows や Linux のディレクトリの権限まわりを参考にすると良さそうです。
- フォルダとデータそれぞれに権限を持たせる
- アクセス自体は全先祖階層の権限は必要なく、そのデータ・フォルダ自体の権限があればよい
- フォルダはフォルダ内の全データの権限を一括で変更できるオプションを追加する
全階層のデータの取得が必要か
ある階層のデータをすべて取得する API をリクエストする場合、親 id をパラメータに追加してリクエストするのは想像ができます。 全階層のデータを取得する API をリクエストする場合、親 id を NULL にして送りたくなるが、親 id が NULL のものは親を持たないトップ階層のデータになります。 そのため全階層のデータを取得する API では、別パラメータで全階層取得であることを表すなどする必要があります。
データの移動の方法
データの移動は大きく 2 種類あると思います。
- データを選択して移動 UI による移動（階層をまたいで一度に移動できる）
- ドラッグ&ドロップによる移動（手軽で使いやすい）
両方ともメリット・デメリットがあるが、両方作るコストが払えない場合は特性にあわせてどちらかを優先して実装するのがよいと思います。
パスの省略
パンくずなど階層のパスを表現するときにパス名が長すぎて全文字列は表現できない場合はどこかで省略する必要があります。 このとき適当な位置で省略するのではなく、深い階層ではトップ階層と直近 2 階層までしか階層名は出さず、あとの階層は省略記法で表現するなどすると汎用的な UI になると思います。
