操作系统文件管理

痛定思痛。 2022-09-28 11:47 313阅读 0赞

博文很长，我把一章的内容都总结在这里了。

在现代计算机系统中，要用到大量的程序和数据，因内存容量有限，且不能长期保存，故而平时总是把它们以文件的形式存放在外存中，需要时再随时将它们调入内存。如果由用户直接管理外存上的文件，不仅要求用户熟悉外存特性，了解各种文件的属性，以及它们在外存上的位置，而且在多用户环境下，还必须能保持数据的安全性和一致性。显然，这是用户所不能胜任、也不愿意承担的工作。于是，取而代之的便是在操作系统中又增加了文件管理功能，即构成一个文件系统，负责管理在外存上的文件，并把对文件的存取、共享和保护等手段提供给用户。这不仅方便了用户，保证了文件的安全性，还可有效地提高系统资源的利用率。

# #

# 1. 有关文件的概念 #

--------------------

**文件** ：

具有符号名（文件名）的一组相关元素的有序序列，是一段程序或数据的集合。

**文件系统：**

是操作系统中统一管理信息资源的一种软件，管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并且方便用户使用。   
文件系统包含文件管理程序（文件与目录的集合）和所管理的全部文件 ， 是用户与外存的接口 ， 系统软件为用户提供统一方法（以数据记录的逻辑单位），访问存储在物理介质上的信息。

有关直接（随机）存取设备的磁盘知识：[硬盘的读写原理和磁盘碎片的产生][Link 1]

# 2. 文件的分类 #

--------------------

**按性质和用途分类**：系统文件、库文件、用户文件。

**       系统文件 ：**由系统软件构成的文件，只允许用户通过系统调用或系 统提供的专用命今来执行它们，不允许对其进行读写和修改。主要有操作系统核心 和各种系统应用程序或实用工具程序和数据组成   
        **库文件： **文件允许用户对其进行读取和执行，但不允许对其进行 修改 。主要由各种标准子程序库组成   
     **   用户文件 ：**是用户通过操作系统保存的用户文件，由文件的所有者 或所有者授权的用户才能使用 。主要由用户的源程序源代码、可执行目标程序的文件和 用户数据库数据等组成 。

** 按操作保护分类：**只读文件、可读可写文件、 可执行文件。  
       **只读文件：**只允许文件主及被核准的用户去读文件，而不允许写文件。标记为：-r-----   
       **可读可写文件：**允许文件主及被核准的用户去读和写文件。标记为： -rw----   
      ** 可执行文件：**允许文件主及被核准的用户去调用执行该文件而不允许读和写文件，标记为：  ---x---

**按用户观点分类（ UNIX系统文件分类）**

** 普通文件(常规文件)  **：是指系统中最一般组织格式的文件，一般是字符流组成的无结构文件   
      ** 目录文件 ：**是由文件的目录信息构成的特殊文件，操作系统将目录也做成文件，便于统一管理   
      ** 特殊文件**（设备驱动程序）

** 按文件的****逻辑结构****分为：**流式文件（，无结构操作系统文件）、记录式文件（有结构的数据库文件）。

**流式文件：**这是直接由字符序列（字符流）所构成的文件，故又祢为流式文件

> > 大量的源程序、可执行文件、库函数等，所采用的就是无结构的文件形式，即流式文件。其长度以字节为单位。对流式文件的访问，则是采用读/写指针来指出下一个要访问的字符。可以把流式文件看做是记录式文件的一个特例。在 UNIX 系统中，所有的文件都被看做是流式文件，即使是有结构文件，也被视为流式文件，系统不对文件进行格式处理。

**记录式文件：**由若干个记录所构成的文件，故又称为记录式文件。也叫数据库文件。

可采用多种方式组织记录，形成不同的文件：

> ①顺序文件：是由一系列记录按某种顺序排列所形成的文件。 
> 
> ②索引文件：当记录为可变长度时，通常为之建立一张索引表。  
> 
> ③索引顺序文件：它为文件建立一张索引表，为每一组记录中的第一个记录设置一个表项。

