Indexing techniques in spatial databases

Due to a great quantity of data in spatial databases, so in general the cost of query in spatial databases is higher than in relational databases. Especially, when there are some functions, in predicate of query, which deal with spatial data, the cost of computing these functions is higher than the cost of comparing strings and numerical values. If query strategy is to scan sequentially spatial data, then the efficiency will be very low. For improving query efficiency, it is necessary to adopt spatial indexing techniques. Indexing techniques in spatial databases have gradually caused the attentions of many people. Research advance of indexing techniques for spatial databases is summarized, and then four new and often used indexing methods, including R-tree, K-D-tree, Quad tree and Generalized search tree, are introduced. Finally, it is pointed out that the high dimensional index is a hot research field in spatial databases.