关键词: 图形处理器, T- 树, 内存数据库, 索引结构, 并行构建, 批量节点插入

Abstract:

In order to improve the operation performance of T-tree,a main memory database indexing,a lock-freeparallel computing scheme for T-tree on the graphics processing unit ( GPU) is proposed.By analyzing the parentchildrelationship of balanced tree structure,a T-tree with m nodes is constructed with n separate threads in a parallelmode on GPG platform.Thus,a T-tree with the maximum parallelism degree is successfully constructed.Then,in orderto verify the correctness of the proposed scheme,a T-tree traversal algorithm with stacking on GPU platform isproposed.Moreover,different schemes of constructing T-tree on different platforms are analyzed and the data transmissionbetween CPU and GPU is optimized by means of memory pinning.The result of experiments on different platformsshow that,as compared with the conventional CPU-based schemes,the proposed scheme obtains about 12 timesbatch creating and 8 times batch inserting of T-tree.

Key words: graphic processing unit, T-tree, main memory database, index structure, parallel creation, batch nodeinsertion