基于March算法的网络多维数据优化存储方法

胡茂美

(合肥滨湖职业技术学院 机电与汽车工程学院，安徽 合肥 230601)

数据库技术的迅速发展，导致各行各业积攒过多的数据量，信息存储在企业发展过程中具有重要意义.数据库的主要应用范围是决策与分析，为这两个应用提供优越的工作平台[1]，数据库内数据存储形式均是多维的.提升在数据库内搜索有价值信息的效率，可帮助企业快速了解其自身情况[2].OLAP技术为用户提供了一种决策支持的有效方法[3]，该技术可提升用户查询数据速度，方便用户使用，操作简单.多维数据集属于OLAP数据查询的核心，通过Data Cube多维分析实现OLAP查询.在Data Cube内包含数据的全部细节信息，也包含不同粒度中的聚集值.聚集记录会浪费存储空间，延长计算时间[4]，降低OLAP分析效率，因此提升多维数据存储效率是目前数据库的主要研究方向.赵亚楠等人针对小文件存储问题，提出大数据分布式存储方法，提升存储效率[5]；陈波等人针对大量数据管理方式存在的缺陷，提出GeoSOT剖分网格的数据存储方法，集中存储大量数据，提升存储效率[6].这两种方法的缺点是未考虑多维数据存储空间较大问题，严重浪费存储空间.March算法为存储器中常用的功能测试与地址解码等测试向量，具备较优的故障与存储时间测量性能[7].为此研究基于March算法的网络多维数据优化存储方法，节约存储空间，提升存储效率.

1 基于March算法的网络多维数据优化存储方法

1.1 网络多维数据存储结构

网络多维数据的组织方式共有两种，分别是维数据与度量数据组织，前者通过多维数据结构与存储维的结构信息完成数据组织[8]，后者通过加快聚集查询效率完成数据组织.

1.1.1 存储组织多维数据

组织维数据的步骤如下：

步骤1：存储组织数据特征提取；

步骤2：映射特征点数据，使其变成多维数据组的坐标值.

维层次的偏序存在一定关系，该关系的表达形式是格，通过这些格构建一个无环图，该图具备方向性，这就说明能够由邻接表描绘并组织维的层次结构及成员间的关系[9].建立一个在全部层次以上的层次all，以all为起始点，建立一棵树，all代表其根节点，all的孩子节点为其下层的全部成员.组织维成员可完成多维数据处理技术的Roll up与Drill down操作[10].然后，需对其实施编码，具体步骤如下：

步骤1：整数编码，在网络多维数据组内，各维中的坐标均是整数，因此需将维护成员变更为整数.令多维数据集Gα的一个层次h中的成员是p1,…,pn，整数编码的步骤为：

a.建立映射函数f；

b.针对h中的成员p1的f是f(p1)=0；

c.如果pα,1≤α≤n与pβ,1≤β≤n属于邻近，且pα≤pβ，那么f(pβ)=f(pα)+1.

令多维数据空间是(G1,G2,…,Gn,F1,F2,…,Fp)，每个维的尺寸一致，由Gα表示，利用上述操作完成整数编码，编码后的多维数组是(g1,g2,…,gn,f1,f2,…,fp)，那么多维数据位置是pos=(…((g1*G2+g2)*G3+…+gn-2)*Gn-1+gn-1)*Gn+gn.

1.1.2 存储组织度量数据

令(G1,G2,…,Gn,F1,F2,…,Fp)，多维数据集Gα组建的数组是G1×G2×…×Gn，顺序存储过程中，依据G1,G2,…,Gn顺序排列度量元素的位置[12].

1.2 March算法

March算法属于常用的存储器测试方法，即对存储器内的存储方法展开测试，优化网络多维数据存储方法.该算法存在高故障覆盖率与低时间复杂度的优势.测试步骤如下：

步骤1：在全部存储器内写入所有是零的背景；

步骤2：读取首个存储单元，其正确读取结果是0；

步骤3：将一个1录入首个存储单元，随后读取该单元，正确读取结果是1；

步骤4：同理，剩余存储单元执行步骤2与3，以全部存储单元完成操作为止[13]；

步骤5：所有单元的内容都是1，代表全部单元的背景均是1；

步骤6：读取首个存储单元[14]，正确读取结果是1；

步骤7：将一个0录入首个存储单元，随后读取该单元，正确读取结果是0；

步骤8：同理，剩余存储单元执行步骤6与7，以全部存储单元完成操作为止.

步骤6能够执行反操作，代表能够以最后一个单元为起始点，按照顺序执行读取操作[15]，结束条件是首个单元完成操作，以公式的形式表达如下：

(1)