**按文件的****物理结构****分类**： 顺序文件（也叫串联文件，连续文件）、链接文件、索引文件、HASH文件、索引顺序文件。

**按文件的存取方式**：顺序存取文件、随机存取文件。

**在****管理信息系统中，****按文件的组织方式分类**：顺序文件、索引文件、直接存取文件。

**按文件中的数据形式分类   
      源文件 ：**由源程序和数据构成的文件   
      **目标文件 ：**由源程序经过相应的计算机语言编译程序编译，但尚未经过链接程序链接的目标代码所形成的文件

# #

# 3. 文件的存取方式 #

--------------------

文件的存取方式是由**文件的性质和用户使用文件的情况决定**。

1 顺序存取。

2 随机存取（也叫直接存取）。

3  索引存取

**        磁带是顺序存取。磁盘是随机存取。**

## **3. 1. 顺序存取** ##

顺序存取是按照文件的逻辑地址顺序存取。

固定长记录的顺序存取是十分简单的。读操作总是读出上一次读出的文件的下一个记录，同时，自动让文件记录读指针推进,以指向下一次要读出的记录位置。如果文件是可读可写的。再设置一个文件记录指针，它总指向下一次要写入记录的存放位置，执行写操作时，将一个记录写到文件 末端。允许对这种文件进行前跳或后退Ｎ（整数）个记录的操作。**顺序存取主要用于磁带文件，但也适用于磁盘上的顺序文件。**  
  可变长记录的顺序文件，每个记录的长度信息存放于记录前面一个单元中，它的存取操作分两步进行。读出时，根据读指针值先读出存放记录长度的单元 。然后，得到当前记录长后再把当前记录一起写到指针指向的记录位置，同时，调整写指针值 。  
    由于顺序文件是顺序存取的，可采用成组和分解操作来加速文件的输入输出。

## **3. 2. 直接存取（随机存取法）** ##

很多应用场合要求以任意次序直接读写某个记录。例如，航空订票系统，把特定航班的所有信息用航班号作标识，存放在某物理块中，用户预订某航班时，需要直接将该航班的信息取出。直接存取方法便适合于这类应用，它通常用于磁盘文件。  
    为了实现直接存取，一个文件可以看作由顺序编号的物理块组成的，这些块常常划成等长，作为定位和存取的一个最小单位，如一块为1024字节、4096字节，视系统和应用而定。于是用户可以请求读块22、然后，写块48，再读块9等等。直接存取文件对读或写块的次序没有限制。用户提供给操作系统的是相对块号，它是相对于文件开始位置的一个位移量，而绝对块号则由系统换算得到。

## **3.3. 索引存取** ##

第三种类型的存取是基于索引文件的索引存取方法。由于文件中的记录不按它在文件中的位置，而按它的记录键来编址，所以，用户提供给操作系统记录键后就可查找到所需记录。  
    通常记录按记录键的某种顺序存放，例如，按代表健的字母先后次序来排序。对于这种文件，除可采用按键存取外，也可以采用顺序存取或直接存取的方法。信息块的地址都可以通过查找记录键而换算出。实际的系统中，大都采用多级索引，以加速记录查找过程。

# 4. 几种常见的文件物理结构 #

--------------------

几种常见的文件物理结构：

顺序文件（也叫串联文件，连续文件）、链接文件、索引文件、HASH文件、索引顺序文件。

# 5. 顺序文件 #

--------------------

是指文件中的物理记录按其在文件中的逻辑记录顺序依次存入存储介质而建立的。即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。

顺序文件在存储介质中可以有两种不同的实现结构：连续结构和链结构。  
        连续结构：是一种最简单的物理文件结构，它把逻辑上连续的文件信息依次存放在连续编号的物理块中。即次序相继的两个物理记录在存储介质上的位置是相邻的。也称为连续文件；

图5.19给出了连续结构文件的图形说明。在图中，一个逻辑块号为0、1、2、3的文件依次存放在物理块15、16、17、18中。

**                ![641711175b7581e120e5b49138781268.png][]**

