(cache) 空間インデックス(R-tree)の理論と実践-理論編

空間データを効率良く検索するためには、インデックス構造が必要です.
しかしながら B-tree INDEXのような一次元的なデータ構造は、空間データといった多次元空間に属するデータを扱うには不向きです. (Geohashという緯度経度の情報を文字列のような B-tree に適したデータにハッシングする方法もありますが)

理論編では R-tree INDEX という多次元データを効率良く扱うためのデータ構造についてと、実践編ではPostgreSQL(PostGIS) や MySQL を用いた空間インデックスの使い方について紹介していこうと思います。
R-treeインデックスは多次元のデータを格納することができますが、以下では簡単のため2次元のデータを例にとって解説していきます。

この記事を読むにあたって B-tree についてある程度の知識があると分かり易いかもしれません。

空間データ

空間データとしては

一点を指すPOINT
二つの地点を結ぶ線分であるLINESTRING
ある空間を囲う領域を示すPOLYGON

などがあります。PostGISだと以下のようなSQLでデータを挿入することになります。

CREATE TABLE geometries (name varchar, geom geometry);

INSERT INTO geometries VALUES
  /* (0, 0) の点 */
  ('Point', 'POINT(0 0)'),
  /* (0, 0) と (1, 1) を結ぶ線分 */
  ('Linestring', 'LINESTRING(0 0, 1 1)'),
  /* (0, 0) と (1, 0) と (1, 1) を頂点とする領域 */
  ('Polygon', 'POLYGON((0 0, 1 0, 1 1))');

R-tree インデックスを使うことで

ある点を包含するレコードを取得
指定した矩形の範囲内に含まれるレコードを取得

などといった検索を効率的に実行することができます。

R-tree INDEX

R-tree はそれぞれの節点の要素に

子節点へのポインタ
子節点が持つすべての要素の空間データを含む最小外接矩形(Minimum Bounding Rectangle 以下MBR)のデータ

のタプルを持ち、葉節点の場合は

レコードに収められている空間データオブジェクト
(上記のSQLで挙げた線分や領域など)のid
レコードに収められている空間データを囲うMBR

を持ちます。

例えば以下の図において赤線部分がデータオブジェクトとすると、それを囲うMBRは破線部分となります。

f:id:tanishiking24:20160403163947p:plain

それでは R-tree インデックスの例を見ていきましょう。
上の図が実際のデータ構造、下の長方形がたくさんある図は各節点が持つ最小外接矩形(MBR)を描いたイメージ図です。

f:id:tanishiking24:20160401003304p:plain

f:id:tanishiking24:20160401003548p:plain

B(+)-TREE と同じようにひとつのノードに直接ぶら下がる部分木の高さの差が1であり
葉ノードにはデータオブジェクトへのポインタが格納されています
(これはB+Treeと同じですね)

各節点の要素数

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

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

mの値を変えることによって、各節点のデータサイズの大小、木の高さが変わってくるものでありパフォーマンスにも関わってきます。

参照処理

点検索

f:id:tanishiking24:20160401020453p:plain

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

根節点から出発

もしその節点が葉節点でない場合、節点内の各要素に関して検索地点を包含する要素すべて探索し、ヒットしたそれぞれの要素の指す子節点について再帰的に2を実行

その節点が葉節点な場合、その節点の各要素が持つに関して検索地点を包含する要素すべて探索しヒットしたそれぞれが持つデータオブジェクトidを取得

上の図の例の場合だと

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

という感じで探索が進みます。

範囲検索

f:id:tanishiking24:20160401022102p:plain

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

根節点からスタート

その節点が葉節点でない場合、節点内で検索範囲と重なる要素を探索ヒットしたそれぞれの要素の指す子節点について再帰的に2を実行

その節点が葉節点な場合、その節点の各要素が持つに関して検索地点を包含する要素すべて探索しヒットしたそれぞれが持つデータオブジェクトidを取得

上の図の例の場合だと

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

データの挿入・削除

R-tree では B-tree と同様に挿入・削除・更新処理の際に木の再構築が行われ平衡な木の状態が保たれます。これにより木が偏ることによって参照処理の最悪計算量が増大してしまうことを防ぐことができます。

