下载掌阅APP，畅读海量书库
立即打开
从数据形式上分类，索引可以分为向量空间索引和度量空间索引。向量空间可以被看作带有坐标信息的特殊的度量空间。在一定条件下，这两类空间是可以相互转换的。快速映射算法就是一种将度量空间中的对象转换为具有低维坐标的向量空间中的点的算法，当在向量空间中定义好一个距离函数而只取物体之间的距离信息时，就将向量空间转换成了度量空间。不难看出，度量空间索引比向量空间索引具有更普遍的适用范围，所用到的信息更少，难度也更大。
进行相似性查询时，在度量空间中算法执行的主要代价被认为是计算距离函数的CPU代价，因此度量空间索引结构主要考虑的是减少距离函数的计算次数。而在向量空间中进行查询的主要代价被认为是读取磁盘的I/O代价，向量空间索引结构主要考虑的是减少磁盘的I/O次数。
在近几十年对向量空间高维数据索引的研究过程中，已经提出了大量的索引结构。根据索引结构的特点分类如下。
❑根据处理数据的类型，索引可以分为点数据和空间数据。点数据是指那些只能处理点数据的索引结构，如KD（K-Dimensional）树、TV（Telescopic-Vector）树等；空间数据指既可以处理点数据，又可以处理线、矩形等具有一定形状的数据的索引结构，如R树、R*树等。
❑根据索引创建时数据的组织形式，索引可以分为静态结构和动态结构。静态结构是指用批处理的方式将全部数据构建成索引，不支持动态的插入和删除，如packed-R树；动态结构指数据依次插入而生成的索引结构，如动态R树、动态R*树等。
❑根据划分方法的不同，索引可以分为数据划分方法、空间划分方法以及混合型划分方法。数据划分方法是根据数据所在的位置进行层次划分，如R树等；空间划分方法则是将整个数据空间逐渐划分为互相邻接的子空间，如KD树等；混合型划分是指既根据空间进行划分又根据数据进行划分，如混合树等。
❑根据索引的组织形式，索引可以分为树型结构和非树型结构。树型结构指索引结构按照树的形式组织，如KD树、R树等；非树型结构类如VA-File等。
❑根据目录节点的形状，索引结构可以分为矩形、球形和混合型。在构造索引结构时，目录节点形状的选择直接影响检索效率，选择为矩形的有KD树、R树、R*树等；选择为球形的有SS树、TV树等；将矩形和球形结合起来使用的即混合型，如SR树等。
R树类的索引结构类似于B树，一般具有层次性的数据结构，最先出现的R树索引结构是在1984年由Guttman提出的R树。此后人们对它的算法和结构进行了改进，不过大多保持了与R树相同或类似的结构特点。
R树是一种平衡树，如图2-1所示，具有类似于B树的层次结构。在R树中存放的数据并不是原始数据，而是这些数据的最小外接矩形（Minimum Bounding Rectangle, MBR），它具有以下性质。
❑如果用 M 来表示一个节点中可以存放的项数目的最大值，用 m （ m ≤ M /2）来表示一个节点中可以存放的项数目的最小值，则除了根节点外，每个节点中必须包含 m ～ M 个项。
❑根节点中至少要包含两个项，除非它是叶子节点。
❑节点中每个项目的结构为（rect, pointer），在内部节点中，rect是子节点中所有数据的MBR，pointer指向该子节点；在叶子节点中，rect是实际数据的MBR，pointer指向实际数据存放的位置。
❑所有叶子节点出现在同一层上。
R树的查找算法类似于B树，是从根节点出发，检查内部节点每一个项是否与要查找的区域重叠。如果重叠，则查找该项指向的子节点，直至查找到叶子节点。由于在R树中存放的是MBR，这些MBR可能相互重叠，因此无法保证查找操作只搜索一个路径即可成功，在最坏的情况下，一个查找操作可能要遍历所有的路径。
图2-1 R树结构示例
向R树中插入一个数据，实际上是插入该数据的MBR。和查找操作不同的是，一次插入操作只需要遍历一个从根节点到叶子节点的路径，从根节点开始，在经过的每一个内部节点中选择这样的项，它所指向的子节点MBR的面积需要是最小的，如果出现面积相同的情况，则选择MBR最小的一个。
当到达叶子节点时，如果该节点中还有剩余的空间，就将数据插入节点，并按原路径返回，修改其祖先节点中相应项的MBR。假如在叶子节点中已经没有足够的空间存放要插入的数据，则发生分裂，生成一个新的叶子节点，并在其父节点中插入一个指向新叶子节点的项。如果在其父节点中同样出现了溢出，也要产生分裂。如此下去直至根节点，如果根节点也发生了分裂，则生成一个新的根节点，树的高度增加1。
要在R树中删除一个数据，首先要进行一次精确的查询操作，如果找到了该数据，则从节点中将其删除。删除之后如果节点中有足够的项，则依次修改其祖先节点中相应项的MBR。如果在删除后节点中项的数目小于 m ，则将该节点所有的项保存到一个临时缓冲区内，并将该节点从树中删除。如果节点删除后其父节点也出现相同的情况，则要进行相同的操作，如此直至根节点。将临时缓冲区内所有的项重新插入到树中，如果在删除完成之后，根节点只有一个子节点，则这个子节点就成为新的根节点，树的高度减1。
R*树对R树的插入算法和分裂算法进行了一些改进，主要体现在以下两点。
❑提出了强制重新插入的概念，即当一个节点在插入的过程中发生了溢出，并不急于进行分裂，而是首先看一下该层节点在这次插入过程中有没有进行过重新插入，如果没有，则选择一定比例的项从该节点中删除并重新插入到树中；如果该层已经有节点进行过重新插入，则对该节点进行分裂。
❑当节点进行分裂时，不仅要考虑分裂后两个新节点的面积，还要考虑分裂后节点周长以及该层节点的重叠面积等因素。
X树引入了超节点的概念，当节点发生溢出的时候，首先考虑为节点选择合适的分裂算法，以使节点分裂以后的重叠区域小到一定程度，假如无法避免分裂后出现较严重的区域重叠，则不分裂节点，而是扩大节点以放入更多的项，形成超节点。
SS树是一种用于多维点数据相似搜索的索引结构，如图2-2所示。它是对R*树的一种改进，提高了最近邻（Nearest Neighbor, NN）查询的性能。它使用了限定球来划分区域的形状，球的中心是包络点的质心，在树的构建算法中利用质心将各点划分成各向同性的邻居。SS树还改进了R*树的强制重插机制，提高了树结构的动态重构性。因为SS树采用的超球体积很大，导致超球之间重叠严重，所以增加了多路搜索的开销。
图2-2 SS树结构示例
SR树是一种用于高维NN查询的多维索引结构，如图2-3所示。SR树的特点是将限定球与限定矩形相结合，限定球可以将点划分为小直径的区域，而限定矩形可以将点划分为小体积的区域。这样的结合既提高了区域之间的不相连性，又改进了NN查询的性能。性能测试表明，SR树优于SS树和R*树。
图2-3 SR树结构示例
网格文件是一种典型的基于哈希的存取方式，由包含很多与数据桶相关联的单元网格目录组成，一般一个数据桶为硬盘上的一个磁盘页，如图2-4所示。
每个单元只对应一个数据桶，而一个数据桶可以包含几个相邻的单元。因为随着数据增多，网格目录可能会慢慢变大，所以通常将其保存在硬盘上。为了保证在精确查询的时候能仅用两次I/O操作就找到相应的记录，一般将网格本身保存在主存中，网格使用 d 个一维数组表示，这些数组构成了网格的刻度。
在进行精确查询的时候，首先用这些刻度来定位要查找的记录成员，假如这个单元不在内存中，那么将进行一次I/O操作，将这个单元从硬盘调入主存，在这个单元中包含一个指向可能找到记录页的指针，读取这个指针所指的页又需要进行一次I/O操作；而对于范围查询，需要检查所有与要查询的区域相交的单元。
图2-4 网格文件结构示例
向网格文件插入一个数据的时候，首先要进行一次精确查询，以确定该数据项应当插入的单元以及对应的数据页。如果在这个页中还有足够的空间，将数据插入即可。如果已经没有足够的空间，则要根据与该页相关联的单元的数目来决定处理的方法。当有几个单元指向该页的时候，检查现在的刻度中是否有合适的超平面能够成功地将该页分开，如果有，就产生一个新的页并根据这个超平面将数据分配在两个页中。如果现存的超平面没有合适的，或者只有一个单元指向该页时，将引入一个新的超平面并产生一个新的页，然后根据这个超平面分配数据，同时要将这个超平面插入到相应的刻度中，而所有与此超平面相交的单元也要发生分裂。
在网格文件中删除数据，也要先进行一次精确查询，确定该数据所在的单元及对应的数据页，并将其删除。假如在删除之后，这个页中存储的数据低于一定数目，则需要进行相应的处理，根据当前刻度对空间的分割情况，选择同其相邻的页进行合并，还可以取消刻度中的一个超平面。
Excell与网格文件的不同之处在于其所有的网格单元的大小是相同的，每次分裂都将导致目录大小成倍增长。
两层网格文件的基本思想是增加一个网格文件，形成两层网格来管理目录，其中第一层被称为根目录，它是第二层目录的一个大致描述，具有指向第二层目录的指针，而第二层才是真正的目录，它包含指向数据页的指针。这种结构的好处是，当发生分裂的时候，产生的影响被限制在第二层目录的范围内，不会过多影响其他数据。
Twin网格文件也引入了另外一个网格文件，不过与两层网格文件不同的是，这两个文件的关系是对等的，而且每个文件都覆盖了整个空间，数据在这两个文件中的分布是动态的，当在插入过程中某个文件的单元所指向的页出现溢出的时候，在这两个网格文件之间重新分配数据。
KD树是一种在 k 维空间中的二叉查找树，如图2-5所示，它主要存储的是点数据，在每一个内部节点中，用一个 k -1维的超平面将节点所表示的 k 维空间分成两部分，这些超平面在 k 个可能的方向上交替出现，而且在每一个超平面中至少包括一个点数据。
图2-5 KD树示例
KD树的查找和插入操作很简单，而删除操作则有点复杂，因为删除一个点可能会导致子树的重建。KD树只能处理点数据，其他具有一定形状的数据只能用中心点来代替。需要指出的是，数据插入的顺序不同时，KD树的结构也不同，而且数据会分散出现在树的任何地方，而不是仅出现在叶子节点上。
Adaptive KD树是在KD树的结构上做了少许改变，在分裂的时候选择合适的超平面，使分裂后的两部分包含相同数量的数据，而且在这些超平面上不一定包含数据及它们的方向，也不一定严格地在这 k 个可能的方向上交替出现。在这种结构里，内部节点表示的是分裂的超平面，所有的数据都出现在叶子节点中，每个叶子只能包含一定量的数据，超过这个数量的时候就要发生分裂。
KDB树是将Adaptive KD树和B树的特点结合到了一起，如图2-6所示。KDB树采用Adaptive KD树中的用超平面来划分节点中的空间，不过对于一个内部节点所表示的空间，可以用多于一个的超平面来划分，形成几个相邻的子空间，每个子空间对应一个内部节点，所有的数据均存储在相应的叶子节点中。KDB树的结构类似于B树，不过在树中不能保证最小空间的利用率。
图2-6 KDB树结构示例
与KD树类似，Quad树也是用超平面的方法来划分整个空间，不同的是，Quad树不是二叉树，在 k 维空间中，每一个内部节点具有2 k 个子节点，每个子节点对应一个子空间。
例如，对于一个在二维空间的Quad树，每个内部节点拥有4个子节点，每个子节点对应一个矩形。这4个矩形一般用NW（North West）、NE（North East）、SW（South West）以及SE（South East）来表示，如图2-7所示。用这种方法将整个空间逐渐划分到每一个矩形中，直到包含的数据数量低于一定的数目为止。显然这样得到的Quad树不能保证是平衡树，在数据比较密集的地方，树的深度将高于其他的地方。
Quad树的查找操作类似于普通的二叉查找树，在每一层选择要继续查找的子树，对于点查询，只需要选择其中一个合适的，而对于范围查询可能需要几个子树，按照这个方法递归执行，直到查找到树的叶子节点。
图2-7 Quad树结构示例
Point Quad树是Quad树的一个变种，它是由点数据一个接一个连续插入构造出来的。对于每一个点，首先进行一个点查找操作，假如没有在树中发现这个点，则将这个点插入刚才查找操作终止的叶子节点，而这个节点所表示的区域以新插入的点为中心分为2 k 个子空间。
如果从Point Quad树中删除一个点，会引起相应的子树的重建，一个简单的解决方法是将所有子树上的数据重新插入。
这一类索引结构的特点是希望找到某种方法对高维空间中的数据进行近似的排序，使得原来在空间中较为接近的数据能在排序后以比较高的概率排列在一起，那么就可以用一维数据对它们进行索引。这种方法在点查询操作中能够取得良好的效果，但在范围查询时就比较麻烦了。根据这种思路，人们提出了4种将高维空间中的点数据映射到一维空间并排序的方法，如图2-8所示。
图2-8 4种空间填充曲线示例
所有的空间填充曲线都有一个重要的优点，就是可以处理任何维数的数据，前提是映射到一维空间的键值可以任意大。这种方法也有一个明显的缺点，将两个不同区域的索引组合到一起的时候，至少要对其中的一个重新编码。
量化近似的思想首先在VA-File中提出，基本思想是将高维点数据进行压缩和近似存储。首先，对于特定总的比特数 b 以及维数 d ，对每一维 j 分配一定的比特数 bj 。
每一维上的比特数决定了在这一维上的刻度，一般来说，第 j 维需要2 bj +1个刻度来得到2 bj 个区间，其中第一个刻度对应该维的最小值，最后一个刻度对应该维的最大值，其余的刻度对该维进行等分。在插入和删除过程中，这些刻度一般保持不变，只有区间之间点数的差别超过了一定的限制后才重新计算。
对每一个点数据，将每一维所在区间对应的比特串联起来即为它的近似值，用两个浮点数表示的点可以用4个比特来表示，从而实现了对原来数据的压缩。当进行查询的时候，VA-File起到过滤的作用，也就是说首先对这些比特串按顺序扫描，根据比特串所对应区间的边界来确定哪些可能是查询结果的数据，再对得到的结果进行精确的查询。
LPC-File为了近似矢量能够更精确地表示原来的高维矢量，增加了极坐标信息，从而提高了查询精度。
VA-Index最大的特点是引入了矢量量化的方法，而不是采用VA-File和LPC -File中的标量量化方法。这种方法虽然在很大程度上提高了查询效率，但其构造复杂度大大提高，而且需要利用历史数据生成较好的矢量量化器。
Pyramid是第一个降维类索引结构，首先将多维空间中的矢量数据映射为一维数据，然后利用传统的索引结构，如B + 树实现索引及相似查询。在Pyramid中，首先将数据空间分割为以中心点为定点的2 d （ d 为高维空间的维数）个金字塔区域，然后将每个金字塔区域划分为多个区域，其中每个区域对应于B + 树中的一个磁盘页。
在划分数据空间后，对每个金字塔按顺序编号，对落入某个金字塔区域的高维数据，根据其所在区域的标号以及高度可以计算得到一个一维数据。在将高维数据映射到一维数据后，利用B + 树进行索引。在进行范围查询时，将二维数据转换为一维数据。
对每个高维数据，iMinMax首先从该数据的所有维度中选择数值最大的维度和数值最小的维度，然后利用这些数值进行简单的计算，获得该高维数据对应的一维数据，并利用B + 树进行索引。
iDistance首先对所有数据进行分割，在分割得到的每一类中选择一个代表点，并对每一类按顺序编号。对每一个高维数据，首先通过其所在的编号及其与代表点之间的相似度得到一个一维数据，然后利用B + 树进行索引和查询。
向量空间索引适用于具有坐标并且可以利用坐标计算距离的场景。最常见的场景是空间数据库、地理信息系统等，主要依靠向量空间索引进行空间检索（注意，地理信息空间有时也存在度量空间的场景）。空间数据可以按照图形分为点类型、直线类型、曲线类型、面类型、体类型等，这些数据都可以用点数据表示。每个点在实际空间中可以采用地理坐标或其他空间坐标表示。在检索时，可以采用的查询方式如下。
❑精确匹配查询（Exact Match Query, EMQ）：对于给定的查询数据 q ，从数据库中找出所有与 q 相同的数据。
❑点查询（Point Query, PQ）：给定点数据 q ，从数据库中找出所有包含点 q 的数据。
❑窗口查询（Window Query, WQ）：给定一个 d 维的矩形查询区 I d =[ l 1 , u 1 ]×[ l 2 , u 2 ]×…×[ l d , u d ]，从数据库中找出至少包含一个 I 中的点的所有数据。
❑相交查询（Intersection Query, IQ）：给定具有一定形状的空间数据 q ，从数据库中找出至少包含 q 中任意一点的所有数据。
❑包含查询（Enclosure Query, EQ）：给定查询数据 q ，从数据库中找出所有包含 q 的数据。
❑被包含查询（Containment Query, CQ）：给定查询数据 q ，从数据库中找出所有被 q 包含的数据。
❑邻接查询（Adjacency Query, AQ）：给定查询数据 q ，从数据库中找出所有同 q 邻接的数据。
❑范围查询（Range Query, RQ）：给定查询数据 q 与查询距离门限 T ，从数据库中找出所有与 q 距离小于 T 的数据。
❑k-近邻查询（k-Nearest Neighbor Query, k-NNQ）：给定查询数据 q 及正整数 k ，从数据库中找出距离 q 最近的 k 个数据。
面向向量空间的索引可以以空间点坐标为基础，首先利用索引中相关空间划分方法划分空间对象，然后建立索引结构，针对不同的查询方法再设计相应的查询算法，从而满足快速检索空间数据的需要。