Tutorial Advent Calendar 22日目、エンジニアの吉野です。

先日、Rails でツリー構造に触れる機会があり、その際に初めて知ることが多くありました。今回はその際に得られた知見を共有させていただこうと思います。

ツリー構造って何？

まず、ツリー構造（木構造）とはなんのことでしょうか？

Wikipediaによると

木構造（きこうぞう）とは、グラフ理論の木の構造をしたデータ構造のこと。

だそうです。下に示した組織図のように、ある要素から派生して階層構造が成り立っているものを、木が根から葉へと広がっていく様子になぞらえてツリー構造と呼んでいるわけですね。

身近なところでイメージしやすいのは、パソコンのフォルダで見られる階層構造もツリー構造にあたります。

RDB でツリー構造を実現する方法

MySQL や PostgresQL といった、Web アプリケーション開発でよく用いられるリレーショナルデータベース（RDB）でフォルダや組織図のようなツリー構造を実現するにはどうしたら良いでしょうか？

本来、列と行で構成されるRDB はツリー構造のような階層構造を表現するには不向きとされています。しかし、先人たちの知恵により、RDB でツリー構造を実現するための解法（モデル）が考案されてきました。現在、主に知られているのは以下の4つのモデルです。

• 隣接リストモデル（ナイーブツリー）
• 経路列挙モデル
• 閉包テーブルモデル
• 入れ子集合モデル

また、Rails ではツリー構造をサポートするメジャーな gem が4種存在し、それぞれが各モデルに対応しています。

• acts_as_tree（隣接リスト）
• ancestry（経路列挙）
• closure_tree （閉包テーブル）
• awesome_nested_set （入れ子集合）

各モデルとgem について、特徴を見ていきましょう。

acts_as_tree （隣接リストモデル）

特徴

親となる要素の名前や id など、一意に親を特定できる情報だけを持つシンプルな仕組みが隣接リストモデルの特徴です。それぞれのデータは、自分の親だけを知っていることになります。
acts_as_tree gem は DB に parent_id を必要とし、そのカラムに親要素の id を保持します。子要素や親要素を取得するメソッドも提供しており、gem をインストールするだけで簡単にツリー構造を実現できるのが強みです。

モデル自体に並び順の概念はなく、gem でもサポートしていないため、例えばフォルダの並び替え機能などを実装する際には、並び順を保持する仕組みを自分で実装する必要があります。

隣接リストモデルは自分で実装するのもさほど難しくないため、gem を使うか自分で実装するかは考えるべきポイントだと思います。

メリット

• 構成がシンプルなため理解しやすい
• 親要素の情報のみを変更すれば良いため、要素の追加、移動が簡単

デメリット

• 階層がどこまで深いか判断する術がないため、SQL で深層の子要素を取得するのが難しい
• • 有名な書籍「SQLアンチパターン」では、第2章で隣接リストモデルがアンチパターンとして紹介されています
  • RDB が再帰クエリをサポートしていれば解決するものの、RDB やそれぞれのバージョンによっては対応していないことがあります

ancestry （経路列挙モデル）

特徴

根っこの要素（root と呼ぶことが多い）からの経路を文字列などで保持して階層構造を実現しています。このモデルも直感的にわかりやすいものだと思います。上の図ではわかりやすさのため経路を文字で表現していますが、通常は id を使用して 1/2/3 といった形で経路を保持することが多いようです。

ancestry gem でも同様に、経路を各データの id を連ねた文字列 1/2/3 という形式で保持します。この gem は各データが自分の階層（先祖）を知っていることを利用して、あるデータの全ての先祖、兄弟要素、全ての子孫要素などを簡単に取得できるメソッドを提供しています。これが非常に便利です。

経路列挙モデルも隣接リストと同じく並び順の概念はなく、gem でもサポートしていません。並び替え機能は自分で実装する必要があります。

メリット

• 構成がシンプルなため理解しやすい
• 先祖、子孫、兄弟などを1つのクエリで取得できる
• • ancestry gem であればメソッドで一発で取得できる

デメリット

• 末端以外のデータの親を変更するとそのデータの子孫データも全て更新しなければならない
• • 例えば課長Aが新キャラ部長Bの部下になった場合、課長Aの部下である社員Bの経路も新たに 部長B>課長A>社員B に更新する必要があります
• RDB のカラムに保存できる文字列の長さは最大値が決まっているため、経路が長くなってくると保存できなくなる
• • 「SQLアンチパターン」1章にアンチパターン「ジェイウォーク」として紹介されています

