![見出し画像](https://assets.st-note.com/production/uploads/images/88091163/rectangle_large_type_2_4e3b90dbb7ded60692fc0d723542a7fc.png?width=1200)
【SQLアンチパターン】ナイーブツリーと閉包テーブル
こんにちは、CryptoGamesの高橋です。
ブロックチェーンサービスを行っている会社です。
今回は「SQLアンチパターン」の第3章の「ナイーブツリー(素朴な木)」について、見ていきます。
では早速、見ていきましょう。
1 今回扱うケース
下のようなスレッドが存在するとします。
いろんな人が書き込みを行っていますね。
枝分かれや、スレッドが下に伸びていったりしています。
![](https://assets.st-note.com/img/1664624551600-pDkgl09vhl.png?width=1200)
例えば「1」のコメントに対して、2つのスレッドが立っている、といった具合です。
![](https://assets.st-note.com/img/1664624810426-iQSKeCOMlT.png?width=1200)
このような、ツリー状の階層をデータベースに格納するのはどうしたら良いでしょう。
2 用語の整理
ここで、用語の整理です。
それぞれの一つ一つを「ノード」と呼びます。
![](https://assets.st-note.com/img/1664656568490-SwKCU12VIB.png?width=1200)
上のように、先端を「リーフ(葉)ノード」と呼びます。
その中間の、ルートでもリーフでもないものが「非葉ノード」です。
3 アンチパターン 隣接リスト
3ー1 隣接リストの概要
アンチパターンとして紹介されていたのが「隣接リスト」です。
下のように、「そのコメントの親は誰か」に着目する構成です。
![](https://assets.st-note.com/img/1664624911014-UuXUSoJx5v.png?width=1200)
例えば、上のように、「コメント3の親はコメント2」、「コメント2の親はコメント1」となります。
3ー2 隣接リストの構成
テーブルの構成は下のようになります。
「親ID」を設定し、そのコメントの親がどれであるかを入力します。
![](https://assets.st-note.com/img/1664625078552-HA9zs5UInC.png?width=1200)
3ー3 先祖のノードの取得の概要
では、例えば、コメント7の先祖を取得するためにどうすれば良いでしょう。
ちなみに、図で見れば簡単です。
下のように、1、4、6が先祖になります。
![](https://assets.st-note.com/img/1664625572087-2xXeuopLFY.png?width=1200)
3ー4 先祖のノードの取得のデータベースでの実施
では、データベース上はどのように取得するでしょう。
下のように、コメントテーブルをさらに右にくっつけることで実現します。
例えば、7番目の親は6なので、右にコメントID6の行をくっつけています。
![](https://assets.st-note.com/img/1664625154897-lzqpve5FcI.png?width=1200)
これによって、次のようにわかります。
・コメント7の親はコメント6
・そのコメント6の親はコメント4
![](https://assets.st-note.com/img/1664625720078-fRb5dl7gZx.png?width=1200)
3ー5 隣接リストの問題点
でも、1つ繋げただけだと、全部の先祖はわかりませんね。
下のように、今回はテーブルを3個つなげることで、ようやく全ての先祖を辿ることができました。
![](https://assets.st-note.com/img/1664625852004-umWx6C6qQG.png?width=1200)
でも、これだと、階層が深くなればなるほど、テーブルを繋げなければいけませんね。
これが、この隣接リストがアンチパターンと呼ばれる理由です。
4 解決策① 経路列挙(Path Enumeration)
4ー1 経路列挙の概要
では、この解決策の一つである、「経路列挙」を見てみましょう。
特徴は「隣接リスト」のような「親ID」ではなく、パスを格納しているという点です。
![](https://assets.st-note.com/img/1664626003154-sMGGmfX1KT.png?width=1200)
4ー2 経路列挙の利点と欠点
確かにこれなら、どれだけ階層が深くなっても、テーブルをつなげることなく、先祖や子孫を抽出することができます。
ただ、これには下のような問題点も残っています。
![](https://assets.st-note.com/img/1664626019984-JMpoWaAi3j.png?width=1200)
上のように、入力ミスが発生するかもしれません。
このような入力ミスの検出が困難なのが欠点です。
5 解決策② 閉包テーブル(Closure Table)
5ー1 閉包テーブルの概要
これらの問題を解決するために、「閉包テーブル」を使います。
なお、今回は本書に紹介されていた「入れ子集合」の解説は割愛します。
これは「親ー子」の関係ではなく、「先祖ー子孫」の関係に着目したやり方です。
![](https://assets.st-note.com/img/1664654678497-0m92SxBiWE.png?width=1200)
例えば上のように、「1」の子孫は「2、3、4、5、6、7」となります。
それを下のような専用のテーブルに格納します。
なお、テーブルの1行目のように、「1」の子孫として自身である「1」も含めます。
![](https://assets.st-note.com/img/1664655005265-daSwO7lvew.png?width=1200)
他にも、例えば、4の子孫は「5、6、7」ですね。(テーブルには子孫に「4」も含めます。)
![](https://assets.st-note.com/img/1664655223839-3AywSLLhMB.png?width=1200)
このように、今まで「親ID」や「パス」として同じ列にあった経路関係の列を切り離しているのが特徴です。
![](https://assets.st-note.com/img/1664655254764-TxB0DgGEOc.png?width=1200)
では、実際にこのテーブルでいろいろな操作が可能かを見てみましょう。
5ー2 先祖ノードの検索
例 7の先祖を検索する
下のように、「子孫」が7の行を検索すれば、見つかります。
![](https://assets.st-note.com/img/1664655318700-GJ1I7u30YT.png?width=1200)
5ー3 子孫ノードの検索
例 4の子孫を検索する
下のように、「先祖」が4の行を検索すれば、見つかります。
![](https://assets.st-note.com/img/1664655465903-oFlUVS3xwo.png?width=1200)
5ー4 ノードの追加
下のように、ノードを追加するとしましょう。
![](https://assets.st-note.com/img/1664655515455-KKcN9VYDh0.png?width=1200)
この場合、その先祖の組み合わせを追加すれば良いですね。
5ー5 非葉ノードの削除
下のように、6以降のコメントを削除するとしましょう。
![](https://assets.st-note.com/img/1664656783577-TIuF3uFbkv.png?width=1200)
このように、「子孫」が「6、7」のものを消せば良いですね。
5ー6 ノードの付け替え
下のように、6以降のコメントを3の下に付け替えるとしましょう。
![](https://assets.st-note.com/img/1664657216035-sdGFl7Z1UR.png?width=1200)
この場合は、まず現在の関係を断ち切るために、子孫が「6、7」の行を消します。
![](https://assets.st-note.com/img/1664657256817-iWZTQuxQAD.png?width=1200)
その後、下のように、新しく先祖になる部分を追加すれば良いですね。
![](https://assets.st-note.com/img/1664657020620-uAOmU6HWSH.png?width=1200)
5ー7 入力誤りのチェック
では、下のような、入力誤りを事前に防ぐことはできるでしょうか?
これは「経路列挙」では難しい問題でした。
![](https://assets.st-note.com/img/1664657685646-m8IUHP6fFj.png?width=1200)
ただ、今回は、コメントテーブルのコメントIDにないものは、そもそも入力できないようにすれば良いですね。
![](https://assets.st-note.com/img/1664657654285-a2dud72v5e.png?width=1200)
5ー8 閉包テーブルの問題点は?
こんな便利な閉包テーブルに問題はあるのでしょうか?
本書に書かれている問題としては、階層が深くなると、その分行数が増えていくということでした。
![](https://assets.st-note.com/img/1664657960287-pVoc7EGdMi.png?width=1200)
6 最後に
いかがでしたでしょうか。
本書では「隣接リスト」の解決策として3つが紹介されていました。(うち、一つはこの記事では割愛)
その中で、最後の「閉包テーブル」を下のように書いていました。
「最も用途が幅広く、また唯一、ノードが複数のツリーへ所属することができます。」
私も個人的には、「閉包テーブル」がしっくりきました。
本記事は以上です。
皆さんの理解の一助になれば幸いです。
サポートをしていただけたらすごく嬉しいです😄 いただけたサポートを励みに、これからもコツコツ頑張っていきます😊