文档介绍：分类号学号 M200972434 学校代码 10487 密级硕士学位论文达梦数据库哈希连接算法的研究学位申请人:汪龙重学科专业:计算机软件与理论指导教师:王元珍教授答辩日期: A Thesis Submitted in Partial Fulfillment of the Requirements for the Degree of Master of Engineering Research on Hash Join Algorithmin DM Database Candidate :Wang Longzhong Major :Computer Software and Theory Supervisor :Prof. Wang Yuanzhen Huazhong University of Science and Technology Wuhan 430074, January, 2012 独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除文中已经标明引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到,本声明的法律结果由本人承担。学位论文作者签名: 日期: 年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定,即:学校有权保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密□,在_____年解密后适用本授权书。本论文属于不保密□。(请在以上方框内打“√”) 学位论文作者签名: 指导教师签名: 日期: 年月日日期: 年月日 I 华中科技大学硕士学位论文摘要连接操作是基本的关系数据库查询操作之一,是从两个不同的关系中检索满足条件的信息。实现连接的方法较多,其中哈希连接在所有的连接算法中被证实是性能最好的,但现有的哈希连接都存在分区溢出问题。如果连接过程中发生分区溢出现象,会严重降低算法效率。研究并改进现有的哈希连接算法对提高哈希连接效率具有重要意义。为了解决现有哈希算法分区溢出的缺点,使用归并连接思想对现有的哈希连接算法进行了改进,设计了一种哈希归并连接(Hash Merge Join, HMJ)算法。该算法分成两个阶段:哈希阶段和归并阶段。哈希阶段利用哈希表的哈希值作为数据对比键值,对哈希表中所有数据进行排序,把整个哈希表中的数据当作一个分区,然后依次对所有数据进行类似处理,使得数据基于哈希值和原始键值有序;归并阶段则对排好序的数据进行归并连接,完成整个连接操作。测试结果证明,该算法不会产生分区溢出。根据达梦数据库管理系统中的操作符特点,以哈希归并连接算法为基础,设计并实现了哈希内连接、外连接和半连接操作符,实现过程中临时数据的存储采用列存储技术,归并操作采用败者树算法对数据进行排序。通过对使用新算法实现的哈希连接进行测试,结果证明,不论是内连接、外连接还是半连接,哈希归并连接算法较以前算法在性能上均有较大提高。关键词:连接,哈希连接,归并,分区溢出 II 华中科技大学硕士学位论文 Abstract The join operation is one of the fundamental relational database query operations. It facilitates the retrieval of information from two different relations. Many techniques and method are used to implement joins, Hash join is found to perform better than other algorithms, but partition overflow is said to occur when using traditional hash join algorithm. If partition overflow occur during joining, it would seriously reduce the efficiency. It is importantto study and improve the hash join algorithm to improvequery efficiency. To Solve