挿入処理

この記事では少し噛み砕いた形でアルゴリズムを紹介します。厳密なアルゴリズムを知りたい場合はこちらの論文の3.2を参照してください:bow:

新しく木に追加する要素をEとします。 f:id:tanishiking24:20160403005304p:plain:w450

Eが所属するべき葉節点を探索します。

Eが節点の要素として追加された場合に対応するMBRが最小になるような節点をたどっていき、葉節点まで探索をすすめる
(上の図だとR5が対象となる葉節点になります)

もし葉節点に空きがあれば(上で定めた各節点の最大要素数M未満なら)そこに挿入。実際にMBRを(必要ならば)拡大していくのを根節点まで順次拡大

もし空きがなければ、節点を分割し新たに作られた節点を親節点にぶら下げる(この分割方法については後で記述します)

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

(このときR15,R16,R6の節点が溢れた場合同様の分割がどんどん行われていくことになります)

節点の分割

上で述べたように、満杯になった節点に要素を追加するためには節点を2つのグループに分割が必要です。インデックス構造を平衡に保ち・空間的な効率も良くデータを格納するためにはできるだけ各節点のMBRが小さくなるように工夫して節点の分割を行う必要があります。

分割の方法として以下のようなアルゴリズムがあります。

Exhaustive Algorithm

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

Quadratic-Cost Algorithm

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

その節点中の要素から最もarea(MBR)-area(要素1)-area(要素2)が大きくなるような要素のペアを選択し、それぞれの要素をそれぞれのグループに分配(O(M^2))

もし全ての要素が分配完了し、それぞれのグループの要素数がm(各節点の最低要素数)以上ならば分割を完了する (O(1))

まだグループに分配されてない要素それぞれについて、各グループに分配された場合のMBRの大きさを計算 (O(M))
すべての要素から、グループ1に分配された場合のarea(MBR)-area(要素)-area(グループ1)の大きさと、グループ2に分配された場合のarea(MBR)-area(要素)-area(グループ2)の大きさの差が一番大きいものを選択

選択された要素を分配後のMBRのサイズが小さくなる方のグループに分配
分配後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))

節点に対応するMBR内の各要素のうち、各軸(2次元ならx軸y軸)について最も離れた要素のペアを選択

各軸のペアについて、正規化された距離を計算
(各要素の距離 / MBRの対応する軸の長さ)

計算した正規化した距離のうち、より大きい距離のペアの要素をそれぞれのグループに分配

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

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

削除

削除対象のレコードが所属する葉節点を探索

葉節点からそのレコードに対応する要素を削除する

その葉節点の要素数が少なすぎる(最低要素数m未満)ようにならないよう木の再構築を行う

再構築後に根節点の要素が一つしかない場合はその要素の子節点を根節点とする

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

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

その節点が根節点なら4へ、非根節点の場合はその節点の要素数がm未満なら、その節点及びその全ての要素を削除

もし節点が削除されなかった場合は、その節点のMBRが最小になるようMBRを縮小

親節点へと移り1から繰り返す

これまで削除したすべての要素を再びインデックスに挿入する
(この際各要素・節点の親子関係は保つようにしなければならない)

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

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

更新処理

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

まとめ

このように R-tree インデックスを用いることで空間データを効率的に扱うことができるようになります。
空間インデックスの方法として他にも空間充填曲線を用いたインデックス方法や、R-tree の改良として R+-tree や R*-tree などがありますが MySQL や PostGIS などで実際に使われているインデックス構造の元となる R-tree を紹介しました。(機会があればそちらも紹介していきたい)
SPATIAL INDEX の動作の理解の助けとなれば幸いです。
また今回参照した論文には、この記事の内容に加えてmの値を変動・節点の分割アルゴリズムの変更によるパフォーマンスの計測・CPUや空間効率性の計測データが掲載されています、詳細が気になる方は論文を読むと良さそうです。

実践編では MySQL・PostGIS を用いた空間データ処理について紹介したいと思います。(5月くらいまでには書きたい)

たにしきんぐダム

空間インデックス(R-tree)の理論と実践-理論編