文件的组织结构及存取方法课件

4.2文件的组织结构及存取方法

文件组织结构分为文件的逻辑结构（filelogicalstructure）和文件的物理结构（filephysicalstructure）。前者是从用户的观点出发，所看到的是独立于文件物理特性的文件组织形式，是用户可以直接处理的数据及其结构。而后者则是文件在外存上具体的存储结构。4.2文件的组织结构及存取方法

文件组织结构1

4.2.1文件的逻辑结构

所谓文件的逻辑结构就是从用户观点出发所见到的文件结构。它通常分为两种形式：记录式文件和流式文件。记录式文件在逻辑上总是被看成一组顺序的记录集合，是一种有结构的文件组织，它又分成定长记录文件和变长记录文件。而流式文件又称无结构文件，是指文件内部不再划分记录，它是由一组相关信息组合成的有序字符流。这种文件的长度直接按字节计算。4.2.1文件的逻辑结构

所谓文件的逻辑结构就是从用户观24.2.2文件的物理结构

文件的物理结构则是指文件在外部存储介质上的存放形式，也叫文件的存储结构。它对文件的存取方法有较大的影响。文件在逻辑上看都是连续的，但在物理介质上存放时却不一定连续。下面是几种基本的文件物理存储组织形式。4.2.2文件的物理结构

文件的物理结构则是指文件在外部存31.连续文件连续文件是基于磁带设备的最简单的物理文件结构，它是把一个逻辑上连续的文件信息存放在连续编号的物理块中。例如文件file1长度为2500字节，存放在连续分块的磁带上，每块大小设为512字节，这样它要占用5块。设首块编号是11，file1在带上的存放形式如图4.3所示。1.连续文件连续文件是基于磁带设备的最简单的物理文件结构，它4……首块编号11文件长度5………1112131415…文件说明磁带file1图4.3连续文件存放形式……首块编号11文件长度5………1112131415…文件磁5

连续文件的优点是在顺序存取时速度较快，常用于存放系统文件，如操作系统文件、编译程序文件和其它由系统提供的实用程序文件。因为这类文件往往被从头至尾依次存取。也存在如下缺点：第一，要求建立文件时就确定它的长度，依此来分配相应的存储空间，这往往很难实现。第二，它不便于文件的动态扩充。第三，可能出现外部碎片，就是在存储介质上存在很多空闲块，但它们都不连续，无法被连续文件使用，造成浪费。连续文件的优点是在顺序存取时速度较快，62.串连文件为了使系统能找到下一个逻辑块所在的物理块，可在各物理块中设立一个指针（称为连接字），它指示该文件的下一个物理块，如图4.4所示。文件A在逻辑上有3块：0~2块；而对应的物理块号却是90、65和71，最后一块的连接字为NULL，表示该块是文件结尾，即没有后继块。新的问题：①一般仅适于对信息的顺序访问，而不利于对文件的随机存取。②每个物理块上增加了一个连接字，为信息管理添加了一些麻烦。2.串连文件为了使系统能找到下一个逻辑块所在的物理块，可在各7……首物理块90……90块6565块7171块Null文件A的说明图4.4串联文件……首物理块90……90块6565块7171块Null文件A83.索引文件索引文件是实现非连续分配的另一种方案：系统为每个文件建立一个索引表，其中的表项指出存放该文件的各个物理块号，而整个索引表由文件说明项指出，如图4.5所示。这种结构除了具备串连文件的优点之外，还克服了它的缺点，它可以方便地进行随机存取。但是这种组织形式需要增加索引表，增加了空间开销。3.索引文件索引文件是实现非连续分配的另一种方案：系统为每个9……A文件的索引指针……257348NULL……25块48块73块…0123图4.5索引文件……A文件的索引……257348NULL……25块48块73104.多重索引文件当文件很大时，不仅存放文件信息需要大量盘块，而且相应的索引表也必然很大。例如，若盘块大小为1KB，那么长度为100KB的文件就需要100个盘块，索引表至少包含100项；若文件大小为1000KB，则相应索引表项要有1000项。设盘块号用4B表示，上述第二种情况下，索引表就至少占用4000B（约4KB）。很显然，在这种情况下把索引表整个放在内存是不合适的，而且不同文件的大小不同，文件在使用过程中很可能需要扩充空间。单—索引表结构已无法满足灵活性和节省内存的需要，为此人们提出多重索引结构（又称多级索引结构）。这种方法具有一般索引文件的优点，但也存在着间接索引需要多次访问磁盘而影响速度的缺点。4.多重索引文件当文件很大时，不仅存放文件信息需要大量盘块，114.2.3文件的存取方法

