たにしきんぐダム

プログラミングやったりゲームしてます

空間インデックス(R-tree)入門

DB tech

R-treeとは空間データを効率良く検索するためのインデックス構造。R-tree について調べたのまとめておく。

目次

参考資料

ナイーブな例

例えば、x座標とy座標をもつデータを格納するテーブルがあり、ある点の近くのレコードをこのテーブルから取得したいとする。

CREATE TABLE `geometries` (
  `name` VARCHAR(100) NOT NULL,
  `loc_x` DOUBLE NOT NULL,
  `loc_y` DOUBLE NOT NULL
);

一番ナイーブなやり方は、ある点と全てのレコードとの距離を計算して距離の順番にソートしてやることだろう。 しかしこのやり方だと近くのレコードを取得したいだけなのに、すべてのレコードとの距離を計算しなくてはならない。

SELECT name, SQRT(POWER($x - loc_x) + POWER($y - loc_y)) AS dist
FROM geometries WHERE dist < 100.0;

それでは、以下のテーブルのように、 region というカラムを追加しておいて、先に region による絞り込みをしてはどうだろうか。

CREATE TABLE `geometries` (
  `name` VARCHAR(100) NOT NULL,
  `loc_x` DOUBLE NOT NULL,
  `loc_y` DOUBLE NOT NULL,
  `region` VARCHAR(100) NOT NULL,
  KEY `idx_region` (`region`)
);

こうすると距離の計算が必要になるのは region で絞り込まれたレコードのみとなり、先ほどの例よりかは効率よく検索することができる。

SELECT name, SQRT(POWER($x - loc_x) + POWER($y - loc_y)) AS dist
FROM geometries WHERE region = "some_region" AND dist < 100.0;

しかし距離は近いのに region が違うからヒットしないというようなことなどが起こるかもしれないし、 region によってレコードが集中していたりしていなかったりして検索効率も安定しないかもしれない。

区画で絞り込んだ後に厳密な距離による絞り込みというのは良い線をしていると思うが以下のようなことが叶うと良いだろう。

  • 近くのレコードどうしで区画を分けたい
  • 区画ごとにレコードの数が均一になり、検索時間が安定して欲しい

これを叶えるのが R-tree である。

R-tree の概要

R-tree は階層的に入れ子になった重なり合う最小外接矩形(Minimum Bounding Rectangle: MBR)により空間を分割する。つまり近くのレコードどうしを囲うMBRにより区画を分けることで、辿るべきノードを絞り込み検索効率を向上させる。

f:id:tanishiking24:20160401003304p:plain

f:id:tanishiking24:20160401003548p:plain

上の図が実際のデータ構造、下の長方形がたくさんある図は各ノードが持つ最小外接矩形(MBR)を描いたイメージ図。

  • 内部ノード/根ノードのエントリは以下のデータを持ち
    • 子ノードへのポインタ
    • 子ノードの全エントリを包含するMBR
  • 葉ノードのエントリは以下のデータを持つ
    • データオブジェクトへのポインタ
    • データオブジェクトを表すMBR

各ノードの要素数

木のバランスはどのように保たれるのだろうか。

各ノードが持つ最大要素数を M とするとき(上の図では3のようです)、 m <= M/2 というように m を定めると

  • 各ノードは m 個以上 M 個以下の要素を持つ
  • 根ノードは(それが葉ノードでない限り)最低2つの要素を持つ

というような制約を各ノードに定める。このルールに遵いながらデータの挿入/削除をすることで木のバランスを保ち検索効率を均一に保つことができる。

m の値を変えることによって、各ノードのデータサイズの大小、木の高さが変わってきて検索効率・挿入削除効率にも影響が出てくるだろう。

参照処理

点検索

f:id:tanishiking24:20160401020453p:plain

上の図の赤い地点を包含するレコードを探索したい場合(答えはR8, R9)のアルゴリズムは以下のようになりる。

  1. 根ノードから出発
  2. 葉ノードでない場合、検索地点を含む子ノードに対して再帰的に2を実行
  3. 葉ノードな場合、検索地点を含むデータオブジェクトを取得

上の図の例の場合だと

  1. 根ノードから探索(R1がマッチ)
  2. R1に進む、R1は葉ノードでないのでR1の要素を探索(R3,R4がマッチ)
  3. R3,R4に進む、R3ではR8が、R4ではR9がマッチ
  4. R8, R9 はそれぞれ葉ノードなのでこれらのノードが持つデータオブジェクトのidを取得

という感じ。

範囲検索

f:id:tanishiking24:20160401022102p:plain

上の図の赤い部分と重なる空間データを取得するクエリです。(答えはR7, R8, R9, R10)
これを探索するアルゴリズムは以下のような感じ

  1. 根ノードからスタート
  2. 葉ノードでない場合、検索範囲と重なる子ノードに対して2を実行
  3. 葉ノードな場合、検索範囲と重なるデータオブジェクトを取得

上の図の例の場合だと

  1. 根ノードから探索(R1, R2がマッチ)
  2. R1以下ではR3, R2内ではR4がマッチ
  3. R3,R4に進む、R3ではR7, R8が、R4ではR9, R10がマッチ
  4. R7~R10 はそれぞれ葉ノードなのでこれらのノードが持つデータオブジェクトのidを取得

データの挿入・削除

R-tree では B-tree と同様に挿入・削除・更新処理の際に木の再構築が行われ平衡な木の状態が保たれる。

挿入処理

f:id:tanishiking24:20160403005304p:plain:w450

