现代数据库多维索引研究现状

多维索引是对索引进行支持的工具，具有很多系统化的实际应用。在IBM公司，QBIC系统是最早被推出的，K-L变换降低了特征维数，同时实现了R-树在其索引上的构造。在哥伦比亚大学开发的系统中，Visual Seek系统实现了二进树在算法上的构造索引，支持位置关系上的查询。该索引的方法众多，包括多维二叉树算法、Cell索引算法、Quad-树和K-d-树索引算法、Gnid-树索引算法等。比起早期在算法上的研究，其在结构上是比较简单的，并不适合现在的高维数据。

在多维索引方法中，比较流行的有R-树、线性四叉树和栅格文件。对于R-树而言，其与其变体相比多维索引是最有效的方式。但是对于R树类索引结构来说，其在进行构造时是在几何意义上进行覆盖的，在数据量和维数增多的同时，其具有的检索性能是在降低的，甚至比顺序扫描更低，n维特征向量是向着20以内的m维进行转换的。维数的降低在一定程度上会导致信息出现丢失的情况，其在查询结果中出现的错误记录也比较多。就目前而言，基于维数下降的算法仍是研究的热点。一般情况下，多维数据能起到关键作用的都是少数。因此，既要实现降维的目的，又要尽可能减少信息丢失的情况，降维技术是其重要的研究内容。

（一）多维数据库的查询类型

对于一种查询方法来说，如果它是合适的，则多维空间数据索引这一环节是十分重要的。与传统的关系数据库相比，多维空间数据在查询方法上对一种标准的空间在代数上的描述目前还没有标准，在空间查询语言方面也没有标准。有时对于一些抽象的数据类型来说，它在进行扩展时使用的是结构化的查询语言，可以用来实现对空间数据目标的查询。但在一般情况下，多维空间数据在查询上相比不同领域可以实现对其的定义。在查询结构上，一般来说是空间数据在其目标集合上的查询。下面对多维空间数据查询的类型进行详细介绍。

1.点查询

点查询是所有查询类型中最简单的。它先规定数据库中的一个点，再对数据库进行相应的检索。这种查询方式类似于对坐标中的点进行查询。点查询实现了查询方式的简化，是对查询数据库中是否有相似点进行的判断，但这种相似点在位置上是不具体的。

2.范围查询

范围查询要对查询点Q、度量M和距离r进行规定，然后在数据库中相应地以固定度量对小于或与r相等距离的点集P进行查询。很明显，相对于点查询而言，范围查询是在度量M和r=0时的特殊情况。若M是欧式距离度量，则在进行范围查询时，数据库中的查询点相对数据空间在其几何意义上的形状是一个球体。

3.最近邻查询

相对点查询和范围查询而言，最近邻查询虽然更加简单，但是缺陷也更加明显，即查询结构上的集合是不可知的。这就是说，用户对查询范围r进行定义后，并不清楚查询结构在数量上的情况。这会导致两种极端的情况出现：一种是没有查到相应的结构，另一种是整个数据库的查询结构包括了数据目标。出现这样的问题是难以接受的，因此最近邻查询才被引入。

在最近邻查询中，先对查询在结果集上的大小进行定义，然后利用近邻原则进行查询。相对数据库而言，其返回的结果是距离查询点最近的数据目标。当查询对象和数据库中的几点在距离上相同时，则可用两种方法进行处理：一种是对这些查询结构进行返回，另一种是对其中的一个结构进行选择，以此作为最后的结构。根据返回结果的不同，最近邻查询又分为确定性最近邻查询和不确定性最近邻查询两种。

4.K-最近邻查询

如果用户在需求上只是希望得到不只一个进行查询的最近的点，同时也是与K最近邻的点，那么使用K-最近邻查询是合适的。由此可见，K-最近邻查询就是从数据库中选择距离查询点最近的K个点。K-最近邻查询与最近邻查询是相同的，不仅存在K个解的情况，而且在特殊情况下其解可能多于K个。

（二）多维数据和多维索引结构的特点

多维数据具有以下特点：

1.结构复杂

多维数据是指多维空间的数据。它一般不像传统的关系型数据库一样，可以用固定大小的条目来保存。

2.动态特性

在插入和删除的过程中，多给数据往往还伴随着对数据本身的修改。

3.数据海量

多维数据库的存储空间比较大。

4.操作多样化

对多维数据而言，其没有标准的操作，一般要根据实际需要而定。

5.时间代价大

尽管多维数据库的操作所花费的时间各不相同，但一般都高于传统的关系型数据库。

6.不能排序

