时间：2022-12-20 20:30:01 | 来源：信息时代
时间：2022-12-20 20:30:01 来源：信息时代
多维索引 : 为方便查找多维空间数据而构造的基于属性特征的数据结构。多媒体数据是多维空间中的点,每个点有若干属性,每个属性是一维。多媒体数据所需要支持的查询种类包括: 部分属性匹配、各属性值分别满足所规定范围的查询、最相似查询和包含给定媒体数据的区域或区域集的查询。如果按照传统的方法为多媒体数据建立一维索引,执行查询操作,理论和实践都证明,不仅性能达不到要求,开销也极其昂贵。因此,必须对多媒体数据建立多维索引。目前,支持多维索引的方法主要有三大类:类散列表、类树和位图。
1. 类散列表
(1)网格: 首先由J. Nievergelt等人于1984年提出。网格是比一维索引性能要好,且最为简单的数据结构之一。网格的每一维网格线把空间分成条状,不同维的网格线的数目可以不同,同一维的线之间可以有不同的距离。网格空间的每一个子空间可以被看成是散列表的一个桶,落入子空间的每个点的记录都存放在属于该空间的块中。如有必要,可以使用溢出块来增加子空间的体积。在多媒体数据分布得相当均匀的情况下,使用网格法进行范围查询、部分匹配和相似查询可以获得较好的性能。
(2)分段散列:1976年由W.A. Burkhard和R.L.Rivest分别提出。分段散列法构造散列函数,使分别散列数据的m个属性得到的m个二进制位拼接成n位的二进制数,而拼接的结果就是该多媒体数据所在的桶号。通常,即使数据分布不均匀,分段散列法用于部分匹配也可以取得较好的效果。
2.类树
(1) 多键索引: 是建立索引的索引,即,一棵树的每一层结点都是一个属性的索引。这种简单的类属方法对于范围查询和最邻近查询较有用,但对部分匹配,其性能较差,且开销较大。
(2) Kd树: 一种二叉树,又叫k维搜索树,是1975年J.L.Bentley提出的。Kd树的内部结点只有属性、划分左右子女的属性值、指向左右子女的指针; 树的不同层的属性不同; 叶结点中存放着尽可能多的纪录。Kd树可以较好地支持部分匹配、范围查询和最临近查询。不过,由于中间结点存放的信息少,如果每个结点占用一个存储块,那么,不仅浪费空间,并且遍历一条路经所需的I/O多于B树。通过将多个内结点压缩到一个存储块内和将内结点设计成具有多分支,就可以有效地提高性能。
(3) 四叉树: 于1974年由R. A. Finke和J. L.Bentley第一次提出。四叉树的每个内结点对应于n维空间的n方体。通常,一个n维的四叉树有2n个子结点,所以,在维数高的情况下可以只保留非空指针和关联的非空象限标示以节省空间。四叉树可以用于部分匹配、范围查询和最临近查询。
(4) R树: 首先于1984年由A.Guttman提出,并分别由T. K. Sellis等人和N. Beeckmann等人于1987年和1990年进行了扩展。R树表示多维区域组成的数据区,它的内结点对应于其中的某个子区域,并用子区域替代键表示子结点的内容。子区域之间可以有重叠,当然,重叠要尽可能小; 所有的子区域不一定覆盖整个数据区,但是都完全包含在数据区内。R树适用于查找指定数据所在的位置,如果子区域都是点,也可以用于部分匹配、范围查询和最临近查询。
3.位图法
Glaser创立的Nucleus公司申请了位图索引的专利,并开发了一个数据库管理系统,在该系统中位图索引既是索引结构又是数据表示。最早商业应用是1970年美国计算机公司(computer corporation of America,CCA)上市的数据库管理系统“Model204”,用于加快查询的处理过程。位图索引的思想是由P.O’Neil于1987年第一次公开介绍,并于1997年进行了改进。Oracle公司于2001年申请了相关专利: 在类B+-树结构中支持位图索引。位图索引最简单的形式是,每个属性的位图索引是长度为n(多媒体数据总数)的位向量的集合。每一个位向量对应于属性可能出现的每一个值。如果第i个数据的某属性值为v,那么对应于值v的位向量在位置i上的取值为1,否则该向量的位置i上的取值为0。在实际问题中,位向量中会有许多取值为0的位,为了节省位图索引空间,可以通过采用游程长度编码来对位图索引进行压缩。位图索引能够支持部分匹配、范围查询、最临近查询。
在线咨询
