空间数据的物理组织优秀课件.ppt

《空间数据的物理组织优秀课件.ppt》由会员分享，可在线阅读，更多相关《空间数据的物理组织优秀课件.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、空间数据的物理组织第1页，本讲稿共25页一、文件组织的基本概念1、操作系统的文件管理 文件系统把有关数据组织成为文件并予以命名。2、逻辑记录与物理记录 数据块是数据物理组织的重要概念，为了简化软、硬件的复杂性，同一系统中的数据块一般均包含相等个数的字节。（1）定长记录固定组块（2）变长记录不跨界组块（3）变长记录跨界组块（4）块列第2页，本讲稿共25页3、地址与指针（1）绝对地址（2）相对地址（3）符号地址 指针就是链接对象的地址。4、分页与系统缓冲区 为了使文件组织独立于具体的物理设备，通常采用分页技术，即把内、外存空间按同样大小分成若干页面。系统缓冲区是主存中特别指定的一块存储空间，以存放

2、从外存读入内存的数据或从内存写进外存的数据。缓冲区管理，就是将缓冲区分成若干块，系统用一个程序分配这些缓冲块，并采用分配算法使缓冲区的利用为最佳。第3页，本讲稿共25页5、文件组织 所谓文件组织，就是按一定的逻辑结构把有关联的数据记录组织成为文件（称为逻辑文件），并用体现这种逻辑结构的物理存储形式把文件中的数据存放到某种存储设备上，使之构成物理文件的机构。（1）文件存储空间利用率 文件包含的数据信息量（折合成字节数）与文件占用的整个存储空间（字节数）的比值。（2）操作的时间耗费 这是文件组织中性能量度的一个重要方面。第4页，本讲稿共25页（3）文件的重新组织 系统周期性地把文件中现存的记录按原

3、来的或新的组织方法和内部结构重新组织起来。6、动态存储管理 存储管理不是研究某种数据结构，而是研究数据结构的空间分配、回收的方法，以满足某种结构对存储的不同要求。解决存储管理的途径一般有三条：由用户解决，由系统解决，由系统和用户共同解决。第5页，本讲稿共25页二、流水文件 它是一种最简单的文件组织方法，即按照数据到达文件的时间顺序依次连续地存储数据，对数据不分析、不规范，记录的类型既可相同，也可不同。在记录类型不相同时，流水文件的记录必须由相关的数据项组成。流水文件中查找记录、插入记录，修改操作过程。流水文件主要用作数据库的日志文件。第6页，本讲稿共25页三、顺序文件1、如何确定关键字值的顺序

4、2、顺序文件的存储组织（1）向量结构（2）链结构（3）块链结构3、顺序文件的查找（1）顺序扫描（2）分块查找（3）折半查找（4）探查4、顺序文件的维护第7页，本讲稿共25页四、索引文件 以英汉词典为例，词典本身是一个顺序文件，其结构是向量的，主关键字是英文单词，记录是英文单词及其解释。若将每页的最后一个单词与页号列表，那么查单词可先查表（称为索引表），等确定页面号后，再细查该页面。这就是索引文件的基本思想。组织索引表（简称索引）是索引文件的关键。第8页，本讲稿共25页1、索引顺序文件 2、索引无序文件3、B树 4、B树5、Hash文件第9页，本讲稿共25页索引顺序文件索引顺序文件 第10页，本

5、讲稿共25页索引顺序文件的索引机制第11页，本讲稿共25页 传统的索引方法不能对地理数据进行有效的索引，尤其是多维性方面。空间索引是对存储在介质上的数据位置信息的描述，是建立逻辑记录与物理记录之间的对应关系的桥梁，用来提高系统对数据获取的效率。1、概述 空间数据索引是指依据空间对象的位置和形状或空间对象之间的某种空间关系，按一定顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。五、空间数据索引第12页，本讲稿共25页 空间索引性能的优劣直接影响空间数据库和地理信息系统的整体性能，它是空间数据库和地理信息系统的一项关键技术。空间索引一般是自顶向下

6、、逐级划分空间的各种数据结构。对一些非常自然地处理区域数据，应用最广泛的是R树，已经可以在商用的DBMS中看到R树索引。第13页，本讲稿共25页（1）基本概念空间索引：依据空间对象所在位置及分布特征，按一定 顺序编排的一种数据结构，且该数据结构包含 有对象标识和定位这些对象的内容的信息。空间检索:给定查询条件，利用空间索引从数据库中找出 符合条件的空间数据的一种操作。点、线、面 检索。（2）空间索引的分类 从数据库索引结构的实现方法 静态索引、动态索引第14页，本讲稿共25页空间检索 空间实体间的关系检索空间实体间的关系检索 面与面面与面 线与线线与线 点与点点与点 线与点线与点 面与线面与线

7、 面与点面与点第15页，本讲稿共25页 从空间索引技术上 对象影射技术、对象复制和裁剪技术、重叠子空间方法。按空间数据对象 a 基于点对象的索引方法 b 基于面对象的索引方法 按照数据的存储介质 a 基于外存的索引 b 基于主存的索引 c 基于数据库的索引第16页，本讲稿共25页（3）基于外存的空间索引 BSP树第17页，本讲稿共25页 K-D树 R树第18页，本讲稿共25页 CELL树第19页，本讲稿共25页（4）基于主存的空间索引 面向主存的空间索引是主存空间数据库的一个重要组成部分。主存网格空间索引 它是一种相对简单的主存空间索引。主存F树空间索引 自顶向下逐级划分空间（5）基于数据库的

8、空间索引 索引实质不同 基于数据库的索引，实质上是基于数据库的SQL语言优化，通过适当的表结构设计，表索引设计，以及SQL查询的设计，达到对空间数据的快速检索。第20页，本讲稿共25页 基于数据库的空间索引的特点 a 无须对原始数据进行结构调整 b 通用性强 c 在一定程度降低了索引设计的复杂度 d 在某些方面又增加了索引设计的复杂度索引方法索引方法索引实质索引实质特点特点基于文件的索引优化I/O用结构适应算法基于内存的索引优化CPU计算量用结构适应算法基于数据库的索引既要优化I/O，又要优化CPU计算量，实质上是基于数据库的SQL语言优化用算法适应结构不同索引方法比较第21页，本讲稿共25页

9、2、空间索引与B树索引 空间索引利用了某种空间联系来组织数据项，数据项的码值可以看成是k维空间中的一个点，这里k是在索引中搜索码的字段的个数。在B树索引中，二维空间域中的点是全排序的。相对而言，空间索引是基于临近度（在底层的二维空间中）来存储数据项的。第22页，本讲稿共25页3、空间填充曲线的索引（1）空间填充曲线（2）Z-排序的四叉树表示（3）Z-排序的空间查询4、网格文件 网格空间索引基本思想是将研究区域用横竖线条划分大致相等和不等的网格，记录每一个网格所包含的空间实体。网格文件在给定的数据集中以反映数据分布的方式将数据空间进行划分。它依赖于网格目录识别出包含所需要的点的数据页。网格文件不是存储区域数据的好结构。第23页，本讲稿共25页5、点和区域的R树索引方法（1）查询（2）插入和删除操作第24页，本讲稿共25页思考题1 1、什么是、什么是R R树空间索引？它包括哪些索引方式？树空间索引？它包括哪些索引方式？2 2、四叉树索引的概念、四叉树索引的概念3 3、依赖性实体的概念。、依赖性实体的概念。4 4、索引文件的关键是什么？、索引文件的关键是什么？5 5、主要的数据索引方式有哪些？、主要的数据索引方式有哪些？第25页，本讲稿共25页