なんとなく気になったので書いておく。
SQLでツリー構造を実現するときに、親要素のIDだけを覚えておく構造を「ナイーブツリー」と言って、世の中ではアンチパターン、つまり「使ってはいけません」ということになっているらしい。 じゃあどうするのかというと、親要素だけではなく、祖先すべてのIDを記録しておくのがよろしい、と。 つまり、親・子・孫・ひ孫のひ孫に当たる要素については、レコードを3個作って、祖先IDフィールドにそれぞれ親・子・孫のID を書くと。 「閉包テーブル」というやつ。
が、ファイルシステムのディレクトリ構造みたいなものを考えた場合、「親」に100個の「子」要素があり、それぞれの「子」に100個の「孫」要素があると、「親」は10100個の要素を抱えていることになる。
この状態で祖先に「親」を持つ要素をクエリすると「子」と「孫」全部、10100個のレコードが返ってきてしまう。
しかも、親にもうひとつフォルダを作って、今まで子だった100個のレコードをそのフォルダの下に移そうとすると、10100個のレコードを新たに作る必要がある。
逆に親フォルダに移すならレコードを削除する必要があるし、一番上の親から枝分かれした別のフォルダ、たとえば、/home/user/tmp/app を /tmp/app/user/data に移したい場合なんかは、app以下にあるレコードの祖先情報をすべて書き換える必要がある。
そんなの考えたくない。
こういう用途には閉包テーブルは明らかに向いてない。
逆に、ナイーブツリーが苦手なのはメールのスレッドのようなもので、1年間、毎日1通、ずっと返信を続けてきたスレッドなんかは、再帰クエリのできないDBではナイーブツリーだと356回クエリを繰り返す必要がある。 閉包テーブルなら一発でスレッドに含まれるメールをすべて取得できる。 そしてメールクライアントではスレッドに含まれるメッセージをすべて取得するというのは割と普通の状況なわけだ。
ファイルシステムなんかは356階層もディレクトリ掘ったらそもそも人間がたどりつくのが容易ではなく、実用的ではない。メールのスレッドは長くなることはあるけど、100人がそれぞれコメントをつけてきて、さらにそのコメントに100人がコメントをつけてくることはあまりないだろうし、要素を移動してしまったらスレッドがぐちゃぐちゃになってしまうから、管理者特権以外でそんなことをする人はいない。 迷惑メールを削除する程度だろう。
横に広く、深さが浅いツリーで、子孫要素を丸ごと移動する可能性があるものは、むしろ閉包テーブルの方がアンチパターンで、ナイーブツリーを使うのが正しいと思う。実際、世の中のファイルシステムはほぼすべてナイーブツリーだと思うし、「経路列挙モデル」はもっとダメだと言われているが、AWSのS3は、実はフォルダという概念がなく、おそらく経路列挙モデルではないだろうか。 枝分かれが少なく、深さが深いツリーはナイーブツリーは確かにアンチパターンで、閉包テーブルの方が向いている。 エンジニアは考えてナンボ、人の言うことは鵜呑みにするな、ということか。 この記事も含めて。
03 Nov 2022: 初稿
Copyright (C) 2022-2023 akamoz.jp
$Id: sql-naive-tree.htm,v 1.2 2023/01/09 06:16:24 you Exp $