---

それぞれの団体に関して、グループ機能という、メーリングリスト的な機能を付与しようと思っていたのですが、その木構造を、二次元表であるRDBMSで表現しようとなると結構厳しいものがあったりします。
というか、長年の間、木構造の表現が難しいことは弱点とされてきており、いろんな手段が考えられてきていました。

いやｗｗｗ木構造って親のデータ持てばそれを再帰的に取ってきたらいいだけやんｗｗｗｗｗｗって思われるかも知れませんが、SQLでこういう再帰的なクエリを書くのはマズいんですよね･･････。
まぁ何故かってのはここは技術エントリじゃないつもりなので書かないつもりですけど･･････とりあえず、処理が半端なく重くなるということです。たぶん。


その中で考えられてきた方法のひとつが「閉包テーブル」という手法で解決しようとしたのですが、調べていくうちに入れ子区間モデルというものにたどり着きました。

このモデルは、前身として入れ子集合モデルというものがあり、木構造を入れ子構造として捉え直したことで、二次元表で再現できるようにしたモデルです。
具体的なメカニズムとかはググってもらった方がはやいのですが、理にかなっていてすごくわかりやすいモデルだと思います。

ただ、その欠点は、新たに子を挿入する際、スペースが余ってなかった場合、論理的に関係のない他のカラムに対してもUPDATEをかけなきゃいけない、つまりデータ量が増大するにつれエラーを引き起こしやすいんですね。更新時ロックとかの影響をモロに受けるわけです。
僕の想定するシステムは、全ての団体の木構造を1つのテーブルで管理することになるので、ちょっとその仕様は厳しそうですね･･････。


その欠点を埋めるために考案されたのが、「入れ子区間モデル」です。
入れ子集合モデルの更新時の負荷が何故引き起こされるのかというと、その数値が整数だから色々問題がおきるわけですね。じゃあだったら、小数点まで許容してはどうだ？？ということで考案されたのが、この入れ子区間モデルというやつですね。

原理的にはこれで無限にノードを挿入できるのですが、実際はMySQLだと使える小数点の桁数に限度があるようで、REAL型だと大体30数回ノードを挿入すると領域が枯れるらしいです。
これは階層の話じゃなく、どちらかというと回数の話に近いですね。


具体的に説明すると、ノードを3分割し、 その真ん中のエリアに新しい円を挿入していくわけですが、その兄弟ノードはその隣の1/3のエリアの中を、さらに3分割したその真ん中のエリアとして挿入されていくロジックになります。
これを言い換えると、30以上の親グループを作ることは不可能ということになり、ちょっとこれを採用するのは厳しそうな気がしますね。
小数点を無限に取れる保障があるのならよかったんですが、やはり閉包テーブルを採用するしかなさそうですかね･･････



閉包テーブルのデメリットはなんでしょうね。
リソースが実質無限になるので(IDが自由に振れる)、枯渇の心配はないのですが、階層が深くなるごとに指数関数的にデータが増大します。とはいえ、そんな深い階層のデータを扱うことは稀だと思いますのでこの欠点は許容できそうですね。

あと、中途半端に木構造の末端でない子を削除する際も結構めんどくさそうなのですが、僕が取り扱うのはフォルダ構造なので、親を削除する際は子も例外なく削除するという構造になっているので、ここもスルーできそうですね。
ということで、閉包テーブルを採用してもよさそうですね･･････。



なんかなんも進展してない感じがしますけど、そんな感じで実装していくことにしましょーーかね。