关键词: 并行算法, 图形处理器, CSB⁺- 树索引, 动态数组, 查询效率

Abstract:

In order to improve the operation efficiency of cache sensitive B⁺- tree (CSB⁺- tree) indexing,this pa-per deals with the parallel construction and query performance of CSB⁺- tree on graphic processing unit (GPU).Inthe investigation,first,the mapping relationship between each key in internal nodes and the corresponding leafnode of the index tree is analyzed, a lock- free parallel algorithm that once for all builds the CSB⁺- tree internal nodekeys is proposed,and the index tree is constructed at the maximum parallel speed.Moreover, dynamic arrays su-pporting the arbitrary expansion of CSB⁺- tree index data on GPU are designed to implement the dynamic allocationof memory space on GPU,and padding bits are added to the boundary of the internal nodes to reduce the number ofbranches,thus improving the query efficiency of CSB⁺- tree.Experimental results indicate that the proposed algo-rithm is 31. 0 and 1.4 times faster respectively than the parallel algorithms based on single node and tree layer.

Key words: parallel algorithms, graphic processing unit, CSB⁺- tree indexing, dynamic array, query efficiency