空间数据结构是指空间数据的编排方式和组织关系。空间数据编码是指空间数据结构的具体实现，是将图形数据、影像数据、统计数据等资料按一定的数据结构转换为适合计算机存储和处理的形式。不同数据源采用不同的数据结构处理，内容相差极大，计算机处理数据的效率很大程度取决于数据结构。

空间数据结构是带有结构的空间数据单元的集合。这些数据单元是数据的基本单位, 一个数据单元可以由几个数据项组成, 数据单元之间存在某种联系叫做结构。所以, 研究空间数据结构, 是指研究空间目标间的相关关系, 包括几何和非几何的关系。数据结构是数据模型的表述, 数据结构往往通过一系列的图表和矩阵, 以及计算机码的数据记录来说明。

随着多维数据在计算机应用方面的数量的增长，空间数据管理的研究成了当前的热点。空间数据(多维数据)包括：点、线段、区域，三维或更高维中的多面体。严格来讲，空间数据库包含带有对象的外在知识、对象的扩展以及对象在空间的位置等多维数据。这些对象是用矢量格式进行描述的。空间数据被视为一种特殊的数据，它们具有要求用非标准数据库管理方法的几个特点：

①空间对象结构的复杂性。比如一个简单的点或一组任意分布的多边形，都是空间数据对象。有固定长度的关联数据库元组不适合存储这样的数据格式。

②空间数据的动态性。这种特点要求数据结构能适应频繁地插入、删除以及更新对象。

⑧空间数据库不断增长。在地理地图或者VLSI电路的对象数目往往需要数千兆字节的存储空间。

④没有空间代数标准。它们通常根据特定空间数据库的应用领域来决定空间操作。

⑤空间操作不封闭。如两个空间对象的交集可能是一组点、线或区域。

⑥空间数据的多维性。该特性使传统数据库索引方法(如B树或线性散列法)不适合索引空间数据。

下面列举了一些最突出的传统空间数据结构视图：格子文件及其变形、四叉树及其变形树、k-d树及其变形树、R树及其变形树。

(1)格子文件及其变形。它是散列方法的代表，适合于存取点数据。格子文件是格子方法的变形，但其单元分割线不一定等距。其目标是最多经过两次磁盘存取获得记录并高效地处理范围查询。这是通过格子块组成的格子目录来完成的。在一个格子块里的所有记录都是存储在相同的存储桶中。只要格子块可以合并构成记录空间的k维矩形，几个格子块就可以共享一个存储桶。

图1表示了一个容量为四个数据点的数据桶的格子文件。

图1中表示了在x轴和y轴上带有比例尺的目录。为了响应符合精确匹配的查询，人们首先使用标尺来定位出包含查找点的单元。如果该格子单元不在主存中，需要一次磁盘存取，并装入有可能包含匹配数据的参考页的单元

另一个技术术语叫多重页： 多重页也是使用称为“轴向排列”的线性标尺形式的目录。然而，多重页存取一个数据及其潜在溢出链不是使用格子目录，而是使用直接从线性标尺计算得出来的地址。多重页分为动态和静态两种。在动态多重页中，设置在探测器因子上的范围控制其执行(定义为一个探测器的页存取平均数)；在静态多重页中，设置在装载因子上的范围或平均页占有控制其执行

把格子文件与多重页相比较．将会发现格子文件把多重页作为格子目录的索引来使用。因此，多重页不需要格子目录而节约了空间，但这需要以存储桶的溢出为代价 这意味着多重页能够获得平均情形时的性能，却不能保证两次磁盘存取得到记录。另外，在分离和合并存储桶时，在多重页中的插入和删除包括数据页的整个行和列(在二维情况下)．然而格子文件可以每次将一页分成几部分．并将格子目录中更多的全局操作局部化。

(2)其他散列方法一EXCELL方法是一棵通过地址计算以阵列的形式提供存取目录的二叉查找树，也可以视为从多维点数据的可扩展散列变化而来。格子文件的超平面划分带有任意性，EXCELL方法则将区域匀称分解，所有的格子单元大小相等。为了在插入操作时保持该特性，每一次新的分解使目录的大小加倍。为缓解这个问题，后来提出一种分级的方法，引进溢出页来限制分级深度

二级格子文件是另一种散列法，其基本思想是用另一个格子文件来管理格子目录。这两级中的第一级称为根目录，是第二级目录的目录根目录条目包含了更低一级的目录页的指针，该人口依次包含指向数据页的指针。有了第二级，划分常常被限制在子目录区域而没有对其他区域造成太大影响。孪生格子文件又是另一种散列法，该方法与通过引入的二级格子文件的初始格子文件相比增加了空间的利用率。这两个格子文件之间的联系不是分级而是在某种程度上有更多的点平衡。在两个文件之间的数据是动态分布的 如果在存储桶的点的数目超过了给定的限度，孪生格子文件设法重新分布在两个格子文件之间的点。点从初始文件P向第二级文件S的传递可能造成在S中的存储桶上溢 然而，也可能意味着在P中存储桶下溢，可能依次导致存储桶合并从而减少在P中的存储桶。孪生格子文件的目标是将两个格子文件P和S中的存储桶总数减到最少。

(1)树。它具有一个根节点，每个中问节点有四个孩子。四叉树的每个节点对应一个正方形。四叉树主要用于对点数据、曲线、表面以及体的表示。四叉树每一层分解成等同的部分(如规则多边形)，也可以由输入决定。分解的方案可以事先确定，或者由输入数据的特性决定。对有些应用能够区分它们是以指定区域的边界(如曲线和表面)为基础的数据结构或以组织它们的内部(如面积和体积)为基础的数据结构。

