高维索引(数据库)

时间：2022-12-22 12:30:01 | 来源：信息时代

时间：2022-12-22 12:30:01 来源：信息时代

    高维索引 : 针对三维或更多维空间数据所建立的索引。随着三维地理信息系统、多媒体数据库及时空数据库的研究和发展,对多维空间目标的搜索及更新功能的要求越来越迫切,而目前常用的空间索引技术,主要是针对一维或二维空间中的空间数据。将这些索引技术运用于三维或更高维空间数据时,其查询效率将大大降低,有时,索引机制甚至不起作用。可扩展的高维索引技术不但能有效地检索一维或二维空间数据,而且能有效地检索高维的空间数据。
1. VP-树
VP-树(vantage point tree)是度量空间(metric space)中较早提出的索引技术。它将三个对象间的距离所存在的三角不等式关系用于近似查询的过滤,从而保证查询的正确性,并减少了目标点和空间数据点之间进行距离计算的次数。VP-树包含两类结点: 内部结点和叶子结点。以二叉VP-树为例,其每个内部结点的结构形如(S_v,M,L_ptr,R_ptr),其中S_v代表受益对象点(vantage point),M是被当前结点所索引的子树中所有数据点与受益点S_v之间的距离的中值,L_ptr和R_ptr分别是指向该索引结点左、右子树的指针。L_ptr指向的数据结点到受益点S_v之间的距离均小于或等于M,R_ptr指向的数据结点到受益点S_v之间的距离均大于或等于M。
对于一个给定的查询对象Q,如果令d(Q,S_v)表示查询对象Q与受益点S_v之间的距离,那么满足与Q之间的距离在某个值r之内的所有数据对象的查找步骤如下:
(1)从根结点开始查找。
(2)如果d(Q,S_v)≤r,那么根结点中的S_v就是结果集。
(3)如果d(Q,S_v)+r≥M,那么递归查找当前结点的右子树。
(4)如果d(Q,S_v)-r≤M,那么递归查找当前结点的左子树。
注意,如果条件(3)和(4)都满足,那么当前结点的两个左、右分支都要被查找。
2. M-树
为了克服静态索引结构的缺点,P.Ciaccia等提出了一种动态的基于度量空间的索引结构M-树(M-tree),它很好地解决了数据更新频繁的问题,当向数据库中添加或删除媒体对象时,不需要进行索引的重构。
同VP-树相比,M-树是一种全新的索引结构。它是一种分页的平衡树结构,采用自底向上的建树方法,引入对象提升和分裂机制,实现了索引结构的动态变化,从而避免了数据库更新过程中对索引进行定期更新的繁琐工作。它在进行查询时,充分采用三角不等式的过滤机制,大大减少了查询时的距离计算次数。
M-树中的对象分为两类:数据库对象和路径对象。叶子结点保存所有的数据库对象,而内部结点保存所有的路径对象。路径对象是通过特定的结点提升算法获得的。
M-树中包含两类结点: 叶子结点和非叶子结点(中间结点)。非叶子结点的结构为:L(O_r,ptr(T(O_r)),r(O_r),d(O_r,P(O_r)),其中O_r是路径对象的特征值;ptr(T(O_r))是一个指向子树T(O_r)根结点的指针,其中的T(O_r)称为O_r的覆盖树; r(O_r)是O_r的覆盖半径;d(O_r,P(O_r))是O_r到它父结点中心的距离。叶子结点的结构为: R(O_j,oid(O_j),d(O_j,P(O_j)),其中O_j是数据库对象的特征值; oid(O_j)是对象标识符,它指向数据库对象;d(O_j,P(O_j))是O_j到它父结点中心的距离。
M-树结构有如下特点:
(1)根结点如果不是叶子结点,则至少有两条记录。除了根结点以外的每个结点中记录的最小数目由结点的最低空间利用率决定,而结点中记录的最大个数受到外存页面大小的限制。
(2)子空间之间存在交叉重叠现象。
M-树第一次考虑了距离计算的复杂性,实现了范围查询。并在范围查询的基础上,采用启发式规则,实现了近邻查询。当M-树进行范围查询时,首先从根结点出发,递归遍历所有没能被滤掉的路径,直到叶子结点。在中间结点,通过三角不等式运算,不经过任何距离计算,就可能将一些子树过滤掉。在M-树的最近邻查询中,同样使用了三角不等式的过滤作用,同时利用了启发式机制,利用优先队列和结果数组的更新来控制有效子树的选择和查询的进程。