5空间存储和索引解析.ppt

第五章空间存储和索引问题的提出物理存储介质缓冲区管理存储组织存取路径:索引结构问题的提出索引的意义空间索引,也称为空间访问方法(essmethod-SAM)就是指依据空间对象的位置和形状或者空间对象之间的某种空间关系按一定的顺序排列的一种数据结构。包含空间对象的概要信息,如对象的标识、外包络矩形、及指向空间对象实体的指针。空间数据库索引技术是对存储在介质上的数据位置信息的描述,是为了快速访问一条特定查询所请求的数据,而无需遍历整个数据库。问题的提出空间索引的提出基于两个因素计算机的体系结构将存储器分为内存和外存访问两种存储器一次所花费的时间相差10万倍以上外存储器作为存储数据的主要设备,访问所花费的代价,要求对数据存储的位置和结构必须加以组织和索引。传统索引技术对空间数据库的不适应性传统索引技术只是基于一维数据之间的关系判读(大于、等于和小于),而空间数据的多维性很难判断存储器分级管理空间索引技术的研究思路目标映射思路基于传统数据库的索引机制:传统数据库的多属性可以看成多维空间上的点,因此多属性数据索引(KD-树、网格文件)可以直接用于索引空间中的点状地物。问题的提出曲线、多边形、多面体,则可以将其先映射成更高纬空间的点,再采用点状目标索引技术。目标复制思路复杂的空间几何体映射高维空间点后,几何体的空间关系发生了变化,查找效率低。于是提出了不允许索引子重叠的索引法。这种方法,将索引空间划分成许多索引子空间,索引目标属于与其相交的子空间。缺点:导致目标重复存储,增加了Insert/Delete等操作的复杂度。目标界定思路如果允许索引子重叠,则可以将空间几何体界定在某一索引子空间内,则目标的重复存储可以避免。索引子空间的重叠,必然导致多条查找路径,因此这种研究的思路重点是索引子空间重叠最小化。基本存储联机存储物理存储介质层次寄存器高速缓冲存储器主存储器快闪存储器磁盘存储器脱机存储光盘存储器磁带存储器容量速度快慢小大物理存储介质:基本存储寄存器(register)CPU的一部分,用于暂存运算中间结果与运算部件直接连接,速度最快,极少(几十个)高速缓冲存储器(cachememory)CPU的一部分,用于缓存主存储器,解决主存储器跟不上CPU读写速度要求的矛盾。在CPU中,速度极快,容量小(几十K~2M)操作系统底层管理物理存储介质:基本存储主存储器(mainmemory)-内存通过总线与CPU相连,存储运算所需的数据和指令速度很快(纳秒级),一般容量在几十M~几个G随机访问:访问任何存储单元,时间相同。易失性:断电丢失。操作系统提供机制,应用程序管理。物理存储介质:在线存储快闪存储器(flashmemory)通过外设接口与总线相连,存储永久保留的数据速度受到存储介质和接口限制随机访问,非易失性,断电不丢失文件系统管理,可以通过操作系统在线访问磁盘存储器(diskmemory)同上,但是机械装置,速度更慢物理存储介质:脱机存储光盘存储器(CDROM/CDR/CDRW/DVD)脱机存储,保存备份或者历史档案分为光物理盘,光化学盘和光磁盘只读,可写一次,可重复读写机械装置,随机访问,速度更低有标准数据记录格式,操作系统提供文件系统接口访问物理存储介质:脱机存储磁带存储器(tape)脱机存储,保存备份或者历史档案电磁记录原理机械装置,顺序访问速度最低,容量价格比最高(至几百G)