基于MD5与HASH的数据库增量提取算法及其应用

摘要

当今社会，信息基础设施越来越完善，信息间的交流愈发频繁，导致了信息的海量增长。数据信息的丢失和损坏将会引起难以估量的损失，数据备份是解决此问题唯一可行的方案。在某段时间里，海量数据中往往只有一部分数据发生了改变，如果采用完全备份则存在效率低下的问题，而增量备份既能缩短备份时间也能减小存储空间。现有的数据库增量提取技术中，基于第三方工具的实现方法，都需要在某些特定的条件下才能实现，存在开销过大、改造成本过高的问题;影子表法是一种通用的基于数据集合本身的增量提取方法，但现有的影子表法对海量数据的增量提取效率低下。本文以提高影子表法效率为重心，主要工作如下:
　　 (1)针对邻近排序影子表法效率低下的问题，提出了一种基于HASH算法的改进型影子表增量提取方法(ST-HJ)。在使用影子表法进行增量提取的过程中，邻近排序法需要对集合进行排序，而对于海量数据的排序效率会很低。为了解决该问题，本文在研究现有影子表法原理和HASH算法的基础上，找到了一种通过将备份表记录映射成散列表，同时利用原始表记录依次到散列表中探测获取增量的方式。该方法不需要对集合进行排序，只需线性扫描一次数据集合就能获取增量记录。实验表明，在对比字段较少的情况下，ST-HJ算法效率较邻近排序法提升了近60％，而在对比字段较多的情况下，效率提升不到10％。
　　 (2)针对多属字段情况下效率提升不明显的问题，本文对ST-HJ算法进行了完善。在分析ST-HJ算法在多属性字段比对的情况下效率提升不明显的原因后发现，是由于多属性字段的比对及其HASH运算造成了算法性能的降低。为了解决此问题，本文在研究“影子主码”和MD5算法的基础上，通过MD5算法将多属性字段变换为固定长度的字符串，然后再结合ST-HJ算法实现增量提取。该方法限定了比对字符串的长度，同时具有了ST-HJ算法的优势。实验表明，在多属性字段比对的情况下，完善后的ST-HJ算法效率提升了近40％。
　　 (3)以ST-HJ算法为基础，实现了一个数据库增量备份系统。将系统应用于中国移动湖南省公司的《移动异常话单监控与分析系统》项目中，实现了异常话单的高效备份，同时减轻了对原有系统的影响。该技术方案得到了中国移动工作人员的一致好评。

目录

声明

摘要

插图索引

附表索引

第1章 绪论

1．1 选题背景及其研究意义

1．1．1 选题背景

1．1．2 研究意义

1．2 数据库备份技术的国内外研究现状

1．2．1 数据库备份技术的国外研究现状

1．2．2 数据库备份技术的国内研究现状

1．3 论文主要研究内容

1．4 论文的组织结构

第2章 数据库中的增量提取技术

2．1 前言

2．2 数据备份的基本概念

2．2．1 数据备份基本原理

2．2．2 现有数据备份技术介绍

2．2．3 数据备份流程

2．3 增量提取的基本概念

2．4 现有常用的增量提取方法介绍

2．4．1 触发器方式

2．4．2 系统日志分析方式

2．4．3 基于快照增量提取法

2．4．4 时间戳方式

2．4．5 影子表法

2．5 几种增量提取方法的对比

2．6 本章小结

第3章 基于HASH算法的改进型影子表法

3．1 前言

3．2 影子表法增量提取原理

3．3 通过减少比对次数的增量提取算法

3．3．1 算法概述

3．3．2 算法描述

3．4 算法复杂度分析

3．5 实验结果展示

3．5．1 测试数据

3．5．2 NOT EXISTS和S-MJ方法的对比

3．5．3 ST-HJ算法与S-MJ算法的对比

3．5．4 字段数增多对新算法的影响

3．6 本章小结

第4章 改进型影子表法在多属性字段中的应用

4．1 前言

4．2 融入MD5的ST-HJ增量提取方法介绍

4．2．1 算法概述

4．2．2 算法描述

4．3 算法复杂度分析

4．3．1 时间复杂度整体分析

4．3．2 明细时间分析

4．3．3 算法复杂度小结

4．4 实验结果展示

4．4．1 测试概述及方法介绍

4．4．2 测试环境

4．4．3 测试结果及分析

4．5 本章小结

第5章 数据库增量备份系统的实现及其应用

5．1 前言

5．2 数据备份系统总体设计

5．3 系统结构模块设计

5．3．1 数据备份代理

5．3．2 服务器代理

5．3．3 存储代理

5．3．4 代理间通信接口

5．4 系统应用

5．5 本章小结

结论

参考文献

致谢

附录A 攻读硕士期间所发表的学术论文目录

附录B 攻读硕士期间参与的项目列表