入れ子区間モデルという幻想

珍しく、C++とは関係のない記事です。
RDBの話ですがSQL文は出てきません。

入れ子区間モデル

RDBで階層構造を表すために、入れ子集合モデルというものがあります。
テーブルに整数で範囲を示す値を入れて、子階層を親階層の内側に追加していくことで、一括してデータを取ってこれるようにしようという考え方です。
で、その整数を実数に拡張したものを入れ子区間モデルと呼ぶらしいです。
詳しくはググってください。ただし、ググって出てきた記事を鵜呑みにしてはいけません。

何が問題なの？

入れ子区間モデルという考え方は、そう悪いものではありません。ただし、それは無限精度の実数（厳密には有理数）を扱えるなら、という前提があって初めて成り立ちます。
少なくとも、MySQLでは無限精度実数を扱えません（プログラミング言語で実装されたものをバイナリシリアライズして値に持たせることはできますが）そして、たかだか64bitしかないMySQLのREAL型は、入れ子区間モデルの考え方に従って分割していくと、あっという間に枯渇します。
具体的に考えてみましょう

MySQLのREAL型は、IEEE 754 binary64の浮動小数点型です。C/C++のdouble型なんかは大抵これと同じ形式です。規格で定められているわけではありませんが。

binary64

+------+--------+--------+
| sign |exponent|flaction|
|(1bit)|(11bit) |(52bit) |
+------+--------+--------|

一々こんな図を書くのは面倒なので、こんな感じで16進表現しようと思います。

S: 0 or 1
O: 0 ~ 7
X: 0 ~ F (16進)

S|OXX|X:XXXX:XXXX:XXXX
^  ^         ^
|  |         |
|  |       仮数部(:はただの桁区切り)
| 指数部
符号

例えば、0はこうなります。

0|000|0:0000:0000:0000

指数部と仮数部が最大の数が最大になるので、

0|7FE|F:FFFF:FFFF:FFFF

これが最大の浮動小数点数になります。(指数部が7FFの時はInfかNaNを表す）
これをmaxとしましょう。実際の値は、

max = 1.7976931348623157e+308

になります。

0.0~max を初期範囲として、入れ子区間モデルを考えてみます。実際は、初期範囲をどこにとっても、問題は変わりません。

一つ目のノードを挿入する時、区間の左端と右端の値をそれぞれleft, rightとすると、

left = max / 3
right = max / 1.5

となります。
実際の値とそれを表現した16進表現は

left = 5.992310449541053e+307

0|7FD|5:5555:5555:5555:5555

right = 1.1984620899082105e+308

0|7FE|5:5555:5555:5555:5555

となります。

おわかりいただけただろうか……
この時点で、上位12bit分がほぼ使えなくなっています。
0~maxの中間をとったと思ったら、52bit分の領域しか残っていませんでした、という状態です。

ちなみに、rightより上の領域は、52bit分の更に2/3の領域しか残っていません。
そこで、後ろ側にもう一つノードを追加してみます。新しい区間を[left2, right2]で表すと、

left2 = right + (max-right) / 3
right2 = right + (max-right) / 1.5

left2 = 1.3982057715595789e+308

0|7FE|8:E38E:38E3:8E38

right2 = 1.5979494532109474e+308

0|7FE|C:71C7:1C71:C71C

一回目と比べれば、領域の減少は少ないです。というのも、指数部が同じなら仮数部は等間隔に分布しているので、3で割れば単純に領域は1/3になるからです。
とは言え、このまま後方にノードを挿入していくことを考えると、指数的に領域が狭くなっていきます。
ざっと計算してみただけなので誤差があるかもしれませんが、大体34回ノードを後方挿入すると領域が枯れます。

解決策

無限精度実数を使う

PostgreSQLには無限精度実数があるそうです。
まあ、無限と言っても、実際には制限があるようなのですが、これを使えばかなり使える資源が増えるので、問題は発生しづらくなるかと思います。
ただし、無限精度の演算はソフトウェアで実装されているので、動作は遅くなるでしょう。
MySQLでは無限精度実数は存在しませんが、上で少し触れたように、無限精度実数ライブラリを利用して、比較可能な形でシリアライズされたものを値にすれば動作させることは可能だと思います。
試してはいませんが、データ使用量と速度に問題がなければ、採用しても良いと思います。

定期的に最適化する

領域が枯渇することがないように、定期的にテーブルの中を調べて領域を振り分けるサービスを動作させるという解決策もあります。
ただし、最適化が行われる前にリソースが枯れそうになった場合、新しいノードが挿入する前に最適化を行わなければならないため、ブロッキングが発生する可能性があります。
それにわざわざそんなサービス作るのクッソめんどくさ（略）

入れ子区間モデルなんて投げ捨てる

そもそもRDBは木構造を扱うための物じゃNEEEE！
でも、どうしてもRDBで木構造を扱いたいのであれば、経路列挙モデル（ファイルパスみたいなものを入れるカラムを作る方法）の方がまだいいのではないでしょうか。

そんなの気にしないぜ俺は入れ子区間モデルを使う

領域が枯渇しないことが十分に保証できるケースなら問題は発生しないでしょう。私はオススメしませんが。
ちなみに、精度の問題は結局のところ整数型を使っても変わらないので、どうしてもと言うなら、入れ子区間モデルではなく入れ子集合モデルを使っても同じではないでしょうか。

終わりに

私はDBに関してはあまり明るくないので、DBに詳しい方にとっては「そんなのは100年前に通った道だぜ」みたいなやつかもしれません。
ネット上で見てみた限りでは、この問題に触れている情報があまり見つからず、見つかったとしても「そんなすぐ枯れることはないから大丈夫だよね」みたいな楽観的な情報だったので、ここは一つ実際にどれくらいで枯れるのか計算してみた次第です。
こうすれば大丈夫だよ、みたいな方法が他にあれば、ツッコミを入れていってください