论文部分内容阅读
本论文所讨论的数据清洗是通过对数据库海量数据冗余信息的匹配、探测并去除错误数据和矛盾数据、提高数据质量的过程。数据质量问题出现在多个数据集合之间。由于出现数据输入错误、数据源异构、数据表示方法通用性差等情况,从而导致现有的数据库中存在这样或那样的“脏数据”。这些“脏数据”大大地干扰了数据处理结果的正确性、有效性和利用率。“数据清洗”利用数理统计、数据挖掘和预定义行业专家库等技术,将“脏数据”转化为满足数据质量要求的数据。为此,“数据清洗”过程在银行、电信、移动的海量数据管理和维护中显得越来越重要。数据清洗过程可大致分为:数据解析、数据格式规范化、数据匹配、数据修正、清洗结果检查这5个比较大的步骤。本文主要讨论的焦点在于海量数据的数据匹配问题,利用现在发展比较迅速的内存数据库系统(Main Memory Database System, MMDB)的相关技术,根据数据匹配的一些特殊性,提出了一种MDB-树索引结构,以及该索引结构下的插入算法和查询算法。数据匹配从一定程度上可以说是数据库记录的精确匹配查询。传统的数据库查询优化的关注点是减少访问磁盘数据的I/O次数。面对数据清洗中海量数据匹配查询,以前旧的DRDB (Disk-Resident Database)已经不再适用。随着计算机硬件技术的发展,在内存中存贮整个数据库数据已经成为可能。这使得内存数据库系统(Main Memory Database System, MMDB)近年来发展迅速。它把所有数据都放入内存中,避免了在查询过程中大量的磁盘I/O操作,在一定程度上提高了查询的执行时间。在MMDB上,由于没有磁盘的I/O操作,因此提高数据匹配效率的关键变成了处理器的计算时间和缓存的有效利用率。处理该问题的方法很多,其中一种方法就是建立合理的数据索引结构,减少查询过程中的匹配失效,从而缩短处理器的执行时间。本文详细研究了现在数据库的数据索引结构,并根据数据匹配的一些特殊性,提出了一种MDB-树(Main Delicate B -tree)索引结构,以及该索引结构下的插入算法和查询算法。利用Cache和TLB失效模型和执行时间模型,对该索引结构和常见的索引结构进行了性能分析。从分析结果中可以看出,MDB-树索引结构克服了原有的索引结构在MMDB中暴露出输出速率提升水平低、缓存冲突过多、使用指针过度等缺点,提高了数据匹配效率。