5.19连续结构文件的示意图件  
     连续文件结构的优点是一旦知道了文件在文件存储设备上的起始地址（首块号）和文图5.19连续结构文件的示意图件长度（总块数），就能很快地进行存取。但是连续结构文件在建立文件时必须在文件说明信息中确定文件信息长度，且以后不能动态增长；而且在文件进行某些部分的删除后，又会留下无法使用的零头空间。因此，连续结构不宜用来存放用户文件、数据库文件等经常被修改的文件。

连续结构的优点是：

(1)结构简单；

(2)顺序访问速度快，对于等长记录的连续文件可以进行顺序存取，也可以进行类似折半查找的随机存取，但是对于不等长记录的连续文件只能进行顺序存取；   
     (3)因为数据集中存放在连续的盘块中，访问时所需的寻道次数和寻道时间少。

连续结构存储的缺点：

(1)由于插入和删除记录会引起其它记录的移动，在外存中执行此操作会引起磁头的频繁来回移动，因此连续结构只能在文件的末尾插入记录，删除记录时，只作标记进行逻辑删除，只有用户指定物理删除时才真正删除相应记录，进行记录的移动；

(2)顺序文件需要连续的盘块存放数据，因此，在插入记录时如果原来分配的盘块已没有空闲空间，而与其邻接的盘块也不空闲时，需要重新在外存中查找新的较大的空闲空间，并将原有数据移动到新空间中，然后才能插入新的数据，因此，连续结构不易动态增长，而且外存容易存在碎片。

链结构将逻辑上连续的文件信息分散存放在若干不连续的物理块中，其中每个物理块设有一个指针，指向其后续连接的另一个物理块。即物理记录的次序由指针相链表示。也称串联文件

图5.20给出了链结构文件的物理结构。使用链结构时，不必在文件说明信息中指明文件的长度，只要指明该文件的第一个块号就可以按链指针检索整个文件。链结构的另一个特点是文件长度可以动态地增长，只要调整链指针就可在任何一个信息块之间插入或删除一个信息块。

![f9ffe9bbcb350eea74be342952b6efc7.png][]

**图5.20链结构文件的示意图**

文件采用链结构时，逻辑块到物理块的转换由系统沿链查找与逻辑块号对应的物理块号的办法完成。例如，在图5.20的文件结构中，如果用户所要进行操作的逻辑块号为2，则系统从第一个物理块20开始，一直沿链搜索到逻辑块号为2的第三块时，得到其所对应的物理块号为22。因此，链结构不适宜随机存取访问。

链结构主要优点是：

(1)提高了磁盘空间利用率，解决了磁盘碎片问题；

(2)便于文件的插入和删除操作；   
     (3)便于文件的动态增长。   
    从本质上讲，顺序文件就是线性表，因而对顺序文件的各种操作与线性表类似，但是，外存的访问速度比主存要慢的多，在考虑算法时要立足于尽量减少外存的访问次数，寻道次数和寻道时间。

磁带是典型的顺序存取设备，因此存储在磁带上的文件只能顺序文件。

# #

# 6. 索引文件 #

--------------------

**1．索引文件**

建立一张逻辑记录和物理记录之间对应关系的索引表。这类包括数据去和索引表两大部分的文件称**做索引文件**。

**2．索引表组成**  
      索引表由若干索引项组成。一般索引项由主关键字和该关键字所在记录的物理地址组成。如图6.1（b）。

注意： 索引表必须按主关键字有序，而主文件本身则可以按主关键字有序或无序。

**3．索引顺序文件和索引非顺序文件**  
      （1）索引顺序文件(Indexed Sequential File)：主文件按主关键字有序的文件称索引顺序文件。  
    　 在索引顺序文件中，可对一组记录建立一个索引项。这种索引表称为稀疏索引。  
     （2）索引非顺序文件(Indexed NonSequentail File)：主文件按主关键字无序得文件称索引非顺序文件。  
    　 在索引非顺序文件中，必须为每个记录建立一个索引项，这样建立的索引表称为稠密索引。  
  注意：  
    　① 通常将索引非顺序文件简称为索引文件。  
    　② 索引非顺序文件主文件无序，顺序存取将会频繁地引起磁头移动，适合于随机存取，不适合于顺序存取。  
    　③ 索引顺序文件的主文件是有序的，适合于随机存取、顺序存取。  
    　④ 索引顺序文件的索引是稀疏索引。索引占用空间较少，是最常用的一种文件组织。  
    　⑤ 最常用的索引顺序文件：ISAM文件和VSAM文件。

