【アールぎ】
R木 とは？
公開:
💡 図形を囲む箱を、さらに大きな箱へまとめる索引
図形を囲む矩形を階層的にまとめ、空間的な検索の候補を絞る索引構造。地図上の範囲検索などに使われ、領域の重なりを許す。
📌 このページのポイント
- 軸に平行な外接矩形を使い、複数の対象を階層的にまとめる
- 兄弟の矩形が重なることがあり、検索時には複数の枝をたどる場合がある
- 図形を矩形で近似した場合、候補を絞ったあと実際の形でも判定する
ひよこ 普通の索引で地図を検索できないの？
ペンギン先生 一つの値の大小順だけでは、平面上の重なりを扱いにくいよね。R木は各図形を囲む矩形を持ち、それらをまとめる矩形を上の階層へ作る。検索範囲と交わらない箱は、中身ごと候補から外せるんだ。
ひよこ 四分木みたいに地図を切り分けるの？
ペンギン先生 R木は対象を囲む矩形をまとめるので、兄弟の矩形同士が重なってもよいんだ。空間を重ならない四区画へ分ける図とは違うね。検索範囲が両方の箱にかかれば、両方の枝を調べる必要があるよ。
ひよこ 箱の中に点があれば、図形の中でもある？
ペンギン先生 そうとは限らないよ。三角形を囲む四角い箱には、三角形ではない余白があるよね。R木で候補を絞ったあと、元の図形と本当に交わるかを判定する。対象そのものが矩形なら、矩形の判定で答えが得られる場合もあるんだ。
ひよこ 木が浅ければ、毎回すぐ見つかる？
ペンギン先生 R木は葉の深さをそろえるけれど、箱の重なりが多いと調べる枝も増えるよ。高さが抑えられていることと、検索で一本の道だけ進めることは別なんだ。SQLiteのR*Treeのように、まとめ方を工夫した派生方式もあるよ。
もっと詳しく知りたい人へ
浮動小数点で保存した矩形は厳密ですか？
座標の保存形式を確認します。SQLiteのrtreeは通常32ビット浮動小数点で境界を外側へ丸めます。重なり検索では余分な候補が出る場合があり、完全包含を調べる条件では境界付近への配慮が必要です。R木一般の定義と個別実装の精度を区別します。
まとめ：ざっくりこれだけ覚えればOK！
「R木」って出てきたら「外接矩形の階層で、空間検索の候補を絞る索引」と思えればだいたいOK！