一种新的前缀立方索引机制

1、一种新的前缀立方索引机制1 引 言数据立方1通过预先对基本关系表中的数据在所有可能的维属性组合之上计算聚集来达到减少实时计算的目的，从而加快OLAP中查询响应速度。但是，预先计算却使得数据立方占用存储的空间随着维数的增加而剧增，而存储巨大的数据立方所带来的大量I/O操作导致了不菲的查询代价。通过研究发现，立方元组之间存在两种冗余，即前缀冗余和后缀冗余。通过消除冗余，新的立方形式，如浓缩数据立方2（Condensed Cube），Dwarf3，Quotient Cube4和 QC-Trees5等，在不破坏数据立方完整性的同时大大缩小了数据立方的尺寸。由于浓缩数据立方的各个小方的元组之间依然存在前

2、缀冗余，所以通过压缩这些前缀冗余就得到了空间代价更小的前缀立方（PrefixCube）6,7。本文提出一种新的前缀立方索引机制Bound-CuboidTree，并通过在真实气象数据及和人造模拟数据集上进行的大量实验来证明其效率。2 前缀立方前缀立方拥有两个互不相交的子立方，一个由所有普通立方元组组成，称为普通子立方；另一个由所有基本单元组2,6组成，称为单元组子立方。在普通子立方中，所有的普通立方元组按数据小方聚簇，即属于同一数据小方的立方元组属于同一个簇，一个簇被称作是一个普通数据小方（normal cuboid）；在单元组子立方中，所有的基本单元组按单值维集聚簇，即具有相同单值维集的基本单

3、元组属于同一个簇，一个簇被称作是一个虚数据小方（virtual cuboid）。如果给定一个基表R如表1所示，我们可以的到其前缀立方的基本结构如图1所示。表1 基本关系表R ABCMt1811100t218150t312360图1是基表R对应的前缀立方结构。前缀立方的头节点N-Roots指向一组N-prefixTree，每一棵N-prefixTree对应一个普通数据小方；头节点V-Roots指向一组V-prefixTree，每一棵V-prefixTree对应一个虚数据小方。除普通数据小方Cuboid（CID=ALL）外，N-prefixTree的高度与其对应普通数据小方的聚集属性个数相同；V-

4、prefixTree的高度则等于其对应的虚数据小方单值维集中维个数加上单值维集最后一个维之后的所有维的个数。前缀树的一层对应一个维。每个小方中，具有相同首维维值的元组形成了一个分组结构。图1中标出了Cuboid（SID=B）的一个分组结构。图1 基本关系R对应的前缀立方的逻辑结构在前缀立方的存储当中，无论是普通数据小方还是虚数据小方都是把元组按维值从小到大的顺序存储到若干固定大小的磁盘页面内，一个页面被称为一个数据块（data block）。数据块中的元组经过前缀共享形成若干个分组结构，分组结构并不跨越块。在同一个数据块内，不同分组按首维维值升序排列；同一个分组内的元组按维值升序排列，并依次共

5、享前缀。逻辑上，属于同一个数据小方的所有元组长度相同，即各元组的维数和聚集维数对应相同，但实际存储一条元组时，该元组的某个维值可能因为共享前一条元组对应维的值而无需存储，从而导致实际存储的元组长度各不相同。所以在原始元组前面加一个数值，用来表示这条元组的实际长度。表2虚小方Cuboid（SID=B）图2 表2对应的数据块数据块内建分组索引。分组索引记录每一个分组在数据块内的相对位置。所以，一个数据块包含了数据、分组索引和块控制信息等三个部分。表2表示一个虚数据小方Cuboid（SID=B），包含聚集维属性B和非聚集维C和一个度量属性M。图2是表2存入数据块后数据块内的结构。从图2可知，该数据块

6、内含有三个分组，索引pi（i=1,2,3）分别对应第i个分组的相对位置。每个分组的首元组都是没有共享其余元组的维值。如，数据块的第一条元组（4,1,1,100），其中4是元组的长度，等于长度（1）加上维数（2）加上度量维数（1）。3 索引前缀立方3.1 Prefix-CuboidTreePrefix-CuboidTree8,10是我们先前提出的一种前缀立方的索引。它通过把多维上的点（这里指立方元组）表示成该点在空间填充曲线C-曲线9,10上的位置，从而把整个多维空间线性化成一维空间由于数据立方的范围查询事实上都可以归结为对若干个特定数据小方的范围查询11，所以我们把每个小方看成是一个独立的多维

7、空间。Prefix-CuboidTree首先按照C-曲线映射方式把小方分割成一条一条的C线段，每一条线段对应一个物理数据块。这些线段是连续但不相交的，这是因为经过C-曲线映射的后整个数据空间的数据点的顺序关系并没有改变。如图3所示。然后以这些线段中第一个数据点在C-曲线上的位置作为索引关键字，用B-Tree12对这些线段进行索引，完成对小方的索引，如图4所示。最后对B-Tree索引的根建立索引，完成对整个数据立方的索引。BCMt111100t22360t38150p34 1 1 1004 2 3 604 8 1 50begendp2p1N索引的查询算法首先选取查询最小下界作为初始查询点，然后在

