A data structure such as a B-tree or sorted array is used for fast
searches of large sets of records, keyed by a single field. These data
structures support both equality queries, (e.g. find part #419), and
range queries, (e.g. find parts manufactured between September 15 and
The choice of a data structure is dictated by the characteristics of the data set. Sorted arrays work well for static, memory-resident data sets. Balanced binary trees and skiplists work well for dynamic, memory-resident data sets. B-trees are best suited for large, dynamic disk-resident data sets.
Many applications need data structures which support spatial searches. For example, a geographic application might store a set of landmarks, and retrieve all landmarks inside a query region. A mechanical CAD application might need to detect interference among 3-dimensional objects. In both cases, the data items to be stored are spatial objects, and the selection criterion is not equality or membership in a range, but spatial containment or overlap.