Research And Implementation On R-Tree Cost Mode And Query Optimization

R-Tree is one of the most widely-used spatial indexes for research and commercial, it is one of the key fields in the research of GIS. There are plenty improvements for R-Tree since it was presented by Guttman in 1984. Research focused on the tree structure improvements for enhancing query effect and cost mode presentation for evaluating and predicting its behavior. It's very difficult to get more effective optimization by improving R-Tree itself. It's almost impossible to find effective methods to comply all circumstances as mass data sets grow and GIS runtime environments become more complicated. So the goal has to be focused on more effective and widely-used algorithm and improving structure of R-Tree by analyzing and pre-processing original data sets. This paper presents three different optimization methods which are page size setting and improvements for buffer algorithm and organization and creating R-Tree with data sampling and iteration based on a real spatial indexes system of R-Tree and real data sets and known cost modes. Theory research and application both are presented.The main jobs of the thesis are as followed:Firstly, research on the main algorithms and cost modes and query optimizations of R-Tree is presented.Secondly, three different improvements on R-Tree are presented: The page size should not be fixed but be determined by properties of data sets so the methods and conclusion on page size are presented by experiences. The improvement for buffer management and organization is presented. The R-Tree creating process by data sampling and iteration is presented for improving the structure of R-Tree.At last the implementation of spatial indexes system based on R-Tree which applies latest optimization results is presented and its implementation detail is highly optimized.