Spatial index

From Wiki.GIS.com

Spatial indexes are used by spatial databases (databases which store information related to objects in space) to optimize spatial queries. Indexes used by non-spatial databases cannot effectively handle features such as how far two points differ and whether points fall within a spatial area of interest. Common spatial index methods include:

• Grid (spatial index)
• Z-order (curve)
• Quadtree
• Octree
• UB-tree
• R-tree: Typically the preferred method for indexing spatial data. Objects (shapes, lines and points) are grouped using the minimum bounding rectangle (MBR). Objects are added to an MBR within the index that will lead to the smallest increase in its size.
• kd-tree