文件组织

介绍

文件的组织是指文件的构造方式。文件用户按照自己的使用要求，把构成文件的元素组织起来，文件的这种结构叫文件逻辑结构。文件系统一方面要使文件满足用户对逻辑文件的使用要求，更重要的要关注如何按照存贮设备特征、文件的存取方式来组织文件，保证文件有效地存贮、检索，也就是说，文件系统主要关注的是文件的物理结构。
文件存取方法是由用户使用文件的要求、存贮设备特征来决定的，不仅要考虑到文件的逻辑结构，而且要考虑到文件物理结构。
当我们讨论文件组织时，我们是在讨论一个文件中记录的排列，因为所有文件都是由记录组成的。用户给出的修改文件内容的命令其实就是一个访问记录的命令。

记录格式

在每个文件里面，记录都应该具有同样的格式——它们可以定长或者变长。不管其具体格式，这些记录都可以是分块或者未分块。
定长记录是最常见的，因为它们最容易直接访问。这就是为什么它们是理想的数据文件。定长记录的关键是记录的大小。如果太小，小过了记录存储的字符数，那么多出的字符就要被截掉了。如果记录大小太大了，大过了要存储的字符数，就会有空间的浪费。
变长记录不会有剩余空间和截掉记录，所以克服了定长的2个缺点。但尽管它也容易一个接一个读取，但因为记录的位置很难计算，所以直接读取很困难。连续访问的文件或者通过目录查找的文件经常使用变长记录格式。记录的格式，它如何分块，和其它相关信息都被保存在文件描述符里。
用来保存信息的空间根据系统各异，它由存储介质的物理性质所限制。

物理组织

一个文件的物理组织就是根据记录的排列和存储介质的特性来组织文件。
在一个磁介质的磁盘上，文件组织可以是下面3种方法中的一种：顺序存储，直接存储，和顺序索引。为了选择最好的方法，程序员或者分析员必须要考虑下面特性的实际：
数据的挥发性——添加和删除的频率
文件的行为——在一个运行中，被处理的记录的百分比

文件大小

响应时间——完成操作之前用户要等待的时间。这在交互环境中的查找和修改信息中尤其重要。
顺序记录组织是最容易实现的，因为记录的存储和得到都是顺序的，一个接一个。为了找到一个记录，文件要从头开始查找直到找到这个记录。
为了加速这个处理过程，一些优化特性被加入系统。一个就是选择记录的一个关键区域，然后再存储记录前都是根据这个区域分类记录。然后当用户需要一个记录的时候，系统只是查找关键区域。当相匹配的记录找到或者关键区域比最后一次比较的记录小时，给出信息“没找到记录”，然后完成搜索。
尽管这个技术辅助查找处理过程，但因为当有记录添加或者删除的时候都要保存，它使得算法更复杂了。为了保存物理顺序，文件必须在更改的时候完成回写或者动态分类。
直接记录组织使用直接访问文件的方法，当然，只有在直接访问存储设备上才能实现。这些文件给用户提供了以任何顺序访问任何记录的灵活性，而不用从头开始寻找。这也是一个随机组织方法，其文件叫做随机访问文件。
记录是由它们的相对地址——它们到文件开始的相对位置来确定的。它们的逻辑地址是当文件被存储或者记录恢复的时候计算出来的。
这个方法很直截了当。用户通过记录格式来确定一个区域（或者区域组合），并标记为键域，它唯一确定每一个记录。程序通过一系列指令来保存数据，叫做散列算法，它将每一个键域编号，即记录的逻辑地址。然后把这些交给信息管理器，它可以把逻辑地址通过几步转换成物理地址（簇，表面和记录号）并保持文件组织，检索记录过程也是同样的。
另外，直接访问文件可以连续访问，即从一个相对地址开始，然后增加地址来找到下一个记录。
直接访问文件比顺序文件可以修改得更快，因为记录可以很快回写到它的原始地址。同时它也不需要保存记录的顺序，所以增加和删除文件可以用更少的时间。
电话邮购公司用散列的方法来直接访问客户信息。假设你在订货，你询问你的顾客号。（假设为152132727）。程序将从数据文件中按照散列算法的键值来计算出你的记录的逻辑地址，（在348）。所以当服务员输入152132727,荧幕很快显示出同一个逻辑地址的顾客号。如果你在数据库中，操作员会很快知道，如果不在，你会很快知道。
散列算法的问题在于，一些有唯一主键（比如顾客号）的记录可能会有同一个逻辑地址——这里将产生冲突。在文件管理存储之前，它必须找到另一个逻辑地址。冲突的记录将被存在一个溢出区域，它在文件的生成时就被附加上了。尽管程序做到了从溢出区域与记录的逻辑地址的连接，文件管理还是要处理空间的分配问题。
文件的最大尺寸在它生成的时候就确立了。最终，文件可能会完全写满或者存储在溢出区域的记录数已经太多了，这将导致数据检索的效率大大降低。在这两种情况下，文件必须重新组织和重新写入，这需要由编程者来干预。
索引顺序记录组织是顺序和直接访问的组合。它通过索引顺序访问方法(ISAM)来生成和维护记录，它消除了编程者处理溢出和保存记录顺序的负担。
这种组织方法避免了冲突，因为它没有用哈希算法来生成一个记录的地址。代替它的是，使用了该信息生成索引文件来实现记录的查找。这种组织将顺序的连续的文件分成了同等大小的块。它的大小由文件管理器来决定，以充分利用物理存储设备的优点并优化检索策略。每一个索引文件的项目包括最高的记录键和这个数据块的物理位置，即这个记录和记录号最小的记录的存储位置。
因此，为访问文件中的记录，系统先搜索索引文件，然后进入物理位置。索引文件就像是一个数据的指示器。一个索引顺序文件也有溢出区域，但是它会扩展到整个文件（可能是很少的记录），所以已有的记录也可以扩展，新的记录可以生成在物理顺序与逻辑顺序最近的地方。另一个溢出区不在主要数据区域，而是只有在其它溢出区都充满了才用。我们叫它为最后记录的溢出区。
这个最后分配的溢出区可以在文件的有效时间内添加记录。记录是用软件包来实现逻辑顺序保存，而不用程序员投入太多的努力。当然，添加太多记录时进程就会变慢，这是因为寻找一个记录必须从目录到主数据区最后才到溢出区。
当恢复时间变得太长，文件就需要重新组织。这个工作尽管不像组织一个直接访问文件一样枯燥，但通常仍要系统的分析员或者程序员来做。
对于大多数的动态文件，索引顺序可以选择，它允许直接访问一小部分记录和顺序访问很多记录。一个索引顺序文件的变体是B-tree。