Applications, such as VLSI CAD, cartography, and geographical information systems, require efficient access methods for spatial data. Many works have been made to enhance the index methods for spatial data. They include the KDB-tree, R-tree, and $R^+$-tree. Among them the R-tree has been shown to be the most efficient spatial data access method with respect to disk I/O and storage overhead. Z transformation which takes quite different approach from the R-tree have been proposed to apply for spatial data access methods recently, but performance comparison with the R tree has not been made.
In this thesis, we evaluate the performance of the R-tree and the Zkd B-tree which is an adapted B-tree to store Z transformed values. The performance parameters are the number of disk I/Os and storage overhead. We show that the storage overhead of the Zkd B-tree is less than that of the R-tree. We also show that the Zkd B-tree achieves higher performance than the R-tree for I/O intensive complex operations such as spatial join and overlay, while both methods have similar performance for the basic tree operations such as insertion, deletion and region search.
