É sabido que operações de busca em banco de dados não espaciais podem ser otimizadas utilizando índices. Isto ainda é verdade em banco de dados espaciais. Com a ajuda de grande variedades de métodos de indexacão multi-dimensionais, o quais já têm sido desenvolvidos, é possível otimizar buscas espaciais. As mais comuns delas são:

O MySQL utiliza Arvores R com separação quadrática para indexar colunas espaciais. Um índice espacial é construído usando o MBR de uma geometria. Para a maioria da geometrias, o MBR é um retângulo mínimo que cerca a geometria. Para uma linha (linestring) horizontal ou uma vertical, o MBR é um retângulo degenerado, nas linhas e nos pontos respectivamente.