论文部分内容阅读
作为多维数据处理的核心问题，多维索引一直是数据库研究的热点方向。随着医药、CAD、地理，以及分子生物学等的不断发展，对于以支持多维数据管理的数据库系统的研究正在逐步深入。一方面以多维查询为核心的处理对数据库的索引查询效率提出了更高的要求;另一方面，与多维数据相应的海量的数据对索引结构的存储效率也有很高的要求。支持高效多维数据处理的数据库平台在多媒体、地理信息、分子生物、数据挖掘等方面有着广泛的应用。鉴于空间填充曲线作为一种N维空间与一维空间的映射方法，能消除数据多维特征的复杂性，课题确定了以空间填充曲线作为多维索引的实现基础。通过对比分析空间填充曲线族的聚集性特征，确定了采用Hilbert曲线作为研究方向。课题着重研究了实现基于Hilbert曲线的多维索引的几个关键问题。具体研究内容包括:降维索引模型、N维Hilbert解析算法、N维Hilbert曲线生成和映射算法、范围查询分析算法和查询优化策略及多维索引引擎的实现等问题。研究成果为国产达梦数据库系统提供多维数据管理方面的技术支持。 以传统关系型数据库作为平台，提出了一种基于Hilbert曲线的多维索引模型。模型采用降维技术实现了多维数据与B+树结构的结合，实现了高效的数据存储;利用Hilbert曲线的良好的聚集性，实现了高效的多维索引查询。该模型在不改变传统关系型数据库索引机制的基础上，提供了高效的多维数据处理支持。由于以传统关系型数据库作为平台，因此模型在稳定性、安全性、数据存储，以及用户接口等方面具有其它模型所不具备的优势。同时也使传统数据库有了更广的适用范围。整个模型包含用户接口、中间件，以及基础算法集。其中基础算法是本课题的研究重点，包括Hilbert的相关算法、范围分析算法和查询优化等内容。 针对N维Hilbert曲线的构造问题，提出了N维Hilbert曲线的解析算法。解析算法以Hilbert曲线的对称性和自相似性为基础，采用演化的思想进行解析，给出了Hilbert单元的编码描述和Hilbert基因的生成描述。算法实际上是给出了一种新的N维Hilbert曲线的描述方法。解析算法为实现高效的N维Hilbert双向映射奠定了基础。 在N维Hilbert解析算法的基础上，给出了一种新的N维Hilbert映射算法。映射算法以Hilbert单元编码和曲线基因表为基础，基于静态演化规则，采用高效的位运算进行映射计算。实验显示新算法的双向映射效率在10维以内与Z-order算法接近。这就使得过去由于高维Hilbert曲线的复杂性，在实用中以Z-order映射为主的状况得以改变，为在实用中全面取代Z-order映射打下了技术基础。 针对范围查询问题，提出了Hilbert范围分析算法，算法实现了把一个N维的矩形范围描述，转换成等价的一维Hilbert线段集合。利用范围分析算法，就能在B+树上实现多维范围查询。由于精确的Hilbert范围分析具有较大的时空复杂度，不能很好的适应查询的效率要求。因此对范围查询分析进行了改进，提出了降低分析精度的优化策略。实验表明优化策略能有效提高分析效率，实现高效的范围查询。Hilbert曲线是超立方的空间填充，因此矩形范围查询是其它类型查询的基础。在实现高效的矩形查询的基础上，提出了圆范围查询、最近邻查询、K近邻查询等算法。 基于Hilbert曲线相关算法和查询分析算法，设计并实现了一个多维数据处理引擎的原型系统。该系统在总体上采用了三层体系结构，包括底层数据库管理器和具有数据转换、数据维护等功能的中间层，以及最上层的用户接口。由于系统设计采用了开放的外挂模块的设计思想，因此，系统具有良好的可扩展性，同时可支持当前各种主流的数据库平台。利用原型系统，我们对三维位图和二维地理信息数据进行了实验。实验显示原型系统在查询效率上优于DBMS的组合簇索引和R树索引。