closure_tree（閉包テーブルモデル）

特徴

データ同士の全ての関係性を別テーブルで管理する方法です。この別テーブルを閉包テーブルと呼んでいるようです。図中の右表、一列目のように親と子どちらも自分自身であるようなデータを保持している点に注意しましょう。

closure_tree gem では、ツリー構造を持たせたいモデルに has_closure_tree を設定することで、自動的に閉包テーブルが作成され、各データの関係性が保存されていきます。また、closure_tree は各データの兄弟間における並び順の保持もサポートしており、フォルダの並び替えなども簡単に実現することができます。

メリット

• 先祖、子孫、兄弟などを1つのクエリで取得できる
• closure_tree を使えば簡単に兄弟間の並び順が保持できる

デメリット

• 閉包テーブルのデータ量が膨大になりやすい
• ノードの削除に伴って閉包テーブルの関連レコードも削除され、DBに負荷がかかる可能性がある
• • 例えば大量の子要素を持つデータを削除した場合、閉包テーブルに保存されている関係性を示すレコードも全て削除することになります（親要素と一緒に子要素も削除する設定の場合）

awesome_nested_set （入れ子集合モデル）

特徴

このモデルはちょっとわかりにくいかもしれません。「達人に学ぶDB設計徹底指南書」の著者であるミック氏の解説によると、

木構造のノードを円と見なし、階層関係を円の包含関係として捉えなおす。

引用元: https://mickindex.sakura.ne.jp/database/db_tree_ns.html

だそうです。データを示す円で表現し、その左端と右端の座標からデータ同士の親子関係、並び順を判別することができる手法になります。

awesome_nested_set gem は parent_id、lft、rgt のカラムを使用することで入れ子集合モデルを実現しています。lft カラムに円の左端座標、rgt カラムに右端座標を格納しているわけですね。

メリット

• 並び順を保持できる
• クエリで複雑なデータの取得が可能
• • 親子関係はもちろん、階層の深さなどもクエリで取得できます

デメリット

• データの追加、更新時の処理が複雑になる
• • 例えば社員Aと社員Bの間に新たな社員を追加しようとすると、上図における座標5以降を全て2ずらす必要があり、場合によっては大量データを更新する必要があります
• 座標がカラムの最大値に達するとそれ以上データの追加ができなくなる

ちなみに、座標を整数ではなく実数で表現する「入れ子区間モデル」という方法があります。小数を利用して座標を分割していくことで、理論上は無限にデータを増やせることになり、「座標がカラムの最大値に達するとそれ以上データの追加ができなくなる」を解決できるのでは、、、と思えます。しかし、RDB の性能の問題でいずれ座標分割の限界は訪れるため、やはりいずれデータの追加ができなくなるのは避けられないようです。

どのモデルを選べばいいの？

ツリー構造を可能にする4つのモデルを紹介しましたが、どのモデルを採用すればいいのかはシステムの要件次第で変わってきます。

例えば隣接リスト方式はアンチパターンとされていますが、

• ツリー構造の階層の深さが予め決まっている
• RDB が再帰クエリをサポートしている
• 一度に子孫全てを取得する必要がない（1階層下の子要素だけ取得できれば十分）

などの状況であれば、採用することに何ら問題はないと思います。

また、階層構造だけでなくデータの並び順も重要だ、というケースでは入れ子集合モデルを採用するか、Rails プロジェクトであれば closure_tree gem を使うのもいいと思います。

どのモデル、gem も一長一短なので、自分の作りたい機能に合わせて選択することが大事だと思います。

終わりに

今回は今まで触れることのなかったツリー構造について紹介しました。似たような情報はネット上に多く転がっていましたが、自分の言葉でまとめることで理解が深まった気がします。

この記事が少しでも誰かの参考になれば幸いです。

参考にした書籍、サイトなど

• SQLアンチパターン（Bill Karwin 著、和田 卓人、和田 省二　監訳、児島 修　訳）
• https://www.slideshare.net/kamekoopa/ss-27728799
• https://gihyo.jp/dev/serial/01/sql_academy2/000501
• https://gihyo.jp/dev/serial/01/sql_academy2/000502
• https://gihyo.jp/dev/serial/01/sql_academy2/000503
• https://mickindex.sakura.ne.jp/database/db_tree_ns.html