空間インデックスの履歴

空間情報を扱うときに、この空間インデックスを使うと便利

なぜゆえに空間インデックス

まず、インデックスとは何か確認してみよう!

MySQLの場合、インデックスは多くの場合B-Treeというものが使われている。(資料: MySQLにおけるインデックスの使用)

いきなりB-Treeと言われても意味がわからないかもしれないが、要は外見上は50音順に並んでいる、ということ。なので、たとえば、データを取得するときや、ソートをするときに使われている。

複合インデックス

たとえば、カラムAだけをキーに取得するような場合には、インデックスは一つのカラムに設定する。

が、複数のキーに設定する場合には、カラムAカラムBに対して複合インデックスを張るということをする。

ここでもし複合インデックスを張り忘れたりすると、データベースは「同じカラムAを持つレコードから順番に全部のレコードを調べる」ということをしてしまう。

正しく複合インデックスを張っている場合には、「同じカラムAを持つレコードを調べ、そのうちのカラムBで○○のレコードを持つレコード」のデータのみを調べることができるようになるのだ。

で、何で空間インデックス

ここで、緯度経度などの座標の場合には問題が出てくる。

緯度経度の座標は多くの場合、近くの点であったとしても違う座標になっているんだ。

お店の位置
______________________________________
      x
                             x
                           x
              x
             x
                                   x
______________________________________
↑ 近くにあるようなお店でも実は緯度も経度も違う。


インデックスを調べる際にB-Treeでは「Aの値がxxのときでかつBの値がyyの場合」には効率よく調べることができるのだけれども、Aの値もBの値もそれぞれ細かく異なる場合には効率よく調べることができないんだ。

なので、ここで空間インデックスを使う。使うとよいらしい。

というか、MySQLのマニュアルにも書いてあった。

For MyISAM tables, SPATIAL INDEX creates an R-tree index. For other storage engines that support spatial indexing, SPATIAL INDEX creates a B-tree index. A B-tree index on spatial values will be useful for exact-value lookups, but not for range scans.
(私訳)
MyISAMテーブルでは空間インデックス(SPATIAL INDEX)はR-Treeを作成します。他の空間インデックスをサポートしているテーブルではB-Treeインデックスを作成します。空間の値を扱うB-Treeインデックスは特定の値の検索には便利ですが、範囲スキャン(range scans)の検索には便利ではありません。

http://dev.mysql.com/doc/refman/5.1/ja/creating-spatial-indexes.html

MySQL上での実装

データ型

空間情報は内部的にBLOBとして記憶されているっぽい。

http://dev.mysql.com/doc/refman/4.1/ja/gis-wkb-format.html

実際、MyISAMの固定長テーブルにPOINT型のカラムを追加したら可変長テーブルになった。

できないこと

2009年7月の時点では、特定の点から半径xxxxメートルの点を検索する、といった芸当はできないらしい。(緯度・経度は互いに1度あたりの距離が異なる!)