(2)四叉树的变形树。区域四叉树是最重要的表示法一个区域四叉树是基于有边界的图像阵列划分连续的四个相同大小的正方形区域(平行于轴)。如果该阵列完全地由1或0表示，那么就划分它为一个个正方形区域，直到得到的块全由1或全由0组成。四叉树的数据结构也可表示三维或更高维中图像，八又树的数据结构是四叉树在三维空间的推广。

k-d树是早期的多维数据结构，也是一棵存储k维空间点的二叉搜索树。在每一个中间节点．k-d树把k维空间分成两个k-1维超平面，即k-d树顶层节点按一维划分，下一层节点按另一维进行各个维循环往复。当一个节点中的点数少于给定的最大点数时结束划分。图2表示了二维空间中的一组点以及这些点的k-d树表示。每条线对应于树中的一个节点，叶节点的最大点数设为1。在X轴上标注深度为偶数的值(根的深度认为是0)，Y轴上标注深度为奇数的值。

三维以上的点数据更适合使用k-d树。k-d树划分超平面是由点的位置决定，而不是以最可能的位置划分平面，从而导致了该树是一棵非平衡树 自适应k-d树是改进的k-d树，在划分时选择了一个把空间分成两个拥有相同数量的点的子空间的超平面。超平面仍然与轴平行，但不包含点 树的内部节点包含维(如X或Y)，各自的坐标是分离的。所有的点都存储在叶子上 叶子可容纳的点数固定，如果超过了这个数，就要进行划分。直观上，k-d树适合静态结构，如果频繁进行插入和删除操作，很难维持其平衡。

R树是分级数据结构。R树及其变形是空间数据库应用最多的数据结构。R树是用来存储多维对象的MBB(最小的边界框)，而不是最初的空间对象。n维对象的MBB是包含初始对象的最小的n维矩形。R树与B树相似，也是平衡树，它们能确保高效地利用存储空间。MBB并不等于实际对象，故R村不能完全响应一个查询清求，除非数据库中的对象就是MBB。R村常常用来处理与查询对象的MBB相交的数据库对象的初步筛选。

每一个R树节点对应一个磁盘页和一个n维的矩形。每一个非叶子节点包含了形如(Ref，Rect)的条目，这里Ref是孩子节点的地址，Rect是孩子节点的所有条目的MBB 叶子包含了同样格式的条目，这时Ref指向数据库对象．Rect是对象的MBB。

GIS(地理信息系统)是采集、存贮、处理、分析、转换和输出空间数据的计算机系统。空间数据模型(Spatial Data Model)和空间数据结构(Spatial Data Structure)是任何地理信息系统设计的核心, 也是推动地理信息系统发展, 使之不断更新的关键。能否在空间数据结构和空间数据模型基础上建立起高效优良的空间数据库, 已经成为当前地理信息系统领域的研究热点。

层次数据结构（Hierachical Structure）即树状结构。主要表达数据元素之间的层次关系, 通常是1 对多的关系, 每层的数据与下一层中的多个数据元素相关。树状结构中只有一个根节点称为主人, 其余若干节点称为成员, 而每一个节点又同时作为下一层节点的主人，如经典的四叉树和八叉树。

在关系数据结构(Relational Structure)中, 关系表是一个二维数据, 数据单元之间是线性关系。实体的层次关系是用列来表示的。每一个数据单元只有一个直接前趋和一个直接后继。关系结构是一个二维结构, 建立的二维表称为关系表。一个实体由若干关系组成。二维表的集合就构成关系结构。

网络数据结构(Network Structure)层次结构相比, 它有多个主人, 因此, 是多对多的关系。

如图3所示。P , S , R 都是实体, 它们之间的关系用网络来联接。一个子节点可以有多个父节点。例如, 图3 中, R2 有S1 , S2 , S3 三个父节点。或者说一个成员可以有多个主人。当然, 多个主人也可以有多个人员。

超图数据结构(The Hypergraph Based DataStructure)。上述几种数据结构存在一些缺陷, 但是超图数据结构能够较好地解决诸如关系数据结构无法表达隐含关系, 缺乏完整性;树状数据结构不适合反映非等级关系;网状数据结构不适合反映非层次结构等问题。

超图的概念是图的概念的一个扩展。在图G =(V ,X)中,X 的每一个元素可以看作是V 的一个二元子集。设V ={v1 , v2 , ..., vp}是一个非空有限集, 令X ={x1 , x2 , ..., xq}是V 的q 个子集的一个组, 则称二元组H =(V , X)为一个超图。

(1)全球数据模型。随着全球的变化, 以及信息交换量日益扩大, 数据库的设计提升到了全球的角度, 迫切需要建立全球数据模型。这样的系统, 往往是:矢量数据模型用经纬度, 利用比例尺卫星影像, 以小比例尺图形分析为手段。但是因为拓扑关系不可能包括任何立体球面, 因此, 必须建立球体数据模型,最终达成全球数据库的建立。

(2)时空数据模型。

通常地理信息系统致力于发展二维数据模型, 但是, 随着遥感技术的发展, 随着数据量的复杂度增大和海量数据的出现, 时间序列变化很大, 建立时间序列数据库已经非常困难, 因此很有必要突破二维平面的限制, 建立一种全新的时空数据模型(Space TimeData Model), 或者称为四维数据模型, 来解决诸如区域的动态监测、战场信息的动态管理等问题。如何建立时空数据模型和建立怎样的时空数据模型已经成为当今GIS 领域的研究热点。