4．2 数据文件及其组织

    地理信息系统的开发和应用同文件关系十分密切，尽管数据库技术已从文件系统发展到数据库系统，但文件系统是数据库系统的基础，从数据库的内部构造看，还是文件的集合。对数据库的各种操作最终是对文件执行相应的操作。

    下面就文件的几种主要组织形式作简单的介绍。

    一、顺序文件(Sequential File)

    顺序文件是按记录进入文件的先后顺序存放的，它的逻辑顺序和物理顺序是一致的。

    顺序文件的优点是结构简单，连续存取速度快，即当存取文件中第i个记录后可以很快存取第i+1个记录；它的缺点是不便于插入、删除和修改，不便于查找某一特定记录。为了防止从头到尾查找记录，提高查找效率通常用分块查找和折半查找。

    分快查找是将整个顺序文件分成若干块，每块包含一定数目记录，并建立一个查找表，查找某个主关键字时，首先判断它在那个块中，然后进一步查找。

    折半查找是将顺序文件的记录分成两半，在查找时，先确定所找的记录在文件的前一半还是后一半，这样不断折半直到找到该记录。

    二、直接存取文件(Direct Access File)

    直接存取文件也称随机文件、散列文件或Hash文件。这种文件采用关键字变地址方法组织文件。通过建立一个Hash函数i=H(k)(k为关键字， i为地址)把关键字转换成地址，然后，把记录存贮到相应的地址中。查找记录时经同样转换方法，直接求得所查找记录地址再进行存取。实际上，其中地址常以桶(bucket)为单位，每个桶中存放一定数量的记录，桶也是一次I/O操作的基本单位。

    直接存取文件的核心是如何构建Hash函数。构建Hash函数的原则，应尽量减少关键字转换成地址时出现的冲突。所谓冲突是指不同关键字经Hash函数转换后得到了相同的地址。

    直接存取文件的优点是文件随机存放，插入删除方便，查找速度快，节省空间。

    三、索引文件(Index File)

    索引文件是指带有索引表的文件。在索引表中存放记录的关键字和记录在文件中的位置。索引表通常按主关键字有序排列，而主文件本身可按主关键字有序或无序排列，前者称索引顺序文件，后者称索引非顺序文件。

    索引文件在存贮器上分为两个区，即索引区和数据区。索引区存放索引表；数据区存放主文件。建立索引表的目的是提高查询速度。

    索引文件的查询分两步进行，首先查索引表，其次按索引表所指地址查记录。由于索引表是有序的，所以对索引表的查找可用顺序查找或折半查找。

    当数据区记录数目很大时，索引表也很大，可能会出现一个物理块容纳不下现象。为了避免查索引时多次访问外存，可以在索引表上再建立一个索引表，这表又称查找表。查找表项目很多时还可建立高一级索引，通常最高可有四级索引。下面以地理信息系统中查找弧段数据文件为例来说明索引文件的应用。表4-1(a)是弧段数据文件，每个弧段数据有标识主关键字弧段号、左多边形号、右多边形号及一批坐标点数据组成。其中各弧段的坐标点数各不相同，故该文件中记录为不定长记录。由于在地理信息系统中一张区域图往往由很多弧段组成，因此，若要查询表4-1(a)中的某一弧段，需要化费一定时间。为解决此问题，可以以关键字为主建立一索引表，如表4-1(b)所示。当需要查询表4-1(a)中某一弧段号时，首先查寻索引表，根据索引表提供的弧段号的地址，可直接到弧段数据文件中读取该弧段号的所有数据。

    在地理信息系统中，由于空间数据量大，因而在空间数据分析处理中，经常使用索引文件，以提高系统运行速度。

    四、倒排文件(Inverted File)

    上面各节介绍的文件都是只含一个主关键字的文件。若需要对主关键字以外的其它次关键字进行查询时，通常的做法是顺序存取主文件中的每一个记录，再对该记录中次关键进行比较，这样存取文件效率太低，为此引入了多关键字文件的概念。在多关键字文件中，需要建立一系列次关键字索引表。次关键字索引表中每个索引项应包含次关键字及具有同一次关键字的多个记录的主关键字或物理记录号。这种次关键字的索引表称作倒排表。倒排表和文件一起共同构成了倒排文件。

    倒排文件的主要优点是对复杂的多关键字查询时，可在倒排表中先完成查询的“交”、“并”等逻辑运算，然后将得到的结果再对主文件中记录进行存取。也就是把对记录的查询转换成地址集合的运算，从而提高了查询的速度。

    在地理信息系统中常常有多关键字文件，并要对多关键字进行逻辑查询。因此，倒排文件在地理信息系统中应用很广。

    例如：已知一批土地资源数据存于文件中，其中地块号为关键字，而地貌类型、坡度、坡向、利用现状为次关键字。现对次关键字分别建立表4-2(b)为地貌类型倒排表，表4-2(c)为坡向倒排表，表4-2(d)为利用现状倒排表。这些倒排表同土地资源文件表4-2(a)共同组成倒排文件。

    假设现在要查询土地资源数据库中，利用现状为林地，地貌类型为缓坡、坡向为半阳的地块，其方法是查询倒排文件并进行逻辑运算。查询过程如下：

    首先从倒排表 4-2(d)查出利用现状为林地的地块号 P1=[1，4，5，6，10]；从倒排表4-2(a)查出地貌类型为缓坡的地块号P2=[1，5，6，10]；再从倒排表4-2(c)查出坡向为半阳的地块号P3=[4，6，10]。所查询的目标地块号的逻辑表达式为：P=P1∩P2∩P3=[6，10]。

    从而知道利用现状为林地，地貌类型为缓坡，坡向为半阳的地块为地块号6和10。

    上述倒排文件中的倒排表，指向主关键字(即地块号)，亦可指向物理地址。不管指针所指的内容是什么，倒排文件的结构意义是相同的。倒排文件和一般文件的不同在于一般文件在查询中首先找记录，然后再找该记录所含的各次关键字是否是所查询的内容。而倒排文件是先定次关键字，然后找含有该次关键字的记录，这样文件查找次序同一般文件查找次序相反，因此称为倒排文件。