2章 Naive Trees(素朴な木)

第二章 ナイーブツリー

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

目的

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

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

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

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

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

SELECT
     c1.*, c2.*
FROM
     Comments c1

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

↑これでは2階層だけなので・・・

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/	ガチネム	葉

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	ガチネム	葉

?????

メリット

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

デメリット

• 近接の親子の取得が面倒

親を取得する

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的なデメリットが問題なければ
入れ子	複雑	簡単	複雑	複雑	不可	ツリーの詠み込み専門職
閉包テーブル	簡単	簡単	簡単	簡単	簡単	容量とるのとトレードオフ