Research On Spatial Index Technology Based On Non-volatile Memory

The Internet has spurred the rapid development of e-commerce,autonomous driving,online social networking,and the Internet of Things,and a large amount of spatial data has been generated.People’s daily lives are increasingly dependent on spatial data.The era of big data for spatial data has arrived.Spatial data has the characteristics of large quantity,fast generation speed,complex structure and special operation.Traditional relational databases cannot cope with the storage and operation of spatial multidimensional data.In addition,the traditional storage device is block storage.Each update is operated according to the block size,which affects the retrieval and insertion performance in the case of a large number of spatial indexes and small data.In response to the above problems,this paper adopts technologies based on R-tree,RLinktree,Non-Volatile Memory(NVM)and Non-Volatile Memory Development Kit(PMDK)and other technologies.Design the OPR-tree(Optimized Persistent R tree)and PRLink-tree(Persistent RLink tree)spatial data indexing structure.The system achieve the main functions of inserting and retrieving spatial data,and satisfies the characteristics of nonvolatile memory such as byte read,8-byte atomic update,and large capacity.OPR-tree and PRLink-tree has the advantage of higher insert,retrieve throughput.The main work of this paper is as follows:(1)Analyze the remaining entries defects of the existing R-tree quadratic splitting algorithm,Aiming at this problem,an improvement for the splitting process is proposed,which modifies the original splitting process.After comparing the distance of the seed node,it is assigned to the one with the closest distance.Tests have shown that this refinement of the splitting process can improve space utilization and reduce coverage.(2)The bitmap is used to speed up the search of the internal branch of the node,and an 8-byte header is designed to save the node metadata OPR-tree header include(level,version number,bitmap),PRlink-tree header include(level,logical sequence number,bitmap),designed to take full advantage of the non-volatile minimum atomic update size of 8 bytes.(3)The In-place update method is used to insert new index records and update old index records.Compared with the original R tree,the overflow node is split into two new nodes,and then the two new nodes are inserted into the parent node.The original R tree splitting method requires the parent node to have two empty branches.if it is not satisfied,the parent node needs to be split again,which increases the number of splits and affects the operation efficiency.The update method of Inplace-update only needs one empty branch,which utilizes the original overflow node branch to improve the operation efficiency.(4)OPR-tree uses mutex locks to implement multi-thread operations,and PRLink-tree uses read-write locks to implement multi-thread operations.And the problem of read and write consistency under multi-thread operation is analyzed.(5)The log structure is used to avoid data inconsistency in non-volatile memory caused by system crash or power failure.For OPR-tree,PRLink-tree index structure,a non-volatile memory experimental environment based on Intel Optane persistent memory was built,and its multi-thread insertion,retrieval throughput,insertion and retrieval throughput under different header sizes were tested,The experimental results show that OPR-tree is superior to FBR-tree in terms of insertion and retrieval performance,the insertion performance of OPR-tree is improved by up to 34%,and the retrieval performance is improved by up to 6%.Compared with OPRtree and FBR-tree,the average number of flushes of PRLink-tree to non-volatile memory is greatly reduced under the same amount of data,and the insertion performance is also better than OPR-tree and FBR-tree.