文件的逻辑结构（顺序文件，索引文件）

所谓的“逻辑结构”，就是指在用户看来，文件内部的数据应该是如何组织起来的。
而“物理结构”指的是在操作系统看来，文件的数据是如何存放在外存中的。

1.无结构文件

无结构文件:文件内部的数据就是一系列二进制流或字符流组成。无明显的逻辑结构。
又称“流式文件”。如:Windows操作系统中的.txt文件。

2.有结构文件

有结构文件:由一组相似的记录组成，又称“记录式文件”。
每条记录又若干个数据项组成。如:数据库表文件。
一般来说，每条记录有一个数据项可作为关键字。
根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种。

1.顺序文件

顺序文件:文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。
各个记录在物理上可以顺序存储或链式存储。

• 顺序存储：逻辑上相邻的记录物理上也相邻（类似于顺序表)
• 链式存储：逻辑上相邻的记录物理上不一定相邻(类似于链表）
• 串结构：记录之间的顺序与关键字无关。
• 顺序结构：记录之间的顺序按关键字顺序排列。

1.链式存储

无论是定长/可变长记录，都无法实现随机存取，每次只能从第一个记录开始依次往后查找

2.顺序存储

1. 可变长记录

无法实现随机存取。每次只能从第一个记录开始依次往后查找

2. 定长记录

可实现随机存取。记录长度为L，则第i个记录存放的相对位置是i*L。
若采用串结构，无法快速找到某关键字对应的记录。
若采用顺序结构，可以快速找到某关键字对应的记录（如折半查找)。

结论:
定长记录的顺序文件，若物理上采用顺序存储，则可实现随机存取;
若能再保证记录的顺序结构，则可实现快速检索(即根据关键字快速找到对应记录).

顺序文件的缺点是增加/删除一个记录比较困难（如果是串结构则相对简单).

2.索引文件

建立一张索引表以加快文件检索速度。每条记录对应一个索引项。
索引表本身是定长记录的顺序文件。因此可以快速找到第i个记录对应的索引项。

可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。

每当要增加/删除一个记录时，需要对索引表进行修改。
由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。

3.索引顺序文件

索引顺序文件是索引文件和顺序文件思想的结合。
索引顺序文件中，同样会为文件建立一张索引表，但不同的是:并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。

索引顺序文件的索引项也不需要按关键字顺序排列，这样可以极大地方便新表项的插入。

1.检索效率分析

1. 若一个顺序文件有10000个记录，则根据关键字检索文件，只能从头开始顺序查找（这里指的并不是定长记录、顺序结构的顺序文件)，平均须查找5000个记录。
2. 若采用索引顺序文件结构，可把10000个记录分为100组，每组100个记录。
   则需要先顺序查找索引表找到分组(共100个分组，因此索引表长度为100，平均需要查50次），
   找到分组后，再在分组中顺序查找记录（每个分组100个记录，因此平均需要查50次）。
   可见，采用索引顺序文件结构后，平均查找次数减少为50+50= 100次。

4.多级索引顺序文件

为了进一步提高检索效率，可以为顺序文件建立多级索引表。
例如，对于一个含$10^6$个记录的文件，可先为该文件建立一张低级索引表，
每100个记录为一组，故低级索引表中共有10000个表项（即10000个定长记录），
再把这10000个定长记录分组，每组100个，为其建立顶级索引表，故顶级索引表中共有100个表项。