ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2020, Vol. 57 ›› Issue (11): 2404-2418.doi: 10.7544/issn1000-1239.2020.20190564

Previous Articles     Next Articles

SBS: An Efficient R-Tree Query Algorithm Exploiting the Internal Parallelism of SSDs

Chen Yubiao1, Li Jianzhong1, Li Yingshu1,2   

  1. 1(College of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001);2(College of Computer Science and Technology, Georgia State University, Atlanta, GA, USA 30303)
  • Online:2020-11-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (U1811461, 61832003, 61732003) and the National Science Foundation of USA (1741277, 1829674).

Abstract: The flash-based SSD has become the mainstream storage device for its excellent features. At the same time, with the magnificent improvement of internal design of SSD architecture, more and more storage chips and hardware resources are integrated into SSDs which makes them full of internal parallelism, while traditional external memory algorithm and data structure optimization rarely take the internal parallelism of SSDs into consideration. Range query is one of the most important basic operations of R-tree. R-tree is the engine index data structure of many geographic information systems. Therefore, the efficiency of range query plays an important role in the performance of the entire geographic information system. Almost all the tree index structures are difficult to effectively utilize the feature of internal parallelism due to the data loading dependency problem. Therefore, a new range query algorithm SBS(stack batch search) based on stack is proposed, which can effectively utilize the internal parallelism of the SSD with memory usage of O(B log N). Finally, we verify the performance of the SBS algorithm through real data experiments. Experimental results show that SBS has the best performance in range query under acceptable memory consumption. On two different solid-state drives, the speed up ratio of SBS can reach 3.4 and 4.5 separately.

Key words: R-tree, range query, internal parallelism, solid state drives, speed up

CLC Number: