すでに知られていることですが、非空間データベースでの検索操作はインデックスを使用して最適化できます。このことは、空間データベースについても当てはまります。 さまざまな多次元インデックス作成方法が考案されており、それらを活用すれば空間検索を最適化することができます。代表的な例を以下に示します。

MySQL では、二次分割アルゴリズムを利用した R-Tree を使用して空間カラムにインデックスを付けます。空間インデックスは、ジオメトリの MBR を使用して作成されます。 多くのジオメトリに対しては、MBR はジオメトリを囲む最小矩形です。水平または垂直な LineString に対しては、MBR は LineString に縮退した矩形です。 Point に対しては、MBR は Point に縮退した矩形です。