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

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.