一、文件的逻辑结构
类似于数据结构的“逻辑结构”和“物理结构”。①、如“线性表”就是一种逻辑结构,在用户角度看来,线性表就是一组有先后关系的元素序列,如:a,b, c, d, e ……
②、“线性表”这种逻辑结构可以用不同的物理结构实现,如:顺序表/链表。顺序表的各个元素在逻辑上相邻,在物理上也相邻;而链表的各个元素在物理上可以是不相邻的。因此,顺序表可以实现“随机访问”,而“链表”无法实现随机访问。
③、可见,算法的具体实现与逻辑结构、物理结构都有关(文件也一样,文件操作的具体实现与文件的逻辑结构、物理结构都有关)
(二)无结构文件
按文件是否有结构分类,可以分为无结构文件、有结构文件两种。无结构文件:文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。如:Windows 操作系统中的 .txt 文件。文件内部的数据其实就是一系列字符流,没有明显的结构特性。(三)有结构文件
有结构文件:由一组相似的记录组成,又称“记录式文件”。每条记录又若干个数据项组成。如:数据库表文件。一般来说,每条记录有一个数据项可作为关键字(作为识别不同记录的ID)根据各条记录的长度(占用的存储空间)是否相等,又可分为定长记录和可变长记录两种。
1. 顺序文件
顺序文件:文件中的记录一个接一个地顺序排列(逻辑上),记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储。2. 索引文件
3. 索引顺序文件
(1)索引顺序文件(检索效率分析)
若一个顺序文件有10000个记录,则根据关键字检索文件,只能从头开始顺序查找(这里指的并不是定长记录、顺序结构 的顺序文件),平均须查找 5000 个记录。若采用索引顺序文件结构,可把 10000 个记录分为 √10000 = 100 组,每组 100 个记录。则需要先顺序查找索引表找到分组(共100个分组,因此索引表长度为 100,平均需要查 50 次),找到分组后,再在分组中顺序查找记录(每个分组100 个记录,因此平均需要查 50 次)。可见,采用索引顺序文件结构后,平均查找次数减少为 50+50 = 100 次。同理,若文件共有 106个记录,则可分为 1000 个分组,每个分组 1000 个记录。根据关键字检索一个记录平均需要查找 500+500 = 1000 次。这个查找次数依然很多,如何解决呢?(2)多级索引顺序文件
为了进一步提高检索效率,可以为顺序文件建立多级索引表。例如,对于一个含 106个记录的文件,可先为该文件建立一张低级索引表,每 100 个记录为一组,故低级索引表中共有 10000 个表项(即10000个定记录),再把这 10000 个定长记录分组,每组100个,为其建立顶级索引表,故顶级索引表中共有 100 个表项。二、文件目录
(一)文件控制块
当我们双击“照片”后,操作系统会在这个目录表中找到关键字“照片”对应的目录项(也就是记录),然后从外存中将“照片”目录的信息读入内存,于是,“照片”目录中的内容就可以显示出来了。FCB 的有序集合称为“文件目录”,一个FCB就是一个文件目录项。FCB 中包含了文件的基本信息(文件名、物理地址、逻辑结构、物理结构等),存取控制信息(是否可读/可写、禁止访问的用户名单等),使用信息(如文件的建立时间、修改时间等)。最重要,最基本的还是文件名、文件存放的物理地址。FCB 实现了文件名和文件之间的映射。使用户(用户程序)可以实现“按名存取”需要对目录进行哪些操作?
①、搜索:当用户要使用一个文件时,系统要根据文件名搜索目录,找到该文件对应的目录项
②、创建文件:创建一个新文件时,需要在其所属的目录中增加一个目录项
③、删除文件:当删除一个文件时,需要在目录中删除相应的目录项
④、显示目录:用户可以请求显示目录的内容,如显示该目录中的所有文件及相应属性
⑤、修改目录:某些文件属性保存在目录中,因此这些属性变化时需要修改相应的目录项(如:文件重命名)