CUBPT: Lock-free bulk insertions to B+ tree on GPU architecture
School of computer & information, Anqing Normal University, Anqing 246401, China
Computer Modelling & New Technologies, 18(10), 224-231, 2014
@article{huang2014cubpt,
title={CUBPT: Lock-free bulk insertions to B+ tree on GPU architecture},
author={Huang, Yulong and Su, Benyue and Xi, Jianqing},
year={2014}
}
B+-tree is one of the most widely-used index structures. To improve insertion process, several batch algorithms are proposed, which all use one thread to complete one node insertion and cannot make full use of GPU’s parallel throughput. So, a batch building and insertion method on GPU named CUBPT is proposed in this paper. During the process of bulk building and insertion, CUBPT use one thread to insert one key, which can maximize the performance by GPU. The experimental results show that when build a 10M tree, the overall performance of CUBPT improved 25.03 times compare with four threads PBI. When insert 10M uniform keys into a 10M tree, the overall performance of CUBPT improved 13.38 times compare with four threads PALM; when insert 10M highly skewed keys into tree with same size, the overall performance of CUBPT improved 15.23 times compare with four threads PALM.
December 5, 2014 by hgpu
