融入MD5的HASH线性获取增量算法研究

郭 亮，杨金民

湖南大学 信息科学与工程学院，长沙 410082

融入MD5的HASH线性获取增量算法研究

郭 亮，杨金民

湖南大学 信息科学与工程学院，长沙 410082

1 引言

随着信息化技术进一步的发展和数据量的暴增，现有的增量提取技术无法大幅度地减少数据备份时间，满足人们的备份需求；对于大部分的用户来说，备份速度过慢将会影响正常的业务运营。在某些大规模数据密集型系统中（如：网络安全监控、金融数据分析、电信数据处理等领域），这些问题尤为突出[1-3]。

常用的数据库增量提取方法主要有两种：（1）基于NOT EXISTS 的 SQL 语句[4]；（2）基于 Sort-Merge Join（S-MJ）的方法[5-7]。第一种方法所采用的扫描策略需要进行至少M×N次比较，其时间复杂度为O(n2)，虽然在数据库中对相关字段建立索引能提高效率，但在数据量较大的情况下，其性能会急剧下降，效率低下。第二类方法中最具代表意义的是SQL语句MINUS[8]，求集合的差集，其具体的实现过程是对原始表和备份表所有记录的相关字段进行排序，线性比较两有序集合得出增量记录；第二种方法较第一种方法有很大的改进，尤其在数据量较大的情况下优势更加明显，但其效率受到排序算法性能和排序字段数的影响较大，有待进一步提升。本文提出了一种融入MD5的 HASH线性扫描获取增量的方法（MD5-Hash Join，M-HJ），采用了HASH查找时间复杂度为O(1)的特性，极大地降低了比对次数；同时通过MD5算法变换属性字段，限定比对字段的个数和长度。M-HJ从整体上来说降低了算法的时间复杂度，实现了线性扫描就能够获取增量数据的目的，提高了增量提取的效率。……