第五讲 多维索引　.ppt

第五讲 多维索引;主要内容;多维索引的应用;地理信息系统(GIS) 用一个（通常是）两维的空间存储对象，对象可能是点或形状（房子、路、桥、管道等）。;数据立方体;应支持4类查询;SQL多维查询;范围查询 ;使用传统索引执行范围查询(P139) 传统索引（如B树）对执行范围查询帮助不大； 利用传统索引执行最近邻查询（P140) 传统索引的其他限制 两类多维索引： 类散列表方法； 类树方法． ;多维数据的类散列结构;网格文件;;网格文件的查找;;网格文件的插入;选择1的缺陷：因为它没有分裂其它桶，却给我们留下了更多的空桶，且没有减少 任何被占用的桶的大小．2),3)相当．如果选择2,如下图;;网格文件的性能 缺陷：高维情况下，桶的数目会随维数目呈指指数级增长．可能还会有大量空桶； ;分段散列函数（Ｐ１４７）;;网格和分段散列的比较;多维数据的类树结构;多键索引;例如对金首饰”建立多键索引,第一???属性为年龄,第二个属性为薪水.关于年龄建立根索引.可根据根索引找到与某一年龄相关的关联指针. 以根据与年龄50相关的4个薪水值(75,100,120,275)其指针指向相关记录.;多键索引的性能 部分匹配查询 如果第一个属性被指定,那么访问是很有效的.使用根索引找到一个子索引,该子索引指向数据点.如果第一个属性没有给出一个指定值,必须有哪些信誉好的足球投注网站每一个子索引,这种情况是潜在、耗时的处理过程。 范围查询 最近邻查询;KD树;;Kd树的操作 插入新值 ;;;;四叉树;R树;;R树的操作 ‘where –am-I’查询,指定一个点P且询问该点所处的数据区域;;插入新的区域;;位图索引;位图查找 部分匹配 ;范围查找;主要内容