**4. 索引文件操作**：

1). 检索方式为：直接存取和按关键字存取。“检索”将分两步进行：先查索引表，利用折半查找法去检索索引表，然后根据索引中指针所指记录（索引项指示的外存物理地址）读取外存记录。

注意：①索引表不大时，索引表可一次读入内存，在索引文件中检索只需两次访问外存：一次读索引，一次读记录。  
　            ②由于索引表有序，对索引表的查找可用顺序查找或二分查找等方法。

2)．插入记录时，“记录”插入在主文件的末尾，而相应的“索引项”必须插入在索引的合适位置上。因此，最好在建索引表时留有一定“空位”。

3)．删除记录时，仅需删除索引表中相应的索引项即可。

4)．更新记录时，应将更新后的记录插入在主文件的末尾，同时修改相应的索引项。

![6ca5057aade1cf62212e10c020c9dd83.png][]

图6.1 （a） 主文件（数据区）  （b） 索引表        c（输入过程中建立的索引表）

**5. 利用查找表建立多级索引 **

**1）查找表**：

**         **对索引表建立的索引，称为查找表。查找表的建立可以为占据多个页块的索引表的查阅减少外存访问次数。

图6.1 (b)的索引表占用了三个页块的外存，每个页块能容纳三个索引项，则可为图6.2所示。检索记录时，先查找查找表，再查索引表，然后读取记录，三次访问外存即可。

![89dd5a2759995d1217a4b0eab6c41a9d.png][]

图6.2  图6.1（b） 索引表的索引，

**2）多级索引**  
    　当查找表中项目仍很多，可建立更高一级的索引。通常最高可达四级索引：  
    　数据文件一索引表一查找表一第二查找表一第三查找表。  
　　  【例】检索过程从最高一级索引--第三查找表开始，需要5次访问外存。：

![61bd56cbff1ac3ee963d4bcc0aa07c54.png][]  
    注意：  
　    ① 多级索引是一种静态索引  
    　② 多级索引的各级索引均为顺序表，结构简单，修改很不方便，每次修改都要重组索引。

**3）动态索引**  
    当数据文件在使用过程中记录变动较多时，利用二叉排序树(或AVL树)、B-树(或其变型)等树表结构建立的索引，为动态索引。  
   **（1）树表特点**  
　　   ① 插入、删除方便  
　　   ② 本身是层次结构，无须建立多级索引  
　　   ③ 建立索引表的过程即为排序过程。  
   **（2）树表结构选择**  
　　   ① 当数据文件的记录数不很多，内存容量足以容纳整个索引表时，可采用二叉排序树(或AVL树)作索引；  
　　   ② 当文件很大时，索引表(树表)本身也在外存，查找索引时访问外存的次数恰为查找路径上的结点数。采用m阶B-树(或其变型)作为索引表为宜（m的选择取决于索引项的多少和缓冲区的大小）。  
   （**3）外存的索引表的查找性能评价**  
    由于访问外存的时间比内存中查找的时间大得多，所以外存的索引表的查找性能主要着眼于访问外存的次数，即索引表的深度。

**优缺点：**

索引结构是链式结构的一种扩展，除了具备链式结构的优点外，还克服了它只能作顺序存取的缺点，具有直接读写任意一个记录的能力，便于文件记录的插入、删除、修改。

索引文件的缺点是：增加了索引表的空间开销和查找时间，索引表的信息量甚至可能远远超过文件记录本身的信息量。

**   有两种典型的索引顺序文件**：

**一、ISAM文件：**ISAM(**I**ndex**S**equential **A**ccess **M**ethod)(索引顺序存取方法)是一种专为磁盘存取设计的文件组织方法。

