ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2018, Vol. 55 ›› Issue (9): 2066-2082.doi: 10.7544/issn1000-1239.2018.20180254

Special Issue: 2018新型存储系统结构前沿技术专题

Previous Articles     Next Articles

R-Tree Optimization Method Using Internal Parallelism of Flash Memory-Based Solid-State Drives

Chen Yubiao1, Li Jianzhong1, Li Yingshu1,2, Li Faming1, Gao Hong1   

  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, Georgia 30303)
  • Online:2018-09-01

Abstract: Recently, flash memory-based solid state disk has more magnificent improvement on internal design than before, which brings rich internal parallelism to solid state disk. R-tree index is widely applied in spatial data management, but up to now, the proposed R-tree optimization methods on solid state disk do not take the internal parallelism into consideration, and also the approach designed for traditional magnetic disk is not suitable for solid state disk. So all of the previous R-tree optimization doesn’t use internal parallelism mechanism of solid state disk to make the query and update operation more efficient. In order to exploit internal parallelism to speed up R-tree. Firstly, a parallel batch asynchronous I/O submitting library is realized. Secondly, optimizing algorithms to accelerate the R-tree search and update operations are achieved by aggregating read or write operations to batch submit through the previous library, Thirdly, we analyze the minimal speed up expectation theoretically, and prove that normal solid state can achieve speed up of at least 1.86 times expectation speed-up with 4 channels and 2.93 times expectation speed-up with 8 channels. Through the experiments on two kind of solid state disk, our optimization R-tree can achieve stable 3 times speed up for query operation compared with original R-tree, and also speed up of about 2 times for update operation. No matter for query intensive or update intensive application scenarios, there is speedup between them.

Key words: solid state disk, internal parallelism, batch submit, R-tree, speed up

CLC Number: