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

Ｂ＾＋－树是一种有效的数据库存储结构，被普遍应用于各种关系数据库系统。把Ｂ＾＋－树并行化，使之用于并行数据库系统显然是一项很有意义的重要工作。本文研究了适用于并行数据库的并行Ｂ＾＋－树存储结构，提出两类基于并行Ｂ＾＋－树工并行Ｊｏｉｎ算法。理论和实验结果表明，这些算法效率高基其它并行Ｊｏｉｎ算法。

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

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.