Re：从零开始的文件结构（融合线性表来理解 考研向）

文件管理

文件的结构

无结构文件

有结构文件（重点）

定长与不定长记录

• 定长记录：
  
• 不定长记录
• 其实这个东西就可以类比于我们在学习线性表中所解决的稀疏多项式问题，也就是一旦当数组当中的某些项的差异比较大的时候，我们如果还是采用定长记录的方式就会使得存储空间的利用率大大下降，
• 例如下图，有的同学没有特长有的同学特长却非常多
  

顺序文件（类线性表）

它的逻辑结构

而这里所提到的关键字可以看做是一个特征 这个特征唯一可以标识每个数据项（结点）
eg:就像上面的校园管理系统的例子中，我们的关键字就是学号，为什么不选择姓名 作为我们的关键字呢，因为在一个庞大的校园里面很有可能出现重名的情况，而现在我们说的是单级目录，单级目录是不允许有重复项出现的

• “顺序结构” 通常指线性结构（数据元素按线性关系排列，如线性表）
• “串结构” 是特殊的线性结构（数据元素仅为字符，如字符串）。

它的物理结构（存储结构）

类似于我们顺序表 我们对于它的存储结构可以分为链式存储（链表）和顺序存储（数组）
当然 对于链式存储 不论采用上面哪种记录方式 我们都得首元结点开始寻找，但是如果要进行增删目录是比较方便的

来看顺序存储结合我们前面提到的两种记录方式 ：

定长记录下：

• 我们最理想的状态就是采取顺序存储的定长记录方式，这样一来就可以拥有了数组的一大优势，随机存取，我们只需要知道首地址我们就可以根据每个记录长度（数组每个元素的大小）以O(1)的时间来得到目标元素的位置
• 当前进一步采用顺序结构（逻辑结构），那么我们是不是此时是不是就可以将它看做一个有序的数组，此时如果给定关键字（学号）我们是不是就可以采用二分查找的快速锁定对应的记录在这个目录的位置呢
• 但是进一步采用串结构是不能做到快速查找这点的 具体原因如下（了解）：
• 串是 “字符序列” 的逻辑结构，没有 “元素包含关键字” 的逻辑设计，缺乏 “关键字→元素” 的映射基础；
• 串的操作围绕字符序列处理，而非关键字的高效检索，无法支持快速查找所需的索引或映射机制；
• 关键字目录的本质是 “基于唯一标识的元素索引”，这与串结构的设计目标（处理字符序列）完全不匹配

可变长记录下：

• 那么如果是可变长记录那么就可以联想到我们稀疏多项式的情况 这个时候由于采取的是可变长记录方式我们并不知道每个记录内容的长度，所以我们必须得一个一个顺序的找

小结

索引顺序文件与多级索引顺序文件

形象化理解（很清晰）

• 对于单级：
  
• 对于多级索引：
  

结语

我觉得如果想要学好文件这一章，需要扎实的数据结构基础，而这一章跟前面我们刚刚学习的基本存储管理方式又有很多相似之处，
所以我建议把前面一章消化吸收之后 再来学这一章的内容更为合适一些 我感觉操作系统当中很多知识的大体框架都是差不多的 甚至于介绍顺序和前因后果都差不多 只不过应用于不同的方面罢了 、
下一篇我会更新文件目录部分 如果弄清楚了前面的多级页表和DS当中的树 会更好理解一些
******************************************************************************************* signed by 曦月逸霜