相对空间在其数据上的二线性排序而言，多维空间在其相邻的数据上也依然保持相邻状态。因为多维空间数据的存取依赖于其空间位置，所以空间索引的建立应根据其在数据空间上所具有的邻近性来实现。但是，多维数据空间无法实现其在临近关系上的排序并作出反应。也就是说，在多维空间中是无法实现一维空间上f的映射的，同时多维空间在其中任意两点之间是相邻的。(https://www.xing528.com)

针对以上这些特性，目前还没有找到一种效率更高的空间索引机制。虽然人们可以不断改进空间索引机制，但是仍旧无法打破多维空间的束缚。这是因为多维索引结构具有以下特点：

（1）动态构造。数据在数据库中的插入和删除等操作是可以随意进行的，并且支持其在索引结构上的相应操作。

（2）二级/三级存储管理。虽然主存容量变得越来越大，但是在主存中实现数据库的保存是十分困难的，所以，索引结构需要实现二级/三级的存储管理。对于传统数据库而言，虽然它们在存取方法上是可行并且有效的，但是它们都是一维的。一般来说，需要对一维存取进行适当的扩展，以实现对多维数据的处理。

（3）独立于数据的输入和插入顺序，多维数据索引支持任意顺序。

（4）可增长性。索引结构应能适应数据库大小的增长。

（5）时间的有效性。查找速度必须是快速的。

（6）空间的有效性。索引结构应比原数据要小，而且还要保证一定的空间利用率。

（7）能支持尽量多的操作，并保证操作的并行性和可恢复性。

（三）数据库中的多维数据索引结构分析

在数据库的研究方面，多维数据索引这一技术一直处于至关重要的地位。与一些比较成熟的索引技术相比，关系数据库得到了充分的应用。下面对常用的基于树形结构的多维索引、基于空间曲线填充的降维方法和位图索引进行重点分析。

1.树形结构多维索引

在查询效率上，树形结构比顺序文件具有更高的效率，同时在维护上的开销也更小，所以，树形结构在索引研究中是广受关注的，其中比较具有代表性的就是B树索引。虽然B树索引目前在文件系统和数据管理系统中得到了一定的应用，但是B树索引在查询上只支持一维键值，相比多维查询而言，它需要建立更多的B树，以保证占据更大的存储空间。由于B树索引在维护上是比较困难的，提出了对多维索引树结构上的支持，如R树索引、KD树索引等。

（1）R树索引。

R树是平衡树。相对B树来说，R树是在多维空间上进行扩展的。R树将附近的数据对象圈起来，形成一个矩形形状，被称为“最小外包矩形”（Minimal Bounding Rectangle，简称MBR）。对于每一个MBR而言，R树在其索引上都是一个叶结点，同时，MBR在其区间上的数值比较小，因此可以实现对较大数值区间的MBR的覆盖，从而形成父结点。

R树在查询操作上是从树的根结点t开始的，若其不是叶子结点，t中的索引项应检查MBR与查询区间的重叠程度。如果有重叠的情况发生，则要先选中这一索引项，再寻找其子结点，同时继续进行查询操作；如果没有重叠的情况发生，无需选择这一索引项，可继续查询，直到叶子结点被找到为止。叶子结点索引项对数据进行读取后，如果有需要，应对所读出的信息进行检查，查看其是否满足查询条件，最后返回查询结果。

R树在进行插入时，其插入的不是一个点，而是对该点最小的外包矩形进行覆盖。利用查询算法，可以查找数据插入的位置。如果该位置与结点相应的索引项比M小，则对该数据进行直接插入；否则就要对结点进行分裂，同时对其父结点进行回溯，并对该父结点发生分裂的情况进行判断，将停止分裂或者根结点完成访问视为结束。

与查询算法相比，R树在进行删除操作时，要确定该删除操作的位置。如果该位置在其结点上的索引项比m更大，则要直接删除数据，否则就对其结点进行合并，同时对父结点进行回溯。通过其父结点是否已合并进行判断，如果完成了合并，则操作结束，或者其根结点仍在访问中，则结束操作。

R树与B树在索引上是不同的，相比多维查询，建立多个索引是不现实的。由于它们具有一定的相似性，针对多维查询，R树索引只需对数据的查询结果进行遍历即可，且查询效率是较高的。与此同时，R树在数据结构上也是动态呈现的，与插入、删除和查询等操作都是可以交叉实现的，并不需要定期进行全局结构重组，因此维护的代价较低。

（2）KD树索引。

KD树（K- dimension tree）是把二叉搜索树推广到多维数据的一种主存数据结构。KD树是一棵二叉树，其部结点用（a，v）值对表示，其中a是当前的划分维度，v是划分值。在d维的数据空间中，（a，v）形成一个d-1维的超平面，将数据空间划分成两个部分：a值小于v的部分和a值大于或等于v的部分。在KD树的不同层，a依次选用d个维度中的一个，所以树的不同层上的（a，v）是不同的。

KD树在插入、查询和删除上，其算法与二叉搜索树的算法相似，并且相对比较简单。KD树在进行多维查询时，只需对其中的一个维度值进行相应的处理即可，所以在计算上是相对简单的。除此之外，根据属性的不同，其取值上要相应进行交替检查。这对于缩小查询结构的范围是有帮助的。

2.空间曲线填充

树形结构是多维数据索引在多维空间的划分上实现的对子空间的分割。通过对树形结构的利用，实现对这些空间的组织和多维数据的索引。空间区间填充是实现多维索引的另一种方式，其核心思想是对某种曲线在技术上进行填充，同时对多维数据在一维线段上进行映射，然后一维线段在其关键字上实现对多维数据的表示。对于目前的一维索引技术而言，通过组织一维线段，可以构成多维数据索引。

目前，在空间曲线填充上比较有代表性的就是Hilbert曲线、Z曲线和Gray曲线。但是，根据空间曲线填充方式的不同，其填充的规则也是不同的，诸如d维数据空间等，都可以实现对曲线的“填满”。

相关研究领域已经提出了许多被改进的位图索引方法，主要有压缩位图、编码位图和分段位图三种。虽然各方法在使用上各不相同，但它们的核心思想都是对位图索引在存储上进行相应的压缩，提升高位图索引在高基数属性上所具有的实现数据处理的性能。由于位图索引在结构上比较简单，同时其位运算的效率也比较高，这就使位图索引能够满足很多数据上的高纬度查询分析和需求。在数据分析方面，位图索引的应用是相当广泛的。