《高技术索引详解讲述》由会员分享，可在线阅读，更多相关《高技术索引详解讲述（84页珍藏版）》请在金锄头文库上搜索。
1、主要内容,ECUST-Jing Zhang,1,高维数据索引结构 高维数据索引结构的概念 树形索引结构 R-tree - SR-tree -SS-tree A-tree - X-tree R*-tree - k-d-tree VA-File类索引结构 基于降维的索引方法 基于聚类的索引方法 R树类索引结构上实现最近邻查询的方法 多维索引方法的演变,索引结构,ECUST-Jing Zhang,2,关于“索引” 索引的主要用途是查找数据。利用索引可以有效地管理大量的数据，并快速的从这些数据中查找到特定的数据。 影响查询效率的关键因素是磁盘的I/O次数，利用索引技术可以有效的减少I/O次数 传统数据
2、库的索引结构： B树:键值一维排序，不能搜索多维空间 哈希表：数值精确匹配，不能进行范围查询,ECUST-Jing Zhang,3,一个简单的B树,一个B树的简单的例子： 数据 24，33，16，2，7，20，22，3，5，27， 39，34，38，14，29，19 每四个数据占用一个磁盘页 16个数据占用了四个磁盘页 查找数据28 需要四次I/O操作,刚才的数据生成的B树,ECUST-Jing Zhang,4,首先，将根结点读入内存,将该叶子结点读入内存,共需要两次I/O操作,28,索引结构的本质：空间换时间,ECUST-Jing Zhang,5,划分和有序组织数据 | 减少不必要磁盘访问
3、| 节省查询时间,高维数据,ECUST-Jing Zhang,6,什么是高维数据？ 高维数据就是高维空间的数据 图形数据库中的数据 两维空间中的点、线、矩形 三维空间中的点、立方体、球 应用领域如：CAD , 医学 多媒体数据库中的特征矢量 高维空间的点数据 应用领域如：图象检索,高维数据的特点,ECUST-Jing Zhang,7,一维数据索引结构无法适用于高维数据 高维数据的特点： 具有复杂的结构：有可能是高维空间的一个点，也有可能是复杂的图形 无法对高维数据排序：即不能找到一个合适的方法，使得在高维空间相近的数据在排序后仍然相近,高维数据索引结构的发展,ECUST-Jing Zhang,
4、8,70年代随着在CAD中处理大量的图形数据而出现的。 近年来应用领域越来越广泛，尤其在多媒体数据库方面。 30多年来，人们提出了近百种高维数据索引结构。,高维索引结构的一种简单分类,ECUST-Jing Zhang,9,树形的高维索引结构 R-tree及其变种，kd-tree，Quad-tree, GC-Tree等 基于近似的索引结构 VA-File, LPC-File, CVA-File, VA+-File等 基于降维的索引方法 Pyramid-Technique ，iMinMax() ，iDistance 等 基于聚类的索引方法 Clindex，VQ-Index 等 等等,高维数据的查询
5、方法,ECUST-Jing Zhang,10,查询类型 点查询 特征矢量，精确匹配 范围查询 特征矢量，查询范围 K近邻查询 特征矢量，整数k 不同高维索引结构对应不同的查询方法，有些索引结构可支持以上三种不同类型的查询，有些只支持其中一种或两种查询方法,R树类索引结构,ECUST-Jing Zhang,11,R-tree,ECUST-Jing Zhang,12,1984年由Guttman提出 是B-tree树在高维数据空间的扩展 是一种高度平衡树 用原始数据的最小边界矩形表示数据 其插入、删除、更新操作都类似于B-tree树 能够有效支持的数据的维数：20维以下 可以进行点查询和范围查询,R
6、-tree,ECUST-Jing Zhang,13,表示数据的方法 由于高维数据类型复杂，无法在索引结构中直接表示原始数据，在R-tree中用原始数据的最小外接矩形（MBR: Minimal Bounding Rectangle)来表示数据。,R-tree,ECUST-Jing Zhang,14,R-tree结构的特点： M表示节点中可存放项的数目的最大值，m（m=M/2)表示最小值，则一个节点中必须包含mM个项，根节点除外。 根节点至少包含两个项，除非它是叶子节点 所有的叶子节点在同一层上,一个R树的例子,ECUST-Jing Zhang,15,名称：内部结点 索引结点 目录结点 特点：不包
7、含实 际的数。,名称：叶子结点 特征：包含实际数据或者指向实际数据的指针,D,F,E,G,H,K,J,I,N,M,L,A,B,C,A B C,D E F G,H I J K,L M N,ECUST-Jing Zhang,16,D,F,E,G,H,K,J,I,N,M,L,A,B,C,A B C,D E F G,H I J K,L M N,从根节点开始，对所有内部节点，查找所有与q相交的项所指向的子节点；到达叶子节点后，输出所有与q相交的数据。,查询定义：对于给定的查询区域q, 查询所有与q相交的数据。,ECUST-Jing Zhang,17,影响查询效率的主要因素：,1、重叠区域 （ Overl
8、ap ）：导致查询时遍历多个路径 2、死空间 （dead space)：导致查询时遍历不必要的路径,为了提高查询效率，在构建R-tree的时候要尽量减少重叠区域和死空间的面积,ECUST-Jing Zhang,18,D,F,E,G,H,K,J,I,N,M,L,A,B,C,A B C,D E F G,H I J K,L M N,1：向R-tree中插入一个数据，首先从根节点出发，在所经过的所有内部节点中选择这样的项：它所指向的子节点为了容纳下该数据面积需要扩大的最小;如出现相同的情况，则选择面积较小的那个。,O,2：到达叶子节点后，如节点中仍有剩余的空间，则将数据插入，然后依次修改祖先节点中的相
9、应项的数据。,O,ECUST-Jing Zhang,19,D,F,E,G,H,K,J,I,N,M,L,A,B,C,A B C,D E F G,H I J K,L M N,O,O,3：如果叶子节点中已经没有足够的空间，则要进行分裂操作，并产生一个新的项，插入到其父节点中,P,P,Q,ECUST-Jing Zhang,20,D,F,E,G,H,K,J,I,N,M,L,A,B,C,A Q B C,D E F,H I J K,L M N,O,O,P,Q,G P,R,D E F G,+ P,D E F,+,G P,1:,2: 生成一个新的项Q，插入到父节点中,ECUST-Jing Zhang,21,H
10、I J K,+ R,H I J,+,R K,1:,2: 生成一个新的项S，插入到父节点中,3: 由于此时根节点已经没有剩余的空间，根节点要发生分裂,4：,A Q B C,+ S,A C,+,B Q S,ECUST-Jing Zhang,22,D,F,E,G,H,K,J,I,N,M,L,A,S,C,A C,D E F,H I J K,O,P,Q,N M O L,R,B,T,U,U T,B S Q,H I J,G P,ECUST-Jing Zhang,23,D,F,E,G,H,K,J,I,N,M,L,A,B,C,A B C,D E F G,H I J K,L M N,1：从R-tree中删除一个数
11、据，首先要进行一次精确匹配查询，查找在R-tree中是否存在该数据，如不存在，删除失败；如存在，则从叶子节点中删除该数据,2：如删除后节点中仍有足够多的项，则依次修改祖先节点中的数据，删除结束； 如节点中已经没有足够多的项，则将该节点从树中删除，并将节点中的所有项重新插入到树中。,ECUST-Jing Zhang,24,分裂算法,决定是否对子节点进行查询访问，要根据查询区域是否与子节点的MBR相交来决定,分裂算法希望能使以后的查询操作中，尽量少的对分裂后的两个子节点同时进行查询。,分裂算法的原则：分裂之后使两个子节点所覆盖的区域面积之和尽量的小。,ECUST-Jing Zhang,25,第一种
12、分裂算法：穷尽组合法,对每一种分裂的可能情况都进行一次计算，从中选择最好的一种做为分裂结果。 优点：分裂效果好 缺点：时间代价过大,ECUST-Jing Zhang,26,第二种分裂算法：二次花费算法,1、从要分裂的节点中首先选择两个数据，作为分裂后的新节点的种子；,D,F,E,G,A,P,原则：其最小外接矩形面积最大的两个。,2、依次从剩余的数据选择这样的项：两个新节点为了容纳下该项，需要扩大的面积之差最大。 然后将该数据放入面积需要扩大较小的节点中。,D,G,D,G,P,D,G,P,ECUST-Jing Zhang,27,3、如其中一个新节点中所包含的数据太少，使得需要把所有剩余的放入才能
13、达到节点规定的最小项的数目，则将剩余的所有数据放入该节点。,D,F,E,G,P,D,F,E,G,P,R-tree,ECUST-Jing Zhang,28,R-tree算法主要存在以下缺陷： 内部节点存在重叠现象，由于节点间数据的相互重叠，在进行查询的时候，可能要遍历多条路径，查找多个叶子节点，最坏的情况下，要遍历所有的路径。 R-tree只对20维以下的数据较为有效，当维数逐渐增大的时候，内部节点中的重叠现象迅速恶化，导致查询性能急剧下降，使索引变的毫无意义，也就是通常所说的“维数灾难”。,R-tree的变种,ECUST-Jing Zhang,29,为了能够减少内部节点之间的重叠问题，在R-t
14、ree的基础上又相继提出了以下一些索引结构： R+ -tree R* -tree X -tree SS-tree SR-tree A-tree,R+-tree,ECUST-Jing Zhang,30,采用R-tree一样的结构 与R-tree的不同之处 采用了clipping的方法，即一个数据可以被分割开来，同时存放在几个不同的叶子节点中。解决了R-tree中内部节点重叠的问题。 不要求节点内必须包含大于等于最大节点的一半的数据。 叶子节点可能重复。 R+-tree比R-tree具有更好的查找性能（特别是对点查询），但是比R-tree占据更多的存储空间 支持点查询和范围查询,ECUST-Jin
15、g Zhang,31,D,F,E,G,H,K,J,I,N,M,L,A,B,C,D,F,E,G,H,K,J,I,N,M,L,A,B,C,P,ECUST-Jing Zhang,32,A B C P,D E F G,I J K,L M N,G H,节点之间没有了重叠，因此可以在查询的时候提高效率。,R+-tree,ECUST-Jing Zhang,33,R+-tree存在的问题 插入的时候可能向几个叶子节点中插入数据 在内部节点分裂的时候，不仅要考虑分裂对祖先节点的影响，还要考虑对孩子节点的影响，复杂度远远大于R-tree。 当维数较高，数据较为密集的时候，R+-tree的效率远比想象中差的多。,R*-tree,ECUST-Jing Zhang,34,R*-tree采用了R-tree一样的结构 R*-tree对R-tree的改进 引入强制重新插入机制对R-Tree的性能进行改进 在选择插入路径时同时考虑矩形的面积
