NES-Join算法的改进算法  

AN IMPROVED ALGORITHM OF NES-JOIN ALGORITHM

作　　者：柯莉珍[1] 苏厚勤[1] 

机构地区：[1]东华大学计算机科学与技术学院,上海201620

出　　处：《计算机应用与软件》2007年第9期175-178,共4页Computer Applications and Software

摘　　要：NES-Join算法是一种无需外排序的连接运算算法,其复杂性优于经典的Sort-Merge Join算法及改进后的SDC-Join算法。在NES-Join算法基础上提出一种改进算法,该算法能够有效压缩原算法中未匹配记录暂存块中的空记录信息,从而使NES-Join算法更具实用性。通过实验和分析表明,改进后的NES-Join算法与原算法时间复杂性相当,但显著提高了磁盘空间的使用率。NES-Join algorithm is a kind of join algorithm that does not need external sort. Its complexity is better than the classical Merge-Join algorithm and the SDC-Join algorithm improved from the Merge-join algorithm. An improved algorithm has been presented in this paper based on NES-Join algorithm. The empty records stored temporarily in the disk blocks in which unmatched records will be stored of the NES- Join algorithm can be compressed effectively, so that the NES-Join algorithm is more practicability. The theoretical analysis and experiment results show that the time complexity is same as the original algorithm and the using rate of disk space has been enhanced effectively of the improved NES-Join algorithm.

关 键 词：Join运算 JOIN算法 NES-Join算法 

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