新しく追加するデータオブジェクトに対応するキーをEとする

  1. Eが所属すべき近接する葉ノードを探索
  2. 葉ノードに空きがあれば挿入しMBRを拡大。親ノードのMBRも拡大していく
  3. 空きがなければノードを分割(分割アルゴリズムは後述)

R5には空きがなかったので、以下のように"良い感じ"にR16とR17に分割される f:id:tanishiking24:20160404145123p:plain

f:id:tanishiking24:20160404144550p:plain

(このときR16,R17,R6のノードが溢れた場合同様の分割がどんどん行われていくことになる)

ノードの分割

上で述べたように、満杯になったノードに要素を追加しようとするとノードの分割が発生する。木を平衡に保ち・空間的な効率も良くデータを格納するためにはできるだけ各ノードのMBRが小さくなるように工夫してノードの分割を行う必要がある。

Exhaustive Algorithm

MBRが最小になるよう分割するにはすべての組み合わせに対して全探索を行う。 計算量はO(2^M)とかなり大きくなり挿入処理の効率が悪くなる。

Quadratic-Cost Algorithm

名前の通り計算量はO(M^2) だが、以下に示すアルゴリズムの1の計算量がO(M^2)なだけであり残りの処理は少ない計算量で実行することができるため、Exhastive Algorithm よりも少ない試行回数で実行することができる。

  1. そのノード中の要素から最もarea(MBR)-area(要素1)-area(要素2)が大きくなるような要素のペアを選択し、それぞれの要素をそれぞれのグループに分ける(O(M^2))
  2. もし全ての要素が分配されていて、それぞれのグループの要素数がm(各ノードの最低要素数)以上ならば分割を完了する (O(1))
  3. まだグループに分配されてない要素それぞれについて、各グループに所属した場合のMBRの大きさを計算 (O(M))
  4. グループ1に分配された場合のarea(MBR)-area(要素)-area(グループ1)の大きさと、グループ2に分配された場合の area(MBR)-area(要素)-area(グループ2) の大きさの差が一番大きいものを選択
  5. 要素を所属させたときMBRのサイズが小さくなる方のグループに所属させる
  6. 分配後2に戻る

下図のようなノード(赤い四角が要素)を分割する例を示す。(外枠はノードに対応するMBRを表し)

f:id:tanishiking24:20160403015102p:plain:w400

以下のようにarea(MBR)-area(要素1)-area(要素2)(青い部分)が最大となるペアを選択 f:id:tanishiking24:20160403015250p:plain:w400

黄枠をグループ1、青枠をグループ2、赤枠を未分類の要素とする。
d=area(MBR)-area(要素)-area(グループ)の差が一番大きいものを選択し(真ん中にある赤枠の要素)次の分配対象とする。

そして中心の要素の分配では、今回の場合dの値がより小さい青のグループに分配する。 f:id:tanishiking24:20160403015845p:plain:w400

Linear-Cost Algorithm

Linear-Cost Algorithm 基本的には Quadratic-Cost Algotithm と同じなのですが、グループに分配する要素の選択に用いられるアルゴリズムが異なる。 Quadratic-Cost Algorithm の一番最初の要素のペアを選択するアルゴリズムが以下のよう(Quadの方では計算量O(M^2)なのに対してLinearではO(M))

  1. ノードに対応するMBR内の各要素のうち、各軸(2次元ならx軸y軸)について最も離れた要素のペアを選択
  2. 各軸のペアについて、正規化された距離を計算 (各要素の距離 / MBRの対応する軸の長さ)
  3. 計算した正規化した距離のうち、より大きい距離のペアの要素をそれぞれのグループに分配

以下の場合、縦軸で最も離れたペアはE1とE2、横軸で最も離れたペアはE1とE3
それぞれの正規化された距離はd1/D1とd2/D2となります。今回の場合d1/D1の方が大きいため、E1とE3がそれぞれのグループの一つ目の要素として分配されることになります。 f:id:tanishiking24:20160403020750p:plain

また残りの要素をグループに分配していく処理は、それぞれランダムに分配していきます(O(1)) 最初のペアの選択である程度分割後のノードに対応するMBRを小さくし、残りの要素の分配は正確性を犠牲にパフォーマンスをとったという感じです。

削除

  • 葉ノードからエントリを削除する
  • 葉ノードのエントリ数が少なすぎないよう木の再構築
  • 再構築後に根ノードの要素が一つしかない場合はその子ノードを根ノードとする

木の再構築のアルゴリズム

削除対象となった葉ノードについて以下のようなアルゴリズムを用いて木の再構築を行う
葉ノードから要素が少なくなったノードを削除という処理を親ノードにどんどん適応していき、最後に削除した要素をすべて再挿入するというアルゴリズムです。

  • 1.エントリ数が少なくなりすぎた節点(及びエントリ)を削除
  • 2.MBRの形を縮小
  • 3.親ノードもについても1を適用
  • 4.最後に削除した全てのノードを再び挿入 (この際各要素・ノードの親子関係は保つようにしなければならない)

B-tree の場合、要素数が少なくなりすぎてノードは兄弟ノードのうち空きのあるノードと要素数を調整・マージという処理が行われるのに対して、R-tree では一度データを木から削除してそれを再挿入するというヘビーな処理が行われている。このような処理を行う理由は以下の二つがあるらしい。

  • 挿入処理を再度利用することができて簡単
  • 再挿入処理で空間的な構造を再構築することによって、各要素が(効率が悪いのに)同一のノードにぶら下がり続けることによる検索効率の悪化を防ぐことができる

更新処理

更新の際もレコードをインデックスから削除して、再挿入が行われます。

まとめ

空間インデックスの方法として他にも空間充填曲線を用いたインデックス方法や、R-tree の改良として R+-tree や R*-tree などがあるらしい。