空间存储和索引.ppt

第章空间存储和索引
第一页，共46页
本章要了解的几个问题
数据库的索引可以用来快速访问一条特定查询所请求的数据，无需遍历整个数据库。一般都用高级逻辑语言书写的。
空间存储结构的目标是方便空间选取和连接查询。
物理数据库设计目标就是让数据传输量保持为一个绝对最小值。
空间查询过程的基本思想就是对近似的使用。使用近似可以产生一种用于过滤和精炼查询过程的策略。可以让索引结构按照一个或多个空间码来管理对象，这些空间码是比对象本身更简单的几何对象。
第二页，共46页
近似能解决的与空间索引相关的操作
近似这样的结构提供了插入，删除和成员查询等操作，用于管理空间类型的集合。可支持一个或多个查询操作。对于所存储的矩形和点，有一些重要操作：
点查询：找出所有包含给定点的矩形
范围查询：找出所有位于给定矩形中的点
最近邻居：找出距查询点最近的点
距离扫描：按与给定点距离的增序列出所有点
相交查询：找出所有与给定矩形相交的矩形
包含查询：找出所有完全包含在给定矩形中的矩形
空间连接查询：找出所有相互交叠的矩形对
目录
第三页，共46页
：磁盘和文件
CPU访问主存的速度是非常快的（纳秒级）。
对二级存储的访问速度相对来说很慢（微秒级），一个严重的瓶颈 。
对于空间数据库来说，更加复杂：
空间应用涉及的函数其计算复杂性与程序设计语言的应用程序不相上下。
空间数据库的存储需求一般来说要比传统数据库更高。
数据可能会溢出到三级存储中。
第四页，共46页
磁盘的几何结构和含义
基本名词：磁道 柱面 扇区 磁盘块
从磁盘读取数据到主存，整个过程可以分为三步，每一步都有一个特征时间：
寻道时间（ts）
延迟时间（tl）
传输时间（tt）
全部存取时间（ta）计算：ta=ts+tl+tt
且通常满足下面不等式：ts>tl>tt
第五页，共46页
缓冲区管理器
缓冲区管理器是DBMS中一个软件模块，专门负责管理主存与二级存储之间的数据传输，确保事务不会因为一部分数据不在主存中而停顿下来。
置换策略是缓冲区管理器所实施的协议。如最近最少使用（LRU）算法
频繁访问集一组被频繁访问的页面。
第六页，共46页
DBMIN算法
DBMIN算法是以查询本地集模型（QLSM）为基础的。将数据库操作的引用模式特征化为顺序引用、随机引用和分层引用。
和一个文件实例关联的缓冲页面集合被看作是它的本地集（local set） ，有一个全局页表和全局空闲链表来管理。
如果在本地集和全局页表中找到了所请求的页面，有找到这一页就直接返回这一页，同时更新该页的使用情况统计信息。
如果没，则把该页读入本地集合（一个空页）中。
如果没有可用的空页（例如，本地集的大小超过了最大阀值），就要根据本地集所指定的页面置换规则，替换一个已经存在的页面。
第七页，共46页
域、记录和文件
基本名词：
文件
记录
域
第八页，共46页
二进制大对象（BLOB）域类型
二进制大对象（BLOB）域类型在空间数据库的发
展中起了重要作用。BLOB的缺点：
BLOB域在技术上还不能算作一种数据类型；
RDBMS将一个BLOB视作没有任何结构的无格式数据；
BLOB域上没有可用的查询操作。
第九页，共46页
文件结构
文件结构指文件中记录的组织形式。

最简单的组织形式，记录没有特定的顺序。
缺点:根据给定的关键码查找一条记录需要扫描文件中的记录。
优点：是在进行插入操作时可以很容易地在文件末尾插入一条新记录。
第十页，共46页