**二、VSAM文件：**VSAM(**V**istual **S**torage **A**ccess **M**ethod)文件是利用操作系统中提供的虚拟存储器的功能组织的文件，免除了用户为读/写记录时直接对外存进行的操作，对用户而言，文件只有控制区间和控制区域等逻辑存储单位。

# #

# 7. ISAM文件和VSAM文件 #

--------------------

## 7.1 ISAM文件 ##

**1. ISAM文件组成**

ISAM为Indexed Sequential Access Method(索引顺序存取方法)的缩写，它是一种专为磁盘存取文件设计的  
文件组织方式，采用静态索引结构。    
        由于磁盘是以盘组、柱面和磁道三级地址存取的设备，所以可对磁盘上的数据文件建立盘组、柱面和磁道三级索引。

1）磁道索引

磁道索引中的每一个索引项，都由两个子索引项组成：基本索引和溢出索引项,每一子索引项又由关键字和指针两项组成。   
    基本索引项关键字记录该磁道中最大（最末一个记录）的关键字，指针记录该磁道中第一记录的位置；

溢出索引项记录该磁道中溢出的记录的最键字，指针记录溢出区中的第一个记录。

2）柱面索引

柱面索引每一索引项由关键字和指针两项组成，关键字记录该柱面中最大（最末一个记录）的关键字，指针记录该柱面中磁道索引的位置。

3）主索引  
    柱面索引存放在某个柱面上，如果柱面索引过大，占多个磁道时，则建立柱面索引的索引—主索引。

因此，ISAM文件由多级主索引、柱面索引、磁道索引和主文件组成。文件存放记录时遵循下面原则：

记录在同一盘组上存放时，应先集中放在一个柱面上，然后再顺序存放在相邻的柱面上；对同一柱面，则应按盘面的次序顺序存放。

各种索引项结构如图7.1所示：

![b2f6df2aea17e8837d15531d45cc21fd.png][] ->![7f75458e56f5c4f401b0822ed48d51da.png][]\->

![49c802a229c55f709b1d7f20f0b1a434.png][]

图7.1

图7.2 为一ISAM文件结构示意图，从图中可看出，主索引是柱面索引的索引，这里只有一级主索引。

![fa0c180ce8a67bd9d842edd5daa0fd46.png][]

7.2 VSAM文件示意图

当文件占用的柱面索引很大，使得一级主索引也很大时，可采用多级主索引。当然，若柱面索引较小时，则主索引可省略。通常主索引和柱面索引放在同一个柱面上(图7.2是放在0号柱面上)，主索引放在该柱面最前面的一个磁道上（图7.2中  
放在0柱面0磁道上），其后的磁道中存放柱面索引。每个存放主文件的柱面都建立有一个磁道索引，放在该柱面的最前面的磁道T0上，其后的若干个磁道是存放主文件记录的基本区，该柱面最后的若干个磁道是溢出区。基本区中的记录是按主关键字大小顺序存储的，溢出区 被整个柱面上的基本区中各磁道共享，当基本区中某磁道溢出时，就将该磁道的溢出记录，按主关键字大小链成一个链表(溢出链表)放入溢出区。

**2. ISAM文件的检索 **

在ISAM文件上检索记录时，过程如下：

1）从主索引出发，找到相应的柱面索引；

2）从柱面索引找到记录所在柱面的磁道索引；

3）从磁道索引找到记录所在磁道的起始地址，由此出发在该磁道上进行顺序查找，直到找到为止。

若找遍该磁道均不存在此记录，则表明该文件中无此记录；若被查找的记录在溢出区，则可从磁道索引项的溢出索引项中得到溢出链表的头  
指针，然后对该表进行顺序查找。

例如，要在图7.2中查找记录R136，先查主索引，即读入C0T0；因为136<286，则查找柱面索引的C0T1，即读人C0T1；因为136<145，所以进一步把C1T0读入内存；查磁道索引，因为90<136<145，所以C1T2即为R136所存放的磁道，读人C1T2后即可查得R136。    
     为了提高检索效率，通常可让主索引常驻内存，并将柱面索引放在数据文件所占空间居中位置的柱面上，这样，从柱面索引查找到磁道索引时，磁头移动距离的平均值最小。

