OS之文件逻辑结构

什么是逻辑结构

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

无结构文件

• 无结果文件就是文件内部的数据就是一系列二进制或者字符流组成的

有结构文件

• 由一组相似的记录组成，又称记录式文件，每条记录又若干个数据项组成
  • 而且一般来说，每条记录有一个数据项可作为关键字（分别不同记录的ID）
• 根据我们记录的长度固定不固定
  • 定长记录
  • 不定长记录

有结构文件的逻辑结构

顺序文件

• 顺序文件：文件中的记录一个接一个地顺序排序（逻辑上），记录可用是定长或者是不定长的，各个记录在物理上可以是顺序存储或者链式存储的
• 按照我们记录之间的顺序跟关键字的关系分为两类
  • 串结构 记录之间的顺序与我们的关键字无关
  • 顺序结构 记录之间的顺序按关键字顺序排列

• 如果我们的顺序文件（在逻辑上是按顺序的）,如果物理上实现是靠链式存储，那么无论无何都无法实现随机存取，只能从第一个记录开始依次往后找
• 如果是物理上按照顺序存储
  • 可变成记录：无法实现随机存取 对于可变长的记录，因为记录的长度不固定，所以需要记录每个记录的长度来区分开我们的记录
  • 定长记录
    • 可以实现随机存取
    • 若采用了串结构，无法快速找到某关键字对应的记录
    • 若采用了顺序结构，因为记录按照关键字的顺序存储，所以可以快速找到某个关键字对应的记录

索引文件

• 对于我们索引表本身是一个定长记录的顺序文件（顺序文件指的在物理上也是顺序存储的）
• 我们还可以在对于关键字上采用顺序结构（按照我们的关键字顺序存储），这样还可以支持对关键字的折半查找

索引顺序文件

• 对应我们的索引文件，每一个记录对应了一个索引表项，因此索引表可能会很大
• 索引顺序文件就是索引文件和顺序文件思想的结合，索引顺序文件中，同样为文件建立一张索引表，但是不同的是，并不是每个记录对应一个索引表项**，而是一组记录对应一个索引表项**
• 每个分组就是一个顺序文件，分组内的记录不需要关键字排序

多级索引顺序文件