基于并行B^+-树的并行Join算法的设计、分析与实现  

DESIGN, ANALYSIS AND IMPLEMENTATION OF PARALLEL JOIN ALGORITHMS BASED ON PARALLEL B^+-TREES

作　　者：孙文隽[1] 李建中[1] 常红[1] 

机构地区：[1]黑龙江大学信息技术研究所,哈尔滨150080

出　　处：《计算机学报》1998年第1期10-17,共8页Chinese Journal of Computers

基　　金：国家杰出青年基金;国家863高科技基金;国家自然科学基金;黑龙江省杰出青年基金

摘　　要：B＋-树是一种有效的数据库存储结构，被普遍应用于各种关系数据库系统．把B＋-树并行化，使之用于并行数据库系统显然是一项很有意义的重要工作．本文研究了适用于并行数据库的并行B＋-树存储结构，提出两类基于并行B＋-树的并行Join算法．理论和实验结果表明，这些算法效率高于其它并行Join算法．B+-tree is a very efficient database storage structure. It has been used inalmost all of the relational database systerns. It is significant and worthy to paral-lelize the B+-tree structure so that it can be used in parallel database systems. Aparallel B+-tree structure is presented and two classes of parallel join algorithrnsusing the parallel B+- tree structures are proposed and analyzed in this paper. First,the parallel B+-tree structure of a file is described, which consists of a set of im-proved B+-trees (IB-tree for short ), distributed among the processing nodes in aparallel computing system. Each IB-tree is built on a partition of the file partitionedby one of the three methods, namely range partition, hash partition and round-robin partition. Then, two classes of parallel join algorithms using the parallel B+-tree are presented and analyzed. ()ne is based on the range partition method. Theother is based on the hash partition method. It is shown that the parallel executiontimes of the algorithms are generally linearly proportional to the size of theoperands and the number of processing nodes- Finally, the two classes of paralleljoin algorithms using parallel B+-tree structures are compared to the well knownparallel join algorithms, such as hybrid hash Join, Grace hash join, merge-sorthash join and the hash join algorithm of Oracle DBMS. In practice, theoretical andexperimental results show that the algorithms using parallel B+-tree structures aremore efficient than the other algorithms.

关 键 词：并行数据库 并行B^+-树 并行JOIN算法 数据库 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]