**3.ISAM文件的插入操作 **  
    当插人新记录时，首先找到它应插入的磁道,若该磁道不满，则将新记录插入该磁道的适当位置上即可；若该磁道已满，则新记录或者插在该磁道上，或者直接插入到该磁道的溢出链表上。插入后，可能要修改磁道索引中的基本索引项和溢出索引项。

(1)插入R65，首先将1柱面1磁道中大于65的记录顺次后移，导致R90溢出至溢出区T11’0(11磁道0块中)，造成磁道T1中最大关键字成为R80，修改磁道索引，将基本项中最大关键字90修改为80，将溢出项中最大关键字改为90，指针指向T11’0（溢出链表头在11磁道0块中），然后在相应位置插入R65。    
    例如，在图7.2中依次插入R65 R95和R83。    
    (2)插入R95，使得T2中的R145溢出至溢出区T11’1，修改相应磁道索引。(3)插入R83，因为80<83<90，则83直接插入溢出区T11’2中，其指针指向T11’0，并修改磁道1的溢出链表，使得表头指向T11’2。  插入完成后的结果如图7.3所示。

![d863f8f00c43cffb9085ea2deae4184b.png][]

图7.3 VSAM

4. ISAM文件的删除操作   
      ISAM文件中删除记录的操作，比插入简单得多，只要找到待删除的记录，在其存储位置上作删除标记即可，而不需要移动记录或改变指针。在经过多次的增删后，文件的结构可能变得很不合理。此时，大量的记录进入溢出区，而基本区中又浪费很多的空间。因此，通常需要周期性地整理ISAM文件，把记录读入内存重新排列，复制成一个新的ISAM文件，填满基本区而空出溢出区。

## 7.2 VSAM文件 ##

VSAM是Virtual Storage Access Method(虚拟存储存取方法)的缩写，它也是一种索引顺序文件的组  
织方式，采用B+树作为动态索引结构。这种文件组织方式利用了操作系统中提供的虚拟存储器的功能，用户读/写记录时不必再考虑外存储器中的柱面、磁道等具体存储信息，文件只有控制区间和控制区域等逻辑存储单位，这种存储方式可以在一个磁道中放个控制区间，也可以一个控制区间跨个磁道。

**1. VSAM文件结构  **

VSAM文件的结构由三部分组成：  索引集  顺序集  数据集

![f0319e322ccce24f0a2444474e806375.png][]

图 7.4

**2.VSAM文件中控制区间的结构 **

**    **在VSAM文件中，记录可以是定长的也可以是不定长的。因而在控制区间中，除了存放记录本身之外，还有每个记录的控制信息(如记录的长度等)和整个区间的控制信息(如区间中存放的记录数等)，控制区间的结构如图7.5所示。在控制区间上存取一个记录是需从控制区间的两端出发同时向中间扫描。

![7f5b2df53590de157e0420616abf2937.png][]

图7.5 VSAM文件控制区间结构图

**3.VSAM文件的插入**   
    VSAM文件中没有溢出区，解决插入的方法是在初建文件时留出空间：一是每个控制区间内不填满记录，在最末一个记录和控制信息之间留有空隙；二是在每个控制区域中有一些完全空的控制区间，并在顺序集的索引中指明这些空区间。当插入新记录时，大多数的新记录能插入到相应的控制区间内，但要注意：为了保持区间内记录的关键字从小至大有序，则需将区间内关键字大于插入记录关键字的记录，向控制信息的方向移动。

若在若干记录插入之后控制区间已满，则在下一个记录插入时，要进行控制区间的分裂，即把近乎一半的记录移到同一控制区域内全空的控制区间中，并修改顺序集中相应索引。倘若控制区域中已经没有全空的控制区间，则要进行控制区域的分裂，此时顺序集中的结点亦要分裂，由此需要修改索引集中的结点信息。但由于控制区域较大，通常很少发生分裂的情况。

