SQLアンチパターンのナイーブツリー（素朴な木）パターンのデメリットと解決方法

こちらの記事では、「SQLアンチパターン」に登場するナイーブツリーについてまとめたものになります。

ナイーブツリー（素朴な木）とは

昨今では、SNS上で不特定多数の方がスレッド形式でコメントを残すことができるようになっています。

そして、そのスレッドはディスカッションのトピックに応じて枝分かれしています。

そのようなコメントスレッドを扱う際に、方法として思いつくのが、各コメントにリプライの対象となっている親コメントを参照させるということかと思います。これがツリー構造をとっており、ナイーブツリーと呼んでいます。

上記のテーブルの例では、id = 1のコメントに対して、 id = 2, 3 が返信をしており、id = 4, 5 は id = 2 のコメントに対してコメントをしていることを表しています。

ナイーブツリーパターンのデメリット

ツリー構造の取得

ナイーブツリーの構成をとると問題が生じてきます。それは、コメントへの返信の連鎖が長い場合、単一のSQLクエリで取得を行うことが難しくなります。

単一のSQLクエリで取得可能なのは、直近の子か、固定した深さまでの子孫の取得のみです。しかし、コメントの返信の深さに制限がないため、全てのコメントを取得するには、大量のSQLクエリが必要になってきます。

上記のテーブルの例で、id = 1 の直近の子（id = 2, 3）を参照する場合は以下のSQLになります。

SELECT * FROM Comments c1 
LEFT OUTER JOIN Comments c2 ON c1.id = c2.parent_id WHERE c1.id = 1;

さらに、三つ目の深さのコメントを取得するためのSQLは以下になります。

SELECT * FROM Comments c1 
LEFT OUTER JOIN Comments c2 ON c1.id = c2.parent_id 
LEFT OUTER JOIN Comments c3 ON c2.id = c3.parent_id 
WHERE c1.id = 1;

このように、固定の深さであればSQLクエリを用意できますが、可変の深さのコメントを取得することができません。

データ削除

また、連鎖している返信コメントの中間のコメントを削除する際に、その子要素の parent_id を変更する必要が出てくるため、単一のSQLクエリでは実行できません。

ナイーブツリーパターンの改善方法

経路列挙

経路列挙は、先祖の系譜を表す文字列を各ノードの属性として格納することで、解決します。

先祖の系譜を表す文字列とは、例えば「1/2/3」というものです。これは、id = 3 の親が id = 2 で id = 2 の親が id = 1 であることを示しています。

経路列挙を使ったテーブルの例を以下に示します。

この構造をとることで、取得する際にパターンマッチを使用して一つのSQLクエリでデータを取得できます。

一方、デメリットとしては、以前のアンチパターンとして紹介した「ジェイウォーク」に違反します。

また、データの更新や削除時に元のナイーブツリーモデルよりも多くのクエリが必要になります。

入れ子集合

入れ子集合は、直近の親ではなく、子孫の集合に関する情報を各ノードに格納します。この情報は、各ノードのnsleft, nsrightと呼ばれる数値で表されます。

「left」より大きく「right」より小さいものが子孫になり、

「left」より小さく「right」より大きいものが先祖になります。

上記のテーブルのnsleft, nsrightは深さ優先探索を用いることで簡単に割り当てることができます。

上記のテーブルで、例えばid = 4 に紐づく子孫のコメントみたい場合は、id = 4 の nsleft と nsright の間に nsleft が含まれるノードを全て検索することで取得できます。以下がSQLの例です。

SELECT * FROM Commentes AS c1 
INNER JOIN Comments AS c2 ON c2.nsleft BETWEEN c1.left AND c1.nsright 
WHERE c1.id = 4;

メリットとしては、子孫や先祖を一括で一つのSQLクエリで取得することができます。

デメリットとしては、データの更新や削除時に「nsleft」「nsright」の再計算が必要になったり、直近の親子だけを

取得したいだけなのに取得が面倒になってしまうことが考えられます。

閉包テーブル

閉包テーブルは、階層構造のシンプルかつエレガントな格納方法です。別テーブルでノード同士の関係性を定義して菅りす流モデルです。

直近の親子関係のみではなく、離れたノードの親子関係と自信を参照するパスも含めます。

メリットとしては、ツリーの取得が容易であったり、追加・削除・更新も容易になります。また、外部キー制約を用いることでデータの整合性も維持しやすいです。

デメリットとしては、データ量がかなり多くなることが考えられます。

まとめ

ナイーブツリーモデルのデメリットに対する解決案が三つもあり、どれを選択するのがよいかがわからないくなりそうですが、テーブルを使ってどんなアプリケーションを作るのか、CRUDのうちどれをよく多用するのか、ということを加味しながらそれぞれのパターンのメリットを活かして選択していく必要がありそうです。