其中，第i行第j列的存储单元是Bij；读取Bij的操作是RBij；将1录入Bij内的操作是W(1)Bij；将0录入内的操作是W(0)Bij；所有Bij的集合是∀ij；集合∀ij中的总和是∑；公式中全部操作过程中的分隔符是“，”；背景0与1是下标0与1.

利用公式(1)能够计算获取存储方法的复杂度是2(1+1)N+N=5N，N代表单元数量.测试的操作次数由5N描绘，5N乘上完成各操作的时间就是总测试时间.5N的大小与测试时间成正比.

通过增加March算法的测试向量，加强其测试效率与故障覆盖率，增加后的数据叫作数据背景(Data Back-ground).在March算法内读取与录入数据是1与0的情况下，便需将正向与逆向的数据背景用于相应的存储方法中.

2 实验分析

首先构建一个P2P网络，在该网络内各塑造一个Web服务器与Tracker Server服务器，剩余节点是OLAP网络节点，在该网络节点内建立一个虚拟的多维数据库，该数据库内共包含50 000个文件夹，利用方法对该数据库内的多维数据实施优化存储，验证本文方法的有效性.

选取大数据分布式存储方法[5]，GeoSOT剖分网格数据存储方法[6]作为本文的对比方法，测试本文方法在优化前后存储不同文件夹数量时的各项性能，共实施5次实验，记录每次实验的优化前后的数据存储时间，取5次记录时间的均值，测试结果如表1所示.

表1 3种方法的各项性能对比结果

根据表1可知，在存储不同文件夹数量时，本文方法的系统响应时间在文件夹数量较少时优势不明显，当文件夹数量超过20000时，本文方法的系统响应时间显著低于其余两种方法；其余两种方法在存储多维数据时所占内存较大，本文方法存储多维数据时的占用内存较小，原因是本文方法中包含压缩存储过程，有效减小内存占用空间；在文件夹数量较少时，其余两种方法存储多维数据时的导入与导出响应时间较短，与本文方法的多维数据导入与导出响应时间差距不大，当文件夹数量较多时，其余两种方法的多维数据导入与导出响应时间明显增长，响应速度显著下降，本文方法的多维数据导入与导出响应时间无明显变化，仅有小幅度增长现象，响应速度较快.实验证明：在存储不同文件夹数量时，本文方法的响应速度较快即存储效率高，内存占用空间最小，具备较优的数据存储性能.

测试3种方法分别存储文件夹数量为5 000与50 000个时的数据存储信噪比，测试在不同压缩比时3种方法在数据存储过程中的信噪比，测试结果如图1与图2所示.

根据图1与图2可知，文件夹数量为5 000时，压缩比逐渐提升，本文方法在存储多维数据时的信噪比无明显变化，平均信噪比为94.5 dB；其余两种方法的信噪比前期下降幅度较小，当压缩比超过50后，其信噪比下降幅度均较大，平均信噪比分别为67.9 dB与69.9 dB；文件数量为50 000时，压缩比逐渐提升，本文方法在存储多维数据时的信噪比出现小幅度下降趋势，平均信噪比为85.3 dB；其余两种方法的信噪比下降幅度较大，当压缩比为80时，两种方法均出现数据存储失真情况，平均信噪比为38.1 dB与39.3 dB.

压缩比图1 文件夹数量为5 000时的信噪比

压缩比图2 文件夹数量为50 000时的信噪比

实验证明：文件夹数量较大时，本文方法在存储多维数据过程中的信噪比有所降低，但依旧高于其余两种方法，在不同压缩比时，本文方法在数据存储过程中的信噪比最高.

文件夹数量为50 000时，3种方法的各项性能差距最为明显，因此测试3种方法在存储文件夹数量为50 000时且不同稀疏度情况下的数据存储信噪比，数据稀疏度越高，所需存储的字数越少，在不同稀疏度时的数据存储过程中的信噪比测试结果如图3所示.

稀疏度图3 不同稀疏度时的信噪比测试结果

根据图3可知，随着稀疏度的不断提升，3种方法数据存储过程中的信噪比均有所增长，其余两种方法的信噪比增长幅度较小，当稀疏度达到10时，大数据分布式存储方法的信噪比不再发生改变，稳定在25 dB左右；当稀疏度达到12时，GeoSOT剖分网格数据存储方法的信噪比不再发生改变，稳定在30 dB左右；本文方法的信噪比在前期增长速度较为缓慢，当稀疏度超过8时，信噪比增长速度较快.实验证明：在不同稀疏度时，本文方法的多维数据存储性能最优.

3 结 论

数据库在各大领域的广泛应用，导致各领域的网络多维数据累积量显著增长，造成传统的多维数据存储方法不足以满足用户对数据库的高要求.因此提出基于March算法的网络多维数据优化存储方法，提升数据优化存储性能，更好地符合MOLAP快速性的要求.