**4. VSAM文件的删除 **

**   ** 在VSAM文件中删除记录时，需将同一控制区间中，比删除记录关键字大的记录向前移动，把空间留给以后插人的新记录。若整个控制区间变空，则回收用作空闲区间，且需删除顺序集中相应的索引项。

**5. VSAM文件的优点   
   ** 和ISAM文件相比，基于B+树的VSAM文件有如下优点：能保持较高的查找效率，查找一个后插入记录和查找一个原有记录具有相同的速度；动态地分配和释放存储空间，可以保持平均75％的存储利用率；而且永远不必对文件进行再组织。因而基于B+树的VSAM文件，通常被作为大型索引顺序文件的标准组织。

# #

# 8. Hash（直接文件）文件 #

--------------------

**1. Hash文件 **

哈希（Hash）文件又称散列文件或者直接存取文件，是利用哈希函数法组织的文件，它类似于哈希表，即根据文件记录的关键字的特点，设计一种哈希函数和处理冲突的方法，从而将记录散列到外存储器上。由于哈希文件中通过计算来确定一个记录在存储设备上的存储位置，因而逻辑顺序的记录在物理地址上是不相邻的，**因此哈希文件不宜使用磁带存储，只适宜使用磁盘存储**；并且哈希文件这种结构只适用于定长记录文件和按主键随机查找的访问方式。

哈希文件的组织方法与哈希表的组织方法相比有一点不同。对于哈希文件来说，磁盘上的文件记录通常是成组存放的，若干个记录组成一个称为桶的存储单位。假若一个桶能存放m个记录，即m个哈希函数值相同的记录可以存放在同一个桶中，而当第m+1个哈希函数值相同的记录出现时才发生冲突。

**2. 链地址法解决冲突的方法是**  
    哈希文件中处理冲突的方法也可采用哈希表中处理冲突的各种方法，但链地址法是哈希文件处理冲突  
的首选方法。    
    当某个桶中的哈希函数值相同的记录超过m个时，便产生“溢出”，此时会动态生成一个桶以存放那些溢出的哈希函数值相同的记录。通常把存放前m个哈希函数值相同的记录的桶称为基桶，把存放溢出记录的桶称为溢出桶。基桶和溢出桶的结构相同，均为m个记录的数组加一个桶地址指针。

当某个基桶未溢出时，基桶中的指针为空；当基桶溢出时，动态生成一个溢出桶存放溢出记录，基桶中的指针置为指向该溢出桶；若溢出桶中的哈希函数值相同的记录再溢出时，再动态生成第二个溢出桶存放溢出记录，第一个溢出桶中的指针置为指向第二个溢出桶。这样就构成了一个链接             ![a653f5bb6c2b98b7a283feed70c70e03.png][]

图8.1 hash文件。   
  
例如，假定某个文件有20个记录，其关键字集合为\{2，23，5，26，1，3，24，18，27，12，7，9，4，19，6，16，33，11，10，13\}。桶的容量=3，桶  
数=7，用除留余数法作哈希函数H(key)=key%7，其对应的哈希文件如图8.1所示。

**3.在哈希文件中查找记录**   
       首先根据待查记录的关键字值求得哈希地址（即基桶地址），将基桶的记录读入内存进行顺序查找，若找到某记录的关键字等于待查记录的关键字，则查找成功；若基桶内无待查记录且基桶内指针为空，则文件中没有待查记录，查找失败；若基桶内无待查记录且基桶内指针不空，则将溢出桶中的记录读入内存进行顺序查找，若在某个溢出桶中查找到待查记录，则查找成功；若所有溢出桶链内均未查找到待查记录，则查找失败。

**4.哈希文件中删去一个记录**    
    仅需对被删记录作删除标记即可。

**6.哈希文件的优点是：  **

> (1)文件随机存放，记录不需进行排序；  
> 
> (2)插入、删除方便；  
> 
> (3)存取速度快； 
> 
> (4)不需要索引区，节省存储空间。

