組織の部署構造、投稿へのリプライ、ファイルシステム、分類 …etc
現実世界をモデリングするときに、ツリー構造がよく出現する。
graph TD
Animals --> Mammals
Animals --> Birds
Mammals --> Cat
Mammals --> Dog
Birds --> Eagle
Birds --> Sparrow
ツリー構造のデータをRDBで扱う方法はいくつかある。
- 隣接リスト
- 経路列挙
- 入れ子集合
- 閉包テーブル
それぞれの特徴とトレードオフについて考えてゆく。
ツリー構造の実装手法
隣接リスト
恐らく真っ先に思い浮かぶのがこの方式。
各ノードが親ノードを参照する列を持ち、隣接するノードのリストとして表現される。
| id | name | parent_id |
|---|---|---|
| 1 | Animals | NULL |
| 2 | Mammals | 1 |
| 3 | Birds | 1 |
| 4 | Cat | 2 |
| 5 | Dog | 2 |
| 6 | Eagle | 3 |
| 7 | Sparrow | 3 |
- メリット:
- ノードの追加や更新が容易
- ツリー内のノードの移動が効率的に行える
- デメリット:
- 特定の階層の親ノードや子ノードを見つけるために再帰的なクエリが必要となる（アンチパターン：ナイーブツリー）
- 末端以外のノードの削除処理が複雑になる
隣接リストにおいては「構成のシンプルさ」と「検索と削除の複雑さ」がトレードオフとなる。
経路列挙
これも比較的直観的な方式。
各ノードがパス（経路）を持ち、それによって親子関係を表現する。
| id | name | path |
|---|---|---|
| 1 | Animals | / |
| 2 | Mammals | /1/ |
| 3 | Birds | /1/ |
| 4 | Cat | /1/2/ |
| 5 | Dog | /1/2/ |
| 6 | Eagle | /1/3/ |
| 7 | Sparrow | /1/3/ |
- メリット:
- ルートからのパス探索は前方一致や完全一致の検索となるためIndexが利用でき、特定のノードやその子孫を高速に見つけることができる
- 生のテーブルデータの可読性が高い
- デメリット:
- ツリーが深くなるとパスも長くなるため、経路が長くなるとDBのカラム制約によっては保存できなくなる場合がある
- ルート以外からのパス探索は中間一致の検索となるためIndexが利用できず、性能が低下する場合がある
- 末端以外のノードの変更が必要な場合に処理が複雑になる
- Foreign Keyが使えないため、親子関係の整合性が担保できない（アンチパターン：ジェイウォーク）
経路列挙においては「構成のシンプルさ・可読性」と「変更の複雑さ・検索パフォーマンス（状況による）・データ整合性」がトレードオフとなる。
入れ子集合
ツリーではなく集合としてモデリングする方式。
区間の左端・右端それぞれのidを保持し、区間を表現する。
| id | name | left | right |
|---|---|---|---|
| 1 | Animals | 1 | 14 |
| 2 | Mammals | 2 | 7 |
| 3 | Birds | 8 | 13 |
| 4 | Cat | 3 | 4 |
| 5 | Dog | 5 | 6 |
| 6 | Eagle | 9 | 10 |
| 7 | Sparrow | 11 | 12 |
- メリット:
- 階層的なデータを自然に表現できるため、データ取得が容易
- 同一階層内での順序の管理ができる
- デメリット:
- データの追加や更新を行う際に、複数のレコードの更新が必要な場合がある
- 例：CatとDogの間にPigを追加する場合、Mammalsの右端以降の座標が2ずつずれる
- Foreign Keyを使わないため、異常なデータを制約で阻止できない
- データの追加や更新を行う際に、複数のレコードの更新が必要な場合がある
入れ子集合においては「検索の容易さ」と「更新の複雑さ・データ整合性」がトレードオフとなる。
閉包テーブル
親子関係を別テーブルで持つ方式。
| id | name |
|---|---|
| 1 | Animals |
| 2 | Mammals |
| 3 | Birds |
| 4 | Cat |
| 5 | Dog |
| 6 | Eagle |
| 7 | Sparrow |
| ancestor | descendant |
|---|---|
| 1 | 1 |
| 1 | 2 |
| 1 | 3 |
| 2 | 2 |
| 2 | 4 |
| 2 | 5 |
| 3 | 3 |
| 3 | 6 |
| 3 | 7 |
| 4 | 4 |
| 5 | 5 |
| 6 | 6 |
| 7 | 7 |
親子がどちらも自分自身であるようなデータも保持するのがポイント。
- メリット:
- シンプルなクエリで先祖・子孫・兄弟の取得ができる
- 階層の深さに実質制限がない
- デメリット:
- テーブルサイズが大きくなる（閉包テーブルの行数はツリー深度の2乗に比例）
- ノードの追加・変更・削除時に更新すべきレコードが多くなる
閉包テーブルにおいては「検索の容易さ」と「テーブルサイズ・更新レコード数」がトレードオフとなる。
使い分け
トレードオフを意識し、状況に応じて選択すればOK。
一般的に隣接リストや経路列挙はアンチパターンとされているが、要件によっては選択できる場合がある。
例えば
- 直近の親子関係のみ取得できればよい場合・再帰クエリが利用できる場合は、隣接リストが採用候補となる
- 柔軟なクエリを実行する必要がなく、ノードの更新が行われない場合は、経路列挙が採用候補となる
アンチパターンとされていない入れ子集合や閉包テーブルを使う場合も、デメリットが許容できるのか検討する必要がある。
例えば
- ツリーの更新頻度が高く、データの整合性が重要である場合は、入れ子集合は採用しないほうがよいかもしれない
- 極めて巨大なツリーを作成する想定がある場合は、閉包テーブルは採用しないほうがよいかもしれない
いずれも銀の弾丸ではないため、要件と照らし合わせて意思決定するほかない。
参考：