The I/O performance for spatial is extremely important since the handing of multidimensional and hudge amount of data is requried in spatial databases for geographic information systems. In this thesis, we propose a new access method called Parallel $R^*$-tree, which applies multiple disks for popular $R^*$-tree, and a Spatial Proximitry(SP) disk allocation method which uses the spatial locality. We have implemented search, insertion, splitting and disk allocation algorithms used for the Parallel $R^*$-tree. The new access method has been compared with the two representative spatial access methods, Parallel R-tree and $R^*$-tree, through the performance results from a simulation. The Spatial Proximity method has been proposed from an analytic study for the spatial locality.
According to the simulation results, with respect to storage overhead, storage utilization, and the number of node splits for the insert operation, the performance of Parallel $R^*$-tree is better than Parallel R-tree. The CPU time and insert I/O performance of Parallel $R^*$-tree is poorer than those of Parallel R-tree. Regarding the response time, the number of disk I/Os, and the number of false drops for a range query, the performance of Parallel $R^*$-tree is better than Parallel R-tree. In addition, the performance of Spatial Proximity method is the best in all disk allocation method such as Round Robin, Minimum Intersection, Minimum Area. The speed up of our method is close linear speed up, which increases with the size of queries or the number of disks.