8、索引当中找到包含该查询点的数据块，在过滤出数据块满足查询条件的所有元组后，经过一定算法得到下一个查询点，如果这个查询点落入查询的区间以外，那么结束查询，如果在区间之内，那么继续查找包含该查询点的数据块。应用该索引的前缀立方取得了比浓缩数据立方更好的查询性能。3.2 Bound-CuboidTreePrefix-CuboidTree使用C-曲线对每一个小方的元组进行一维线性化，从而巧妙的避免了映射顺序和小方内分组结构映射顺序之间的矛盾，最终能够把整个空间映射成的直线划分为连续不相交的线段，从而利用B-Tree对映射后所有的线段进行索引。但是，现实世界中的数据往往都是非均匀分布的。虽然数据有聚集的

9、情况，但是大部分空间是未为利用的，这些未利用的区域称为死区（Dead Space）13。从图3可以看到，在整个二维空间中，只有深色小方块才是有效数据区域，剩下所有的空间都是死区。所以，在索引这种数据的时候，怎样避免对死区的查询成为提升索引的查询性能至关重要的问题之一。很不幸，Prefix-CuboidTree并没有考虑到这些问题。从图4中可以发现，Prefix-CuboidTree对整个空间进行划分后。索引了整个空间，包括所有有效空间和几乎所有死区。这样没有对死区进行甄别就直接进行索引的方式，使得索引在范围查询的时候必须要查询到数据块之中才能保证确实不存在符合查询条件的数据。图4 图3中拉直后

10、的C曲线以及Prefix-CuboidTree 图5图3中拉直后的Z曲线以及Bound-CuboidTree为了尽量减少查询死区，提高索引查询效率，在CuboidTree11结构的基础上，我们使用BUB-Tree13索引结构代替Z-KDB-tree14，提出了前缀立方的一种新的索引机制Bound-CuboidTree的结构。之所以使用BUB-Tree是因为1）它所使用的Z-曲线已被证明更能体现数据在多维意义上的位置临近性15；2）它是Z-KDB-tree的一个扩展，能更好集成于CuboidTree结构中；3）它通过采用被索引Z-区间的范围而不是典型值作为索引关键字，减少了范围查询时的死区，提高

11、了查询效率。对比图4、图5我们可以发现，Z-曲线上数据点间的距离要比C-曲线短，这就说明Z-曲线上有效数据点间死区要比C-曲线上要少。虽然Z-曲线相对于C-曲线可以减少有效数据之间的死区，但是由于前缀立方小方内的分组结构的存在，所以我们不能打散原有数据块而只能按照Z-曲线把数据块映射成一维的Z线段。这些线段之间虽然是连续的，但是线段之间却是很有可能是重叠的。如图5的Z线段，如果因为小方中含有元组（3,1,10），显然包含元组（1,1,100）和（2,3,60）的数据块映射后的Z线段区间为3,13，包含元组（3,1,10）和元组（7,1,50）的数据块映射后的区间为11,43，显然，这两个数据块

12、之间的Z范围产生了重叠。而BUB-Tree则要求数据块映射成Z线段后的范围是连续且不相交的，但对于存在分组结构的前缀立方而言，数据块映射的Z线段是连续但相交的。那么，怎样解决表示区间的重叠问题呢？范围的重叠问题经典的解决方案是空间数据库中的R-Tree16索引。R-Tree可以看成是B-Tree对多维对象（点和区域）的扩展。R-Tree是将原始的多维空间划分为合适的重叠子空间。每一个子空间可以看成是多维空间平面上的一个矩形，用空间的边界作为索引的关键字，然后对于每个子空间进行索引。R-Tree通过计算插入后最小的面积增量来控制索引节点的插入和分裂操作，以得到表示数据范围之间重叠达到最小化的索引

13、结点之间表示，从而达到减少索引中间结点查询，节约查询时间的目的。虽然R-Tree是面对多维索引的，其手段是在索引增长的过程中尽量减少面积增量，但是其解决区间重叠问题思想的本质是一样的。针对一维情况下不会产生面积的情况，在索引建立的过程当中，我们在把一个索引入口插入索引节点时，通过选取插入后索引节点表示范围的增量最少的那个索引节点进行插入，使得在索引建立的过程当中尽量减少索引节点之间的范围重叠问题。利用R-Tree只能减少索引生长过程当中索引节点之间的范围重叠的问题。但是面对数据块之间的范围重叠的情况，却是无能为力的。如果查询的区间落入了数据块重叠的范围当中的话，那么这两个数据块都需要查询，从一

