Research On Linked Spatial Index Based On LSM-Tree

With the development of geographic information data collection equipment,the update frequency of spatial data is gradually increasing.The management of spatial data must not only meet the needs of efficient queries,but also take into account the needs of efficient updates.When the spatial data is updated frequently,the existing spatial index usually results in a large number of random reads and writes to the disk,which seriously affects the efficiency of the spatial index operation and makes it difficult to meet the current spatial data update requirements.This thesis focuses on the frequently inserted and updated spatial data,to analyze the defects of the current spatial index.Starting from the spatial index structure and the implementation of primary key indexes and secondary indexes,to delve into the current needs for efficient updating and querying of spatial data.To resolve the problem of low update efficiency of current spatial indexes,a spatial index implementation scheme is designed to meet the needs of efficient updates and to provide the underlying support for geospatial data.The specific research contents are as follows:(1)The Hilbert R-Tree structure is improved to store the range of Hilbert values in non-leaf nodes.A batch merge algorithm with "top-down" query and "bottom-up" adjustment is proposed to resolve the problems of large memory demand for static Hilbert R-Tree merging and low efficiency of dynamic Hilbert R-Tree merging which achieves the effects of high R-Tree merge efficiency,less memory consumption during merge,higher space utilization rate and higher query efficiency after merge to provide a basic index structure for the following new spatial index research.(2)By fusing LSM-Tree and improved Hilbert R-Tree,Hilbert R-Tree with LSMTree(LSM Hilbert R-Tree,LH R-Tree)is implemented to improve Hilbert R-Tree by combining memory and disk hierarchical management.We also design a set of efficient index operation algorithm for LH R-Tree to resolve the problem of low efficiency of frequent updating of spatial index under the guarantee of certain spatial query efficiency and realize efficient updating of spatial index.(3)Spatial index linkage between LSM B-Tree and LH R-Tree is realized.Based on the LSM B-Tree primary key index and the LH R-Tree secondary spatial index,combined with the memory hash index,the association between the primary and secondary indexes is established to overcome the low operation efficiency problem that the spatial index combined with LSM B-Tree and LSM R-Tree will read and write a large number of index trees in the disk during the operation of the primary key indexes and secondary indexes and to effectively improve the update and retrieval operations of the entire index effectiveness.Research and experimental results show that the improved Hilbert R-Tree merging algorithm proposed in this thesis can resolve the problems of large memory required by static Hilbert R-Tree and low dynamic Hilbert R-Tree merging efficiency and query efficiency,and achieve efficient merging of R-Tree by balancing the three aspects of merging efficiency,memory size and query efficiency.LH R-Tree is constructed and applied to realize the secondary index linked with the LSM B-Tree which can effectively improve the efficiency of the primary key indexes and secondary indexes based on the LSM-Tree structure and provide a set of effective solutions for the management of frequently inserted and updated spatial data.