**7.哈希文件的缺点是**：   
     (1)不能进行顺序存取，只能按关键字随机存取；   
     (2)询问方式限于简单询问；   
    （3）在经过多次插入、删除后，可能造成文件结构不合理，需要重新组织文件。

# #

# 9. 多重文件 #

--------------------

**1.多重表文件 **  
    多重表文件是一种将索引方法和链接方法相结合的组织方式，他对主关键字建立主索引，对每个需要查询的次关键字均建立一个索引，同时将具有相同次关键字的记录链接成一个链表，并将此链表的头指针、链表长度及次关键字，作为索引表的一个索引项。通常多重表文件的主文件是一个顺序文件。如图：

![b99948282aa5588aa32f8598a242633f.png][]

**2. 倒排文件 **  
      倒排文件和多重表文件构造相似，主要区别在于在次关键字索引中，具有相同次关键字的记录之间不设指针进行链接，而是在倒排表中列出具有该次关键字记录的所有物理记录号。 倒排文件中的次关键字索引称做倒排表。倒排表和主文件一起就构成了倒排文件。上例文件中的倒排表如图9.2所示。

![719484a5aceb194d72c7c4c0ab0c7834.png][]

图9.2 倒排表

**3. 倒排文件的应用 **  
    倒排文件应用非常广泛，例如在WEB或者其它文本搜索引擎的设计中，在搜索引擎收集完数据进行预处理时，搜索  
引擎往往需要一种高效的数据结构来对外提供检索服务，而现行最有效的数据结构就是倒排文件，他是搜索引擎的核心内容之一。

详细内容请看：[倒排索引-搜索引擎的基石][-]

参考：

《数据结构(C语言版)》.严蔚敏\_吴伟民

《计算机操作系统教程》张尧学 第三版

[Link 1]: http://blog.csdn.net/hguisu/article/details/7408047
[641711175b7581e120e5b49138781268.png]: /images/20220708/2c9c2e1faba1480480915ac63656c7d8.png
[f9ffe9bbcb350eea74be342952b6efc7.png]: /images/20220708/0dac0298ba0e448983038ffc119cf7d1.png
[6ca5057aade1cf62212e10c020c9dd83.png]: /images/20220708/ec6dac2606064a3e8643ac04c347941c.png
[89dd5a2759995d1217a4b0eab6c41a9d.png]: /images/20220708/bc7f194393ba448f89dadae63e44da13.png
[61bd56cbff1ac3ee963d4bcc0aa07c54.png]: /images/20220708/27bbf61884ce45d488c8bc9ad88a3cfe.png
[b2f6df2aea17e8837d15531d45cc21fd.png]: https://img-blog.csdnimg.cn/img_convert/b2f6df2aea17e8837d15531d45cc21fd.png
[7f75458e56f5c4f401b0822ed48d51da.png]: /images/20220708/4290a95db1674fb9a66dc624b442783e.png
[49c802a229c55f709b1d7f20f0b1a434.png]: /images/20220708/deec09f6eb9648359c734aabcf2e45eb.png
[fa0c180ce8a67bd9d842edd5daa0fd46.png]: /images/20220708/e24ced1729fe41d3ae5c3c46a6d3a60d.png
[d863f8f00c43cffb9085ea2deae4184b.png]: /images/20220708/644ed04f8e4543ddb873ddd4082eae4a.png
[f0319e322ccce24f0a2444474e806375.png]: /images/20220708/d97cc863f01440c38107a70f1cf4e7bc.png
[7f5b2df53590de157e0420616abf2937.png]: /images/20220708/7d66fd04549a4d1eb449e86e5287a6cb.png
[a653f5bb6c2b98b7a283feed70c70e03.png]: /images/20220708/ca5ec3e8d47c42ae9cecedb940de5226.png
[b99948282aa5588aa32f8598a242633f.png]: /images/20220708/f682234efe4544b5be8de3482c0b464f.png
[719484a5aceb194d72c7c4c0ab0c7834.png]: /images/20220708/d1ad837458fa4b20b6299d961e919d33.png
[-]: http://blog.csdn.net/hguisu/article/details/7969757