2章 Naive Trees(素朴な木)

第二章 ナイーブツリー

「ブログのコメント欄をスレッド形式で見れるようにしたいよね・・・」



## 目的
階層構造を格納して、クエリを実行する

こんなテーブル設計したとして、


| comment_id | parent_id | comment | etc |
|:-:|:-:|:-:|:-:|
| 1 | NULL | 眠い | 根 |
| 2 | 1 | そこなー | 非葉 |
| 3 | 2 | うっわ中2 | 葉 |
| 4 | 1 | ガチネム | 葉 |

ここにコメントの階層構造を格納する

comment_id=1に関係するコメントを全て取得したいとき

```sql
SELECT
     c1.*, c2.*
FROM
     Comments c1

     LEFT OUTER JOIN Comments c2
     ON c2.parent_id = c1.comment_id    
```
↑これでは2階層だけなので・・・

```sql
SELECT
     c1.*, c2.*, c3.*
FROM
     Comments c1

     LEFT OUTER JOIN Comments c2
     ON c2.parent_id = c1.comment_id    

     LEFT OUTER JOIN Comments c3
     ON c3.parent_id = c2.comment_id    
```
↑3階層・・・・！

#### これだと何が辛いか
- 一発でツリー構造を取得みたいなことが出来ない
- 関連するコメント数を取得するみたいなクエリも同様


また、comment_id=2を削除するときは

| comment_id | parent_id | comment | etc |
|:-:|:-:|:-:|:-:|
| 1 | NULL | 眠い | 根 |
| 3 | 2 → 1 | うっわ中2 | 葉 |
| 4 | 1 | ガチネム | 葉 |

整合性を取るために`UPDATE`が必要になる
(論理削除だと上記対応は不要)


## ここでのアンチパターンとは・・・
親のみに依存した構造だと
 -> 上記の様にツリー構造を取得するのに不便
 -> また、整合性を保つのに一苦労
 -> 素朴(ナイーブ)が故に貧弱




## みつけかた
##### _このツリーでは深さを何階層までサポートすればいい？_

再帰的に取得できないことからくる辛み

##### _孤児になった行を綺麗にするために定期的にスクリプトを実行しなければ_

いちいち整合性を取るのが面倒という辛み


##### _ツリー型のデータ構造を扱うコードなんて二度と書きたくないな_

上記2つを悟った辛み

##アンチパターンを使っても良い場合
1. 仕様を満たせる場合
しっかりツリー構造保持しなくていいよ系
n階層まででいいよ系

2. DBが再帰クエリ構文をサポートしている場合
1クエリでツリーの取得ができる


## どうすれば良いのか → 別の構造を検討する！

### 1. 経路列挙モデル
| comment_id | path | comment | etc |
|:-:|:-:|:-:|:-:|
| 1 | NULL | 眠い | 根 |
| 2 | 1/2/ | そこなー | 非葉 |
| 3 | 1/2/3/ | うっわ中2 | 葉 |
| 4 | 1/4/ | ガチネム | 葉 |

```sql
SELECT
	*
FROM
	Comments AS c
WHERE
	'1/2/3/' LIKE c.path || '%';
```
`1/%`と`1/2/%`に一致

##### メリット
- クエリ一発でツリー構造を取得できる

##### デメリット
- なんというかJaywalk -> http://qiita.com/iwata@github/items/f33490d34dd1400b166e#1-2
- バリデーションはアプリケーション側依存
- 物理削除を行った時は隣接リストモデルよりも多くのクエリの修正が必要



### 2. 入れ子集合モデル
| comment_id | nsleft | nsright | comment | etc |
|:-:|:-:|:-:|:-:|:-:|
| 1 | 1 | 8 | 眠い | 根 |
| 2 | 2 | 5 | そこなー | 非葉 |
| 3 | 3 | 4 | うっわ中2 | 葉 |
| 4 | 6 | 7 | ガチネム | 葉 |

?????

##### メリット
- こちらもクエリ一発でツリー構造を取得できる
- どこかを物理削除しても(再計算すれば)自動的に反映される

##### デメリット
- 近接の親子の取得が面倒

```sql:親を取得する
SELECT
	parent.*
FROM
	Comments as c

	INNER JOIN Comments as parent
	ON parent.nsleft < c.nsleft AND c.nsleft < parent.nsright
	LEFT OUTER JOIN Comments AS in_between
	ON in_between.nsleft < c.nsleft AND c.nsleft < in_beetween.nsright
	AND parent.nsleft < in_between.nsleft AND in_between.nsleft < parent.nsright

WHERE
	c.comment_id = 3
	AND in_between.comment_id IS NULL;
```

> バグの温床臭半端ない

- コメントの追加削除されるたびに再計算が必要


### 3. 閉包テーブルモデル
| comment_id | comment | etc |
|:-:|:-:|:-:|
| 1 | 眠い | 根 |
| 2 | そこなー | 非葉 |
| 3 | うっわ中2 | 葉 |
| 4 | ガチネム | 葉 |


| ancestor | descendant |
|:-:|:-:|
| 1 | 1 |
| 1 | 2 |
| 1 | 3 |
| 1 | 4 |
| 2 | 2 |
| 2 | 3 |
| 3 | 3 |
| 4 | 4 |

##### メリット
- 親子の検索、ツリーの検索、コメントの追加削除、整合性の維持が容易

##### デメリット
- レコード数が爆発的に増える


## まとめ

| 設計 | 親子へのクエリ | ツリーへのクエリ | 挿入 | 削除 | 整合性維持 | ひとこと |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 隣接リスト | 簡単 | __複雑__ | 簡単 | 簡単 | __複雑__ | 仕様を満たすのであれば最もシンプルで簡単 |
| 隣接リストw再帰クエリ | 簡単 | 簡単 | 簡単 | 簡単 | 簡単 | RDBMSに再帰クエリが対応していれば最も簡単 |
| 経路列挙 | 簡単 | 簡単 | 簡単 | 簡単 | __不可__ | Jaywalk的なデメリットが問題なければ |
| 入れ子 | __複雑__ | 簡単 | __複雑__ | __複雑__ | __不可__ | ツリーの詠み込み専門職 |
| 閉包テーブル | 簡単 | 簡単 | 簡単 | 簡単 | 簡単 | 容量とるのとトレードオフ |