LoginSignup
157

More than 3 years have passed since last update.

2章 Naive Trees(素朴な木)

Last updated at Posted at 2014-08-28

第二章 ナイーブツリー

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

目的

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

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

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
157