空间数据的物理组织

空间数据的物理组织第1页，课件共25页，创作于2023年2月一、文件组织的基本概念1、操作系统的文件管理文件系统把有关数据组织成为文件并予以命名。2、逻辑记录与物理记录数据块是数据物理组织的重要概念，为了简化软、硬件的复杂性，同一系统中的数据块一般均包含相等个数的字节。（1）定长记录固定组块（2）变长记录不跨界组块（3）变长记录跨界组块（4）块列第2页，课件共25页，创作于2023年2月3、地址与指针（1）绝对地址（2）相对地址（3）符号地址指针就是链接对象的地址。4、分页与系统缓冲区为了使文件组织独立于具体的物理设备，通常采用分页技术，即把内、外存空间按同样大小分成若干页面。系统缓冲区是主存中特别指定的一块存储空间，以存放从外存读入内存的数据或从内存写进外存的数据。缓冲区管理，就是将缓冲区分成若干块，系统用一个程序分配这些缓冲块，并采用分配算法使缓冲区的利用为最佳。第3页，课件共25页，创作于2023年2月5、文件组织所谓文件组织，就是按一定的逻辑结构把有关联的数据记录组织成为文件（称为逻辑文件），并用体现这种逻辑结构的物理存储形式把文件中的数据存放到某种存储设备上，使之构成物理文件的机构。（1）文件存储空间利用率文件包含的数据信息量（折合成字节数）与文件占用的整个存储空间（字节数）的比值。（2）操作的时间耗费这是文件组织中性能量度的一个重要方面。第4页，课件共25页，创作于2023年2月（3）文件的重新组织系统周期性地把文件中现存的记录按原来的或新的组织方法和内部结构重新组织起来。6、动态存储管理存储管理不是研究某种数据结构，而是研究数据结构的空间分配、回收的方法，以满足某种结构对存储的不同要求。解决存储管理的途径一般有三条：由用户解决，由系统解决，由系统和用户共同解决。第5页，课件共25页，创作于2023年2月二、流水文件

它是一种最简单的文件组织方法，即按照数据到达文件的时间顺序依次连续地存储数据，对数据不分析、不规范，记录的类型既可相同，也可不同。在记录类型不相同时，流水文件的记录必须由相关的数据项组成。流水文件中查找记录、插入记录，修改操作过程。流水文件主要用作数据库的日志文件。第6页，课件共25页，创作于2023年2月三、顺序文件1、如何确定关键字值的顺序2、顺序文件的存储组织（1）向量结构（2）链结构（3）块链结构3、顺序文件的查找（1）顺序扫描（2）分块查找（3）折半查找（4）探查4、顺序文件的维护第7页，课件共25页，创作于2023年2月四、索引文件

以英汉词典为例，词典本身是一个顺序文件，其结构是向量的，主关键字是英文单词，记录是英文单词及其解释。若将每页的最后一个单词与页号列表，那么查单词可先查表（称为索引表），等确定页面号后，再细查该页面。这就是索引文件的基本思想。组织索引表（简称索引）是索引文件的关键。第8页，课件共25页，创作于2023年2月1、索引顺序文件2、索引无序文件3、B－树4、B＋树5、Hash文件第9页，课件共25页，创作于2023年2月索引顺序文件第10页，课件共25页，创作于2023年2月索引顺序文件的索引机制第11页，课件共25页，创作于2023年2月

传统的索引方法不能对地理数据进行有效的索引，尤其是多维性方面。空间索引是对存储在介质上的数据位置信息的描述，是建立逻辑记录与物理记录之间的对应关系的桥梁，用来提高系统对数据获取的效率。1、概述空间数据索引是指依据空间对象的位置和形状或空间对象之间的某种空间关系，按一定顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。五、空间数据索引第12页，课件共25页，创作于2023年2月

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

面与线面与点第15页，课件共25页，创作于2023年2月②从空间索引技术上对象影射技术、对象复制和裁剪技术、重叠子空间方法。③按空间数据对象

a基于点对象的索引方法

b基于面对象的索引方法④按照数据的存储介质

a基于外存的索引

b基于主存的索引

c基于数据库的索引第16页，课件共25页，创作于2023年2月（3）基于外存的空间索引①

BSP－树第17页，课件共25页，创作于2023年2月②K-D树③

R－树第18页，课件共25页，创作于2023年2月④CELL树第19页，课件共25页，创作于2023年2月（4）基于主存的空间索引面向主存的空间索引是主存空间数据库的一个重要组成部分。①主存网格空间索引它是一种相对简单的主存空间索引。②主存F－树空间索引自顶向下逐级划分空间（5）基于数据库的空间索引①索引实质不同基于数据库的索引，实质上是基于数据库的SQL语言优化，通过适当的表结构设计，表索引设计，以及SQL查询的设计，达到对空间数据的快速检索。第20页，课件共25页，创作于2023年2月②基于数据库的空间索引的特点

a无须对原始数据进行结构调整

b通用性强

c在一定程度降低了索引设计的复杂度

d在某些方面又增加了索引设计的复杂度索引方法索引实质特点基于文件的索引优化I/O用结构适应算法基于内存的索引优化CPU计算量用结构适应算法基于数据库的索引既要优化I/O，又要优化CPU计算量，实质上是基于数据库的SQL语言优化用算法适应结构不同索引方法比较第21页，课件共25页，创作于2023年2月2、空间索引与B＋树索引空间索引利用了某种空间联系来组织数据项，数据项的码值可以看成是k维空间中的一个点，这里k是在索引中搜索码的字段的个数。在B＋树索引中，二维空间域中的点是全排序的。相对而言，空间索引是基于临近度（在底层的二维空间中）来存储数据项的。第22页，课件共25页，创作于2023年2月3、空间填充曲线的索引（1）空间填充曲线（2）Z-排序的四叉树表示（3）Z-排序的空间查询4、网格文件网格空间索引基本思想是将研究区域用横竖线条划分大致相等和不等的网格，记录每一个网格所包含的空间实体。网格文件在给定的数据集中以反映数据分布的方式将数据空间进行划分。它依赖于网格目录识别出包含所需要的点的数据页。网格文件不是存储区域数据的好结构。第2