顺序存取方法进程从文件开始处顺序读取文件中所有字节或者记录，不能够跳过某些内容，也不能够非顺序读取，即按照逻辑顺序依次存取文件中的内容。这种存取方式最为简单，在以磁带为存储介质的系统中，用这种顺序存取方法是非常方便的。对文件的大量操作是读和写。可以用一个读写指针rp指向下一次要读出的记录的起始地址，那么当该记录读出后，对rp作相应的修改。例如对定长记录文件，有rpi+1=rpi+L其中，L是记录长度。4.2.3文件的存取方法

顺序存取方法122.随机存取方法随机存取是把文件视为带有编号的块或记录，每块的大小通常是一样的，它们被操作系统作为最小的定位单位。随机存取文件允许随意读出或写入块，对文件的存取不限定顺序对于变长记录结构的文件，用计算从头至指定记录的长度来确定读写位移的方式是很不方便的，通常采用索引表组织方式，如图4.6所示。2.随机存取方法随机存取是把文件视为带有编号的块或记录，每块13L0L1……Li……R0R1……Ri…………

01i索引号长度指针索引表逻辑文件图4.6变长记录文件L0L1……Li……R0R1……Ri…………01143.其它存取方法4.成块和缓冲

磁盘系统是典型的成块I/O系统：由扇区大小来定义物理块的大小，所有的磁盘I/O都以块为基本单位，各块大小相同。文件逻辑记录的大小并不一定恰好等于物理块的大小。逻辑记录的长度甚至可以是变化的。文件信息的传输是经过缓冲区的：读文件时，先把数据从盘块送到缓冲区，再由缓冲区传到指定内存中；写文件的数据流向恰好与之相反。为了管理方便，缓冲区的大小一般与物理盘块大小相同。3.其它存取方法4.成块和缓冲154.2文件的组织结构及存取方法

文件组织结构分为文件的逻辑结构（filelogicalstructure）和文件的物理结构（filephysicalstructure）。前者是从用户的观点出发，所看到的是独立于文件物理特性的文件组织形式，是用户可以直接处理的数据及其结构。而后者则是文件在外存上具体的存储结构。4.2文件的组织结构及存取方法

文件组织结构16

4.2.1文件的逻辑结构

所谓文件的逻辑结构就是从用户观点出发所见到的文件结构。它通常分为两种形式：记录式文件和流式文件。记录式文件在逻辑上总是被看成一组顺序的记录集合，是一种有结构的文件组织，它又分成定长记录文件和变长记录文件。而流式文件又称无结构文件，是指文件内部不再划分记录，它是由一组相关信息组合成的有序字符流。这种文件的长度直接按字节计算。4.2.1文件的逻辑结构

所谓文件的逻辑结构就是从用户观174.2.2文件的物理结构

文件的物理结构则是指文件在外部存储介质上的存放形式，也叫文件的存储结构。它对文件的存取方法有较大的影响。文件在逻辑上看都是连续的，但在物理介质上存放时却不一定连续。下面是几种基本的文件物理存储组织形式。4.2.2文件的物理结构

文件的物理结构则是指文件在外部存181.连续文件连续文件是基于磁带设备的最简单的物理文件结构，它是把一个逻辑上连续的文件信息存放在连续编号的物理块中。例如文件file1长度为2500字节，存放在连续分块的磁带上，每块大小设为512字节，这样它要占用5块。设首块编号是11，file1在带上的存放形式如图4.3所示。1.连续文件连续文件是基于磁带设备的最简单的物理文件结构，它19……首块编号11文件长度5………1112131415…文件说明磁带file1图4.3连续文件存放形式……首块编号11文件长度5………1112131415…文件磁20