14、定程度上加重了查询的负担。我们考虑到，可以利用数据块当中分组范围信息作为索引的副关键字，在遇到上面问题的时候提供更多的甄别信息。使用分组范围信息的原因是：首先分组范围提供了数据块中数据分布情况；其次分组范围之间不存在重叠的现象，这样不会产生新的重叠问题；再次，这样可以在出现查询的Z区间落入了数据块重叠Z区间的范围内的时候可以利用分组的区间信息对两个数据块进一步区分；最后，因为记录数据块中分组信息只要记录所有分组中共享的首维维值的最大值和最小值就可以，这样减轻了索引大小膨胀的压力。综上，结合BUB-Tree和R-Tree技术，我们提出了前缀立方一种新的索引机制Bound-CuboidTree。它

15、首先把前缀立方小方的数据块映射成一维空间的Z线段，使用线段的Z编码上下界作为主关键字，使用线段分组的首维维值范围作为副关键字，利用类R-Tree的索引生长方式对每个小方建立类BUB-Tree索引，最后对每一个BUB-Tree索引的根建立索引。虽然因为增加分组范围作为索引的副关键字而导致建立后的Bound-CuboidTree索引比建立后的Prefix-CuboidTree索引要大，但是在大部分情况下Bound-CuboidTree却要比Prefix-CuboidTree的查询性能好。这说明采用了Z-曲线映射方式和Z-范围表示关键字的Bound-CuboidTree比采用C-曲线映射方式和典型值

16、表示关键字的Prefix-CuboidTree能更有效减少对数据块内和数据块间死区的查询，从而有效减少了查询时间。3.3 Bound-CuboidTree的查询Bound-CuboidTree的范围查询首先把查询条件转换成Z-编码范围，然后选择那些根据索引节点的Z编码范围与查询条件的Z编码的相交的路径进行查询。但是，查询条件转换成Z-编码以后查询空间中会包含着大量我们并不需要查询的数据信息，我们称之为查询的无效区间（Invalid Space）。例如，一个查询Select A, B from Cuboid（CID=AB）where 1=A=2 and 1=B=2我们得到查询条件是（1,1）-（

17、2,2），那么计算成Z编码以后就是3,12，但是实际上我们只需要查询的记录是（1,1），（1,2），（2,1），（2,2），计算成Z编码后为（3,6,9,12） 4个点，所以区间4,5 7,810,11是查询的无效区间。若根据索引的节点的Z范围把原始查询分解成多个子查询，然后根据分解后的子查询对查询的路径进行剪枝和过滤，这样就可以减少对无效区间的查询。例如，如果能把查询分解成3,6和9,12两个区间的话，就能够避免查询7,8这个无效区间。所以，在查询当中，Bound-CuboidTree根据当前索引提供路径所包含的数据范围的情况对查询进行分解，这样一来，减少了因为选择包含查询的无效区间的路径而

18、引起的总的查询时间的增加。在范围查询算法的策略上，Bound-CuboidTree采用了与Prefix-CuboidTree不同的策略。如3.1节所述，Prefix-CuboidTree的查询采用的是深度优先的策略。Bound-CuboidTree则是采用的是宽度优先的策略，查询对索引每一层进行查找，找到该层所有可能路径，然后根据这些路径到下索引下一层查找直至找到所有满足条件的数据块。4实验分析4.1实验设计试验对比的是Bound-CuboidTree（简称B-CTree）和Prefix-CuboidTree（简称P-CTree）的范围查询性能。性能比较的标准是同数据集同查询条件下一个范围查询

19、的平均查询时间（单位：毫秒/ms）。实验采用的数据集为气象数据集17，模拟生成的均匀分布数据（Uniform）和自相似（Self-Similar）数据。气象数据集基表总共包含1,015,367条元组，每条元组有9个维，各个维的基数依次为：station-id（7,037），longitude（352），solar-altitude（179），latitude（152），present-weather（101），day（30），weather-change-code（10），hour（8），brightness（2）。自相似和均匀分布的数据基表都有200,000条元组，每条元组9个维，各个维的基

20、数分别为2000，1000，500，200，100，80，60，50，30。实验平台为：Celeron 500MHZ，256MB内存，60GB IDE硬盘，Windows 2000操作系统。我们在所有数据集上分别进行维度（dimensions）变化和选择度（selectivity）变化的范围查询实验。维度试验固定选择度为1/4，维度从2到9变化来考察维度变化对范围查询的影响，对每一个数据小方，我们随机生成10个范围查询；选择度试验固定维度为9，选择度从1/8到1渐变（每次试验选择度调高1/8），来考察选择度变化对范围查询的影响，同样的，对每一个数据小方，我们也随机生成10个范围查询。4.2实验结果及其分析实验首先比较维度变化时B-CTree和P-CTree的查询性能，见图2上半部分。实验结果表明，在气象和均匀分布数据集上维度越大，B-CTree的查询性能越好。这是因为随着维度的增加，数据分布更为稀疏，这样，一方面Z-边界关键字越能准确分辨所查询的数据块中是否存在符合当前查询条件的元组，另一方面稀疏的数据更有利于副关键