文件的逻辑结构
目录
参考资料：
在进行文件系统高层设计时，所涉及的是文件的逻辑结构，即如何将这些逻辑记录构成一个逻辑文件。在进行文件系统低层设计时，所涉及的是文件的物理结构，即如何将一个文件存储在外存上。
因此，在系统中的所有文件都存在着以下两种形式的文件结构：
- 文件的逻辑结构(File Logical Structure)，文件是由一系列的逻辑记录组成，用户可以直接处理数据及其结构，它独立于文件的物理特性，又称为文件组织(FileOrganization)。
用户使用且可见，软件层
- 文件的物理结构，又称为文件的存储结构。指系统将文件存储在外存上所形成的一种存储组织形式，用户不可见。文件的物理结构不仅与存储介质的存储性能有关，而且与所采用的外存分配方式有关。
系统存储且用户不可见，硬件层
无论是文件的逻辑结构，还是其物理结构，都会影响对文件的检索速度。
1 文件逻辑结构的类型
1.1 有结构文件和无结构文件
有结构文件，由一个以上的记录构成的文件，又称为记录式文件，在记录式文件中，每个记录都用于描述实体集中的一个实体，各记录有着相同或不同数目的数据项。记录的长度可分为定长和不定长两类。
无结构文件，由字符流构成的文件，又称为流式文件。文件的长度是以字节为单位的。对流式文件的访问，则是利用读、写指针来指出下一个要访问的字符。可以把流式文件看做是记录式文件的一个特例：一个记录仅有一个字节。
1.2 按文件的组织方式分类
根据文件的组织方式，可把有结构文件分为三类：
- 顺序文件：指由一系列记录按某种顺序排列所形成的文件，其中的记录可以是定长记录或可变长记录。
- 索引文件：指为可变长记录文件建立一张索引表，为每个记录设置一个表项，以加速对记录的检索速度。
- 索引顺序文件：这是顺序文件和索引文件相结合的产物，这里，在为每个文件建立一张索引表时，并不是为每一个记录建立一个索引表项，而是为一组记录中的第一个记录建立一个索引表项。
2 序文件(Sequential File)
在顺序文件中的记录，可以按照各种不同的顺序进行排列。一般地，可分为两种情况：
- 第一种串结构。在串结构文件中的记录，通常是按存入时间的先后进行排序的，各记录之间的顺序与关键字无关。
按时间顺序
- 第二种顺序结构，按照关键字大小进行排序。
**顺序文件的优点：**最佳应用场合是在对文件中的记录进行批量存取时，即每次要读或写一大批记录。所有逻辑文件中顺序文件的存取效率是最高的。此外，对于顺序存储设备，也只有顺序文件才能被存储并能有效地工作。
适合批量存储，比如范围查找
**顺序文件的缺点：**不适合在交互应用的场合，对其中一条记录的查找或修改，也不适合在中间插入或删除一条记录。不适合单条记录操作
3 索引文件(lndex File)
3.1 根据关键字建立索引
定长记录的文件可以通过简单的计算，很容易地实现随机查找。但变长记录文件查找记录必须从第一个记录查起，一直顺序查找到目标记录为止，耗时很长。
所以，为变长记录文件建立一张索引表，为主文件中的每个记录在索引表中分别设置一个表项，记录指向记录的指针(即记录在逻辑地址空间的首址)以及记录的长度 L，索引表按关键字排序，因此，索引表本身也是一个定长记录的顺序文件，这样就把对变长记录顺序文件的顺序检索转变为对定长记录索引文件的随机检索，从而加快对记录检索的速度，实现直接存取。
由于是按关键字建立的索引，所以在对索引文件进行检索时，可以根据用户提供的关键字利用折半查找法去检索索引表，从中找到相应的表项。再利用该表项中给出的指向记录的指针值去访问所需的记录。而每当要向索引文件中增加一个新记录时，便须对索引表进行修改。
折半查找要求记录是顺序的
3.2 具有多个索引表的索引文件
使用按关键字建立的索引表与顺序文件一样，都只能按该关键字进行检索。而在实际情况中，不同的用户，为了不同的目的，希望能按不同的属性(关键字)来检索一条记录。为实现此要求，需要为顺序文件建立多个索引表，即为每一个关键字都配置一张索引表。在每一个索引表中，都按相应的一种属性或关键字进行排序。
多个关键字，多个索引表
检索索引文件的主要优点是，它将一个需要顺序查找的文件改造成一个可随机查找的文件，极大地提高了对文件的查找速度。
但是，它除了有主文件外，还须配置一张索引表，而且每个记录都要有一个索引项，因此增加了存储开销。
4 索引顺序文件 (ndex Sequential File)
4.1 索引顺序文件的特征
索引顺序文件是对顺序文件的一种改进，它基本上克服了变长记录的顺序文件不能随机访问，以及 不便于记录的删除和插入的缺点，它是顺序文件和索引文件相结合的产物。
索引顺序文件保留了顺序文件的关键特征，即记录是按关键字的顺序组织起来的。它又增加了两个新特征：
- 引入了文件索引表，通过该表可以实现对索引顺序文件的随机访问。
- 增加了溢出(overfow)文件，用它来记录新增加的、删除的和修改的记录。
4.2 一级索引顺序文件
首先将变长记录顺序文件中的所有记录分为若干个组，如 50 个记录为一个组。然后为顺序文件建立一张索引表，并为每组中的第一个记录在索引表中建立一个索引项，其中含有该记录的关键字和指向该记录的指针。
对记录进行分组，为分组建立索引，可减少索引表的大小
在对索引顺序文件进行检索时，首先也是利用关键字以及某种查找算法去检索索引表，找到该记录所在记录组中第一个记录的表项，从中得到该记录组第一个记录在主文件中的位置。然后，再利用顺序查找法去查找主文件，从中找到所要求的记录。
顺序索引文件的查找
4.3 两级索引顺序文件
对于一个非常大的文件，为找到一个记录而须查找的记录数目仍然很多，为了进一步提高检索效率，可以为顺序文件建立多级索引，即为索引文件再建立一张索引表，从而形成两级索引表。
建立多级索引表可以减少查找次数
5 直接文件和哈希文件
5.1 直接文件
采用前述几种文件结构对记录进行存取时，都须利用给定的记录键值，先对线性表或链表进行检索，然后找到指定记录的物理地址。
对于直接文件，则可根据给定的关键字直接获得指定记录的物理地址。换而言之，关键字本身就决定了记录的物理地址。这种由关键字到记录物理地址的转换被称为键值转换（Key to address transformation）。组织直接文件的关键在于用什么方法进行从记录值到物理地址的转换。
键值映射：关键字->物理地址
5.2 哈希(Hash)文件
目前应用最为广泛的一种直接文件。它利用 Hash 函数(或称散列函数)可将关键字转换为相应记录的地址。
但为了能实现文件存储空间的动态分配，通常由 Hash 函数所求得的并非是相应记录的地址，而是指向某一目录表相应表目的指针，该表目的内容指向相应记录所在的物理块，如下图所示。
通常，把 Hash 函数作为标准函数存于系统中，供存取文件时调用。