Las operaciones de búsqueda en bases de datos no espaciales pueden optimizarse mediante índices. Esto también es aplicable a las bases de datos espaciales. Con la ayuda de una gran variedad de métodos de indexación multidimensional que han sido previamente designados, es posible optimizar las búsquedas espaciales. Los más usuales de estos métodos son:

MySQL utiliza Árboles R con partición cuadrática para indexar las columnas espaciales. Un índice espacial se construye utilizando la MBR de una geometría. Para la mayoría de las geometrías, la MBR es el rectángulo mínimo que la circunscribe. Para una línea vertical u horizontal, la MBR es un rectángulo reducido a una línea. Para un punto, la MBR es un rectángulo reducido a un punto.