连续文件的优点是在顺序存取时速度较快，常用于存放系统文件，如操作系统文件、编译程序文件和其它由系统提供的实用程序文件。因为这类文件往往被从头至尾依次存取。也存在如下缺点：第一，要求建立文件时就确定它的长度，依此来分配相应的存储空间，这往往很难实现。第二，它不便于文件的动态扩充。第三，可能出现外部碎片，就是在存储介质上存在很多空闲块，但它们都不连续，无法被连续文件使用，造成浪费。连续文件的优点是在顺序存取时速度较快，212.串连文件为了使系统能找到下一个逻辑块所在的物理块，可在各物理块中设立一个指针（称为连接字），它指示该文件的下一个物理块，如图4.4所示。文件A在逻辑上有3块：0~2块；而对应的物理块号却是90、65和71，最后一块的连接字为NULL，表示该块是文件结尾，即没有后继块。新的问题：①一般仅适于对信息的顺序访问，而不利于对文件的随机存取。②每个物理块上增加了一个连接字，为信息管理添加了一些麻烦。2.串连文件为了使系统能找到下一个逻辑块所在的物理块，可在各22……首物理块90……90块6565块7171块Null文件A的说明图4.4串联文件……首物理块90……90块6565块7171块Null文件A233.索引文件索引文件是实现非连续分配的另一种方案：系统为每个文件建立一个索引表，其中的表项指出存放该文件的各个物理块号，而整个索引表由文件说明项指出，如图4.5所示。这种结构除了具备串连文件的优点之外，还克服了它的缺点，它可以方便地进行随机存取。但是这种组织形式需要增加索引表，增加了空间开销。3.索引文件索引文件是实现非连续分配的另一种方案：系统为每个24……A文件的索引指针……257348NULL……25块48块73块…0123图4.5索引文件……A文件的索引……257348NULL……25块48块73254.多重索引文件当文件很大时，不仅存放文件信息需要大量盘块，而且相应的索引表也必然很大。例如，若盘块大小为1KB，那么长度为100KB的文件就需要100个盘块，索引表至少包含100项；若文件大小为1000KB，则相应索引表项要有1000项。设盘块号用4B表示，上述第二种情况下，索引表就至少占用4000B（约4KB）。很显然，在这种情况下把索引表整个放在内存是不合适的，而且不同文件的大小不同，文件在使用过程中很可能需要扩充空间。单—索引表结构已无法满足灵活性和节省内存的需要，为此人们提出多重索引结构（又称多级索引结构）。这种方法具有一般索引文件的优点，但也存在着间接索引需要多次访问磁盘而影响速度的缺点。4.多重索引文件当文件很大时，不仅存放文件信息需要大量盘块，264.2.3文件的存取方法

顺序存取方法进程从文件开始处顺序读取文件中所有字节或者记录，不能够跳过某些内容，也不能够非顺序读取，即按照逻辑顺序依次存取文件中的内容。这种存取方式最为简单，在以磁带为存储介质的系统中，用这种顺序存取方法是非常方便的。对文件的大量操作是读和写。可以用一个读写指针rp指向下一次要读出的记录的起始地址，那么当该记录读出后，对rp作相应的修改。例如对定长记录文件，有rpi+1=rpi+L其中，L是记录长度。4.2.3文件的存取方法

顺序存取方法272.随机存取方法随机存取是把文件视为带有编号的块或记录，每块的大小通常是一样的，它们被操作系统作为最小的定位单位。随机存取文件允许随意读出或写入块，对文件的存取不限定顺序对于变长记录结构的文件，用计算从头至指定记录的长度来确定读写位移的方式是很不方便的，通常采用索引表组织方式，如图4.6所示。2.随机存取方法随机存取是把文件视为带有编号的块或记录，每块28L0L1……Li……R0R1……Ri…………

01i索引号长度