There are two common techniques for spatial database queries:
1) R.Tree: One of the best known techniques is the use of R-trees and their variations. R-trees group objects that are in close spatial physical proximity on the same leaf nodes of a tree-structured index. Since a leaf node can point to a certain number of objects only, algorithms for dividing the space into rectangular sub-spaces that include the objects are needed. Typical criteria for dividing the space include minimising the rectangle areas, since this would lead to a quicker narrowing of the search space. Problems such as having objects with overlapping spatial areas are handled differently by the many different variations of R-trees.
The internal nodes of R-trees are associated with rectangles whose area covers all the rectangles in its sub-tree. Hence, R-trees can easily answer queries, such as find all objects in a given area by limiting the tree search to those sub-trees whose rectangles intersect with the area given in the query.
2) Quadtree: Other spatial storage structures includequadtrees and their Quadtrees generally divide each space or sub-space into equally sized areas, and proceed with the sub-divisions of each sub-newer space to identify the positions of various objects. Recently, many spatial access structures have been proposed, and thisarea is still an active research area.
