Edited at

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/%に一致


メリット


  • クエリ一発でツリー構造を取得できる


デメリット


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的なデメリットが問題なければ

入れ子
複雑
簡単
複雑
複雑
不可
ツリーの詠み込み専門職

閉包テーブル
簡単
簡単
簡単
簡単
簡単
容量とるのとトレードオフ