階層構造のDB設計について

その他

この記事を書いたチーム：frontier

概要
実現方法の種類
隣接リスト
経路列挙
入れ子集合
閉包テーブル
最後に

概要

【エンジニア募集中】フルリモート可◎、売上/従業員数9年連続UP、平均残業8時間、有給取得率90％、年休124日以上 etc.　　詳細はこちらから＞

担当案件でフォルダの作成・削除、ファイルのアップロード、削除ができ、一覧表示、パンくずリストをする画面を作成する必要があったため、階層構造のDB設計の方法について調査した。後学のために調査した内容について記載します。

実現方法の種類

主要な実現方法としては下記の４種類があった。

隣接リスト
経路列挙
入れ子集合
閉包テーブル

それぞれの方法の概要、メリット、デメリット等を記載します。

隣接リスト

・概要
　各フォルダに自身の親フォルダを保持して、参照する方法。
・メリット
　構造が直観的で隣接した親子関係の取得が容易。
・デメリット
　フォルダの階層が深い場合に階層の数分、LEFT JOINして取得する必要がある。
　（但し再帰が使用可能なDBでは解消可能。）

経路列挙

・概要
　各フォルダに自身のフォルダパスを保持して、参照する方法。
　保持したフォルダパスに”%”を付与して、like句を使用することで
　親フォルダ、子フォルダの取得が可能。
・メリット
　データの操作が容易。
・デメリット
　フォルダパスの管理はアプリのコードに依存し、チェックが複雑になりやすい。
　フォルダパスはvarchar型で保持するため、有限となる。

入れ子集合

・概要
　各フォルダに子フォルダの集合情報（nsleft、nsrightと呼ばれる数値）を保持して、参照する方法。
　nsleft、nsrightの間にあるnsleftをbetween句を使用することで、親フォルダ、子フォルダの取得が可能。
・メリット
　階層構造をシンプルなデータ構造で表現可能。
・デメリット
　フォルダの作成や移動等の階層構造に変更がある場合の更新処理が他に比べて複雑。
　（nsleft、nsrightの再計算が必要となるため。）

閉包テーブル

・概要
　各フォルダにidを付与したテーブルを用意して
　付与したidの親子関係を別テーブルにて保持して、参照する。
　（別テーブルには隣接した親子関係だけでなく、離れた親子関係、自身も保持する。）
・メリット
　親子関係を別テーブルで管理しているため、取得が容易。
・デメリット
　親子関係を保持したテーブルのデータ量が増える。