An implementation and performance analysis of spatial data access methods

Four spatial data access methods, R-trees, K-D-B-trees, R+trees, and 2-D-Isam, have been implemented within a preliminary version of the POSTGRES DBMS (database management system). These access methods have been tested over a range of shapes and sizes of two-dimensional objects and for a range of logical page sizes. The CPU time, number of disk reads and writes, and the resulting tree sizes have been tabulated for insert and retrieve operations. It is concluded that R-trees provide the best tradeoff between performance and implementation complexity and that choice of implementation is crucial to the performance of all the methods investigated.>