1、文件逻辑结构概述文件逻辑结构概述北京交通大学计算机学院翟高寿翟高寿文件逻辑结构及设计要求提高检索效率文件记录或数据检索速度及效率方便修改文件记录或数据的增、删、修改降低文件存储成本减少文件占用存储空间北京交通大学计算机学院翟高寿文件逻辑结构的类型有结构文件（记录式文件）定长记录和不定长记录顺序文件索引文件索引顺序文件无结构文件（字符流文件或称之为流式文件）基于读写指针和字符进行存取北京交通大学计算机学院翟高寿北京交通大学计算机学院翟高寿知行合一，知行合一，开拓进取！开拓进取！文件逻辑结构概述顺序文件逻辑结构顺序文件逻辑结构及直接存取及直接存取北京交通大学计算机学院翟高寿翟高寿顺序文件逻辑记录的
2、排序 串结构与顺序结构顺序文件读写操作读写指针RWptr对应记录逻辑地址定长记录 RWptr+=recordLength变长记录 RWptr+=currentRecordLength顺序文件评析 适于批量存取及磁带介质交互应用场合单个记录查找或增删修改操作低效与关键字次序与关键字次序一致与否一致与否解决方案？解决方案？北京交通大学计算机学院翟高寿4li(lk+1)顺序文件直接存取分析R0R1R2R3Ril0lll2l3lli*ll (i+1)*lRWptrl0R0l10l0 l0+1RWptrR1liRil1 l0+l1+2i-1(lk+1)li定长记录顺序文件北京交通大学计算机学院变长记录顺
3、序文件翟高寿北京交通大学计算机学院翟高寿知行合一，知行合一，开拓进取！开拓进取！顺序文件逻辑结构及直接存取索引文件逻辑结构索引文件逻辑结构北京交通大学计算机学院翟高寿翟高寿关键字记录长度l 指针ptrkey0l0key1l1key2l2keyili索引文件组织及检索机制R0R1R2R3Ri主数据文件索引表（定长记录顺序文件）北京交通大学计算机学院翟高寿北京交通大学计算机学院翟高寿知行合一，知行合一，开拓进取！开拓进取！索引文件逻辑结构索引顺序文件逻辑结构索引顺序文件逻辑结构北京交通大学计算机学院翟高寿翟高寿姓名其它属性AnKangAnQiBaoLuoBaoRong关键字 指针ptrAnKang
4、BaoLuoChenLin索引顺序文件组织及检索机制索引表（定长记录顺序文件）北京交通大学计算机学院主数据文件翟高寿分组大小分组大小 sqrt(N)条记录条记录丼例说明(N=10000)=N 件，若 N)北京交通大学计算机学院翟高寿2、索件组织方式(N 条索引顺序文件检索效率分析1+2+3+(N-1)+N/N 对于拥有N条记录的主数据文(N+1)/(2 基于顺序查=(N+1)/2sqrt(N)+1/2+sqrt(N)+1/2=sqrt(N)+1 顺序文引文件：检索开销(10000+1)/2=5000.53、索引顺序文件：设分组大小为100条记录，共检索开销 1001条两级索引顺序文件组织方式
5、主文件分组大小 100 条记录CubicRoot(N)一级索引表分组大小 100 条记录CubicRoot(N)检索开销 151.5条1.5*CubicRoot(N)+1.5一级索引顺序文件含10000索引项,共基于多级索引的索引顺序文件主数据文件含1000000条记录,共10000分组;建立多级索引以进一步提高检索效率100分组;(100+1)/2+(100+1)/2+(100+1)/2 分组大小 1000 条记录=151.5北京交通大学计算机学院翟高寿北京交通大学计算机学院翟高寿知行合一，知行合一，开拓进取！开拓进取！索引顺序文件逻辑结构文件物理结构文件物理结构与外存分配概述与外存分配概述
6、北京交通大学计算机学院翟高寿翟高寿文件物理结构与外存分配文件物理结构（文件存储结构）文件在外存上的存储组织形式外存空间分配方法设计目标外存空间利用及文件访问速度外存分配方式与文件物理结构连续文件结构连续分配链接文件结构索引文件结构直接文件与散列文件北京交通大学计算机学院离散分配离散分配翟高寿北京交通大学计算机学院翟高寿知行合一，知行合一，开拓进取！开拓进取！文件物理结构与外存分配概述连续文件物理结构连续文件物理结构北京交通大学计算机学院翟高寿翟高寿连续文件示意图文件目录file start lengthcount 0 2tr 14 3mail 19 6list 28 4f 6 21591317
7、212529count0371115mail192327314812162024list282f610tr1418222630北京交通大学计算机学院翟高寿连续分配及连续文件组织评析外部碎片问题磁盘空间分割后形成的较小的无法存储文件的连续区紧凑方法紧凑方法主要优点顺序访问容易且速度快支持直接存取主要缺点要求有连续的存储空间，空间利用率低必须事先知道文件的长度北京交通大学计算机学院翟高寿北京交通大学计算机学院翟高寿知行合一，知行合一，开拓进取！开拓进取！连续文件物理结构链接文件物理结构链接文件物理结构北京交通大学计算机学院翟高寿翟高寿链接文件物理结构基本思想支持离散分配方式，通过盘块上的指针实现同
8、一文件多个离散盘块的链接优点评析消除了外部碎片，外存空间利用率高按需分配，且无需事先知道文件长度支持文件动态增长，方便文件增删改链接方式隐式链接/显式链接北京交通大学计算机学院翟高寿file start endjeep 9 25隐式链接示意图文件目录-1104812162024281 1059 1613172125292610 25141822263037111519232731北京交通大学计算机学院翟高寿隐式链接问题及对策主要问题只适合顺序访问，对随机存取极其低效仅通过链接指针实现离散各盘块的链接，只要其中任何一个指针出现问题，都会导致整条链的断开，所以可靠性较差为了提高检索速度和减少指针所
9、占用的存储空间，可将几个盘块组成一个簇，以簇为单位进行盘块分配缺点：内部碎片增大北京交通大学计算机学院翟高寿FAT4显式链接与文件分配表FAT6EOF11105EOF901234567891011文件控制块FCB-A盘块号文件分配表物理地址文件控制块FCB-B物理地址北京交通大学计算机学院翟高寿设定盘块大小为1KB对于1.2MB的软盘，共有盘块1.2MB/1KB=1.2K（28,212）故文件分配表表项取12位即1.5B所以FAT共需空间1.2K1.5B=1.8KB对于200MB的硬盘，共有盘块200MB/1KB=200K（216,220）故文件分配表表项取20位即2.5B所以FAT共需空间2
10、00K2.5B=500KB典型FAT文件系统类型文件分配表空间开销计算北京交通大学计算机学院翟高寿北京交通大学计算机学院翟高寿知行合一，知行合一，开拓进取！开拓进取！链接文件物理结构FAT12文件系统标准文件系统标准北京交通大学计算机学院翟高寿翟高寿FAT12文件系统标准之一文件分配表（12位表项）描述磁盘上所有数据簇的状态和位置目录（32字节表项）1.44MB软盘组织结构北京交通大学计算机学院翟高寿FAT北京交通大学计算机学院翟高寿引 12导区 件组 系织 统结 标之二FAT12文件系统标准之三FAT结构软盘空间：80磁道/盘面*18扇区/磁道*2盘面*512字节/扇区=2880扇区扇区*5
11、12字节/扇区=1440*1024字节 1.44MBFAT12合法逻辑簇号：2,0 xFF0)0 xFF0=0 x1000 16=4080北京交通大学计算机学院翟高寿FAT12文件系统标准之四目录项结构北京交通大学计算机学院翟高寿FAT12文件系统标准之五目录项属性域组织结构北京交通大学计算机学院翟高寿北京交通大学计算机学院翟高寿知行合一，知行合一，开拓进取！开拓进取！FAT12文件系统标准索引文件物理结构索引文件物理结构北京交通大学计算机学院翟高寿翟高寿索引文件示意图048121620242815913172125292610141822263037111519232731文件 file 序
12、号目录 jeep 1991610251-1-119索引块北京交通大学计算机学院翟高寿两/多级索引文件结构基本思想对于太大的文件和索引块太多时，直接用链接指针来链接索引块的方法显然是低效的，为此应引入多级索引分配方式允许文件最大长度两级索引、盘块大小1KB、盘块号占4B则一个索引块可含 1KB/4B=256个盘块号，于是两级索引最多可含256256=64K个盘块号，允许文件最大长度为64MB北京交通大学计算机学院翟高寿混合索引文件结构示意图modeowners(2)time stamp(3)sizeblock counti.addr(0)i.addr(1)i.addr(9)i.addr(10)i
13、.addr(11)i.addr(12)DataDataDataDataDataDataDataDataDataDataDataDataDataDataDataDataData北京交通大学计算机学院翟高寿混合索引文件结构详解(UNIX系统)直接寻址直接地址项存放对应文件数据的盘块的盘块号盘块大小4KB、盘块号占4B，则支持长度在4KB10=40KB以内的文件一次间接寻址i.addr(10)指向对应文件的一级索引块一级索引块可含4KB/4B=1K个盘块号，故支持长度在(4KB1K=4MB)+40KB 以内的文件多次间接寻址i.addr(11)、i.addr(12)分别指向对应文件的两级索引块和三级
14、索引块，所以支持文件长度可达(4KB1K1K1K=4TB)+(4KB1K1K=4GB)+4MB+40KB北京交通大学计算机学院翟高寿UNIX文件操作地址转换过程I.II.A.B.将字节偏移量转换为文件逻辑盘块号LogicBlk#=Offset/SizeOfBlk将逻辑盘块号转换为物理盘块号确定物理盘块号所在地址项或索引盘块确定物理盘块号所在索引盘块及位置举例说明（假定盘块大小（假定盘块大小1KB）Offset 9000B=LogicBlk#8=i.addr(8)Offset 14000B=LogicBlk#13=对应i.addr(10)的索引盘块中的第3个盘块号北京交通大学计算机学院翟高寿北京
15、交通大学计算机学院翟高寿知行合一，知行合一，开拓进取！开拓进取！索引文件物理结构直接文件和散列文件直接文件和散列文件北京交通大学计算机学院翟高寿翟高寿直接文件和散列文件 直接文件记录键值=物理地址散列文件（Hash文件）散列函数及目录表201#键值KH(K)散列函数目录表物理块号0123456201#346#块因子？实时处理文件、操作系统目录文件、编译程序变量名表北京交通大学计算机学院翟高寿北京交通大学计算机学院翟高寿知行合一，知行合一，开拓进取！开拓进取！直接文件和散列文件目录管理基本要求目录管理基本要求及文件控制块及文件控制块北京交通大学计算机学院翟高寿翟高寿目录管理功能及要求目录引入理由
16、文件的有效管理与组织要求基于文件名便能快速、准确地找到指定文件文件目录管理的功能及要求实现“按名存取”（文件名外存地址）提高目录检索速度及文件存取速度文件共享（外存保留一份文件副本）允许文件重名，以便于文件使用北京交通大学计算机学院翟高寿文件控制块基本概念文件文件控制块文件目录项文件目录文件控制块有序集合目录文件主要信息内容基本信息（文件名、物理位置、结构类型）存取控制信息（各类用户存取权限）使用信息（建立/上次修改日期及时间）当前使用信息（当前已打开该文件的进程数、是否被其它进程锁住、文件在内存是否已修改但尚未拷贝到盘上）北京交通大学计算机学院翟高寿()文件控制块长度为32字节文件名及文件扩
17、展名共11个字符对于360KB的软盘，总共含有112个FCB，故占用4KB的存储空间。目录检索开销？目录检索开销？文件112*32/512=112/16=7个盘块盘性 度北京交通大学计算机学院翟高寿FAT文件系统标准引导扇区文件分配表目录项逻辑簇号物理扇区号磁盘分区组织结构 1.44MB软盘组织结构北京交通大学计算机学院不同FAT文件系统支持的磁盘空间大小及根目录下文件数根目录下文件数？翟高寿北京交通大学计算机学院翟高寿知行合一，知行合一，开拓进取！开拓进取！目录管理基本要求及文件控制块索引结点索引结点北京交通大学计算机学院翟高寿翟高寿文件名索引结点编号文件名1文件名2文件名3索引结点的引入必
18、要性文件目录存放在磁盘上，且可能要占用大量盘块N，检索开销很大（平均盘块调入次数 N+1/2）可行性只有文件名对目录检索有用文件描述控制信息UNIX文件目录北京交通大学计算机学院索引结点（i 结点）集合翟高寿文件名和索引结点指针分别占用 目 14B和2B，文假设每次目录读取仅拷贝一个 录件目录共需占用目录检 索平均需启 个盘块，盘块到内存，则3200 16/1K=50动磁盘驱动器(1+2+3+200)引入索引结点后（目录项仅占16B）故查找一个文件平均需启动磁盘25.5+1次/200=200*(1+200)/2/200=100.5次北京交通大学计算机学院翟高寿入索引结点前（i FCB占64B）
19、文件目录 bL占用320064/1K=200点所在的盘块号start+inti 100.5索引结点检索开销分析 丼例说明 引 故根据索引结点编号、索引结点大小iL以及盘块大小 共需便可计算获得对应索引 个盘块，结故查找一个文件平均需启动磁盘 iL/bL 次磁盘索引结点与内存索引结点磁盘索引结点文件磁盘索引结点主要内容（文件主标识、文件类型、文件存取权限、文件长度、文件存取时间、文件物理地址、文件连接计数）内存索引结点文件打开时对磁盘索引结点在内存的拷贝专有内容（索引结点编号、索引结点状态、索引结点访问计数、文件所属文件系统逻辑设备号、空闲链表/散列队列指针）北京交通大学计算机学院翟高寿北京交通
20、大学计算机学院翟高寿知行合一，知行合一，开拓进取！开拓进取！索引结点目录结构演化及相关概念目录结构演化及相关概念北京交通大学计算机学院翟高寿翟高寿文件名状态位状态位物理地址文件其它属性Alpha.wpsReport.pptText.dat单级目录结构文件创建目录检索申请空目录项属性设置文件删除目录检索外存空间回收目录项回收缺点查找速度慢、丌允许重名、丌便于文件共享北京交通大学计算机学院翟高寿用户名指向用户子目录的指针ZhaiGSGaoLBShouJHBetaDeviceMisxAlphaTestReportTest两级目录结构示意图ZhaiGS用户目录ShouJH用户目录AlphaTestGa
21、oLB用户目录ReportTest主文件目录MFD北京交通大学计算机学院翟高寿Alpha/BetaDeviceMisx两级目录结构评析优点提高了目录检索速度 MFD含n个UFD，UFD最多有m个目录项，则为找到指定文件（用户指定文件（用户+文件名）文件名）最多需检索n+m个目录项；对于单级目录结构，最多需检索nm个目录项丌同用户目录下可使用相同的文件名相同的文件名丌同用户可用不同名称访问同一共享文件可用不同名称访问同一共享文件缺点?用户隔离丌便于文件共享和用户间协作北京交通大学计算机学院翟高寿ABCFEDDEFJNKLMNOHPICGH树型目录结构示意图16234512131478910111
22、51618192122201723北京交通大学计算机学院翟高寿 绝对路径名 工作目录 相对路径名树型目录结构相关概念及实现机理路径名（绝对路径名）从根目录到各数据文件之间只有唯一的通路，该路径上的全部目录文件名不数据文件名用“/”连接形成特定数据文件的路径名相对路径名 当前目录当前目录（工作目录）从当前目录开始逐级通过中间目录文件最后到达所访问数据文件的路径名称为相对路径名目录增删 目录检索作为第一步 目录删除处理方法（是否允许删除非空目录）满足目录管理的所有要求北京交通大学计算机学院翟高寿北京交通大学计算机学院翟高寿知行合一，知行合一，开拓进取！开拓进取！目录结构演化及相关概念文件存取与目录
23、查询技术文件存取与目录查询技术北京交通大学计算机学院翟高寿翟高寿文件存取及目录查询技术实现文件按名存取的基本步骤1.系统根据用户提供的文件名，对文件目录进行查询，找出该文件的文件控制块或索引结点2.按照对应文件控制块或索引结点中所记录的文件物理地址（盘块号），计算出文件在磁盘上的物理地址3.启动磁盘驱动程序，将所存取的文件读入内存进行具体读写操作目录查询技术 线性检索法（顺序检索法）和散列方法北京交通大学计算机学院翟高寿文件系统结构信息(盘块及磁盘索引结点)磁盘索引结点块 2#K#存放磁盘索引结点文件数据块(K+1)#N#存放文件数据假设盘块大小为构块所UNIX文件卷组织结1KB，索引结点占6
24、4字节，则i#索引结 系统引导点 0#在的物理盘块号为：超级块 1#北京交通大学计算机学院翟高寿1.1.4bin7dev2#14lib9etc6(2)usr8tmp6.1.19dick30erik51jim26ast45bal26.6.64grants92books60mbox81minix17src物理盘块 132目录查询举例说明:/usr/ast/mbox根目录496结点 i.addr(0)26496#盘块/usr/ast子目录3#物理盘块496#物理盘块(1)(4)132#物理盘块索引结点集结点6 i.addr(0)(3)(5)(6)结点 i.addr(0)5#物理盘块60132#盘块/
25、usr子目录1077#物理盘块1077(7)北京交通大学计算机学院翟高寿北京交通大学计算机学院翟高寿知行合一，知行合一，开拓进取！开拓进取！文件存取与目录查询技术文件共享概念与早期技术文件共享概念与早期技术北京交通大学计算机学院翟高寿翟高寿文件共享概念及必要性概念指系统应允许多个用户（进程）共享同一份文件，从而在系统中只需保存该共享文件的一个副本即可必要性如果系统不能提供文件共享功能，就意味着凡是需要该文件的用户，都须各自备有此文件的副本，因此必然会造成存储空间的极大浪费北京交通大学计算机学院翟高寿ABCFEDABDJMKACGAJNAH绕弯路法162345121314789101115161
26、718202119 3F17J:*E J 3F9A:*CA(相对/绝对)路径北京交通大学计算机学院翟高寿1ABCFEDABDJNKJMKAHFACGA连访法62345121378149101115161718202119ba 3F17J:K(b)3F(D)9A:*D F(a)连访属性及用户计数北京交通大学计算机学院翟高寿0 1 2 3 4 5 6 7 8 9 Mist7Alpha6Report8Oaf9 Sqrt5Beta6 Zhang3Wang4符号名 ID基于基本文件目录实现文件共享ID基本文件目录空闲文件目录基本文件目录空闲文件目录主文件目录用户符号文件子目录Zhang用户符号文件子目录
27、WangSqrtBeta(Wang)/Alpha(Zhang)MistReportOaf符号名 IDID符号名其它 物理信息 位置北京交通大学计算机学院翟高寿北京交通大学计算机学院翟高寿知行合一，知行合一，开拓进取！开拓进取！文件共享概念与早期技术基于索引结点或符号链基于索引结点或符号链的文件共享方法的文件共享方法北京交通大学计算机学院翟高寿翟高寿法1：FCB在不同目录文件中的拷贝 举例：Linux硬链接及处理方案 一旦文件发生改变，则一致性难以保证法2：符号目录与索引结点相结合cat YLJFile基于索引结点的文件共享用户C目录用户C目录用户B目录用户B目录Owner=CCount=1链接
28、前Owner=CCount=2链接后Owner=CCount=1拥有者删除文件后文件删除否？基于文件目录建立文件共享关系ln DataFile.txt YLJFilerm DataFile.txt 指针悬空问题北京交通大学计算机学院翟高寿仅 Linux 含 软链接举例：件的路径名即符号链文件 DataFile.txt 根据文件类型区别处理只有文件主才拥有其索引结点的指针，从而避免cat RLJFile基于符号链的文件共享可用于链接网络中任何地方计算机中的文件系统开销问题文件操作多次读盘与磁盘启动 符号链索引结点及文件空间开销 整个文件系统遍历操作的复杂度和工作量加大整个文件系统遍历操作的复杂度
29、和工作量加大LINK类型文件 包 被共享文评析rm DataFile.txt了指针悬空问题北京交通大学计算机学院翟高寿北京交通大学计算机学院翟高寿知行合一，知行合一，开拓进取！开拓进取！基于索引结点或符号链的文件共享方法文件间数据一致性控制文件间数据一致性控制北京交通大学计算机学院翟高寿翟高寿数据的一致性问题当一个数据被分别存储到多个文件中时，便会出现数据的一致性问题商品进价（流水账、付费帐、分类账、总帐），修改中系统发生故障硬件支持-稳定存储器理论上不会出现故障和错误而实际上高度可靠的存储器系统采用冗余技术，即将一份信息同时驻留在多个独立的非易失性的存储器上北京交通大学计算机学院翟高寿事务概
30、念及恢复算法事务的定义用于访问和修改各种数据项的一个程序单位可分散在多个文件中“原子性”特征（提交操作/夭折操作）事务记录事务记录表（运行记录）事务名、数据项名、旧值、新值、恢复算法（两个核心过程）已完成事务Redo(Ti)/夭折事务Undo(Ti)发生故障时，清理在此之前所发生的事务北京交通大学计算机学院翟高寿检查点及恢复算法改进检查点作用事务记录清理工作经常化（事务记录表和已修改数据输出到稳定存储器），减少恢复开销每当出现一条记录记录时，执行恢复操作恢复算法改进查找事务记录表，确定在最近检查点以前开始执行的最后事务Ti针对Ti以后开始执行以后开始执行的事务集T中的事务Tk区别不同情况分别执
31、行恢复操作Redo(Tk)/Undo(Tk)发生故障或检查点时执行恢复算法北京交通大学计算机学院翟高寿并发控制用于实现事务顺序性的技术利用互斥锁来实现顺序性共享对象互斥锁简单易行，但效率不高效率不高利用互斥锁互斥锁和共享锁共享锁来实现顺序性共享文件具有只允许一个事务去写但却允许多个事务同时读的特点类似于读者与写者问题解决方案北京交通大学计算机学院翟高寿北京交通大学计算机学院翟高寿知行合一，知行合一，开拓进取！开拓进取！文件间数据一致性控制重复数据一致性问题重复数据一致性问题及检查方法及检查方法北京交通大学计算机学院翟高寿翟高寿重复文件的一致性为保证文件系统的可用性，应为系统中的关键文件设置多个
32、重复拷贝目录项（文件名）多个索引结点号当一个文件拷贝发生修改时，其它的文件拷贝也应做同样的修改，以保证文件中数据的一致性对策：1、直接根据索引结点找到所有拷贝位置和进行修改；2、为新修改的文件建立同样多份拷贝和替换原有文件拷贝北京交通大学计算机学院翟高寿盘块号一致性的检查盘块使用情况空闲盘块表（链）与文件数据盘块对策：构建基于盘块号的两个计数器，分别就空闲盘块号和数据盘块号进行计数，正常情况下，对应每个盘块号的空闲盘块号计数值和数据盘块号计数值应当互补，否则出错北京交通大学计算机学院翟高寿盘块号计数器组0123456789101112131415空闲盘块计数器组数据盘块计数器组11010111
33、100111000000100001100011盘块号计数器组0123456789101112131415空闲盘块计数器组数据盘块计数器组11011011100111000010010001100011正常情况与盘块丢失举例北京交通大学计算机学院翟高寿盘块号计数器组0123456789101112131415空闲盘块计数器组数据盘块计数器组11011011100111000010020001100011盘块号计数器组0123456789101112131415空闲盘块计数器组数据盘块计数器组11012111100111000010000001100011空闲/数据盘块号重复出现举例北京交通大学计算机学院翟高寿链接数一致性的检查Unix类型文件目录目录项索引结点号共享文件索引结点号在目录中出现的次数应当与其索引结点中的共享用户（进程）计数值相同对策：通过目录遍历构造一张计数器表，为每个文件建立一个表项以记录其索引结点号的计数值北京交通大学计算机学院翟高寿北京交通大学计算机学院翟高寿知行合一，知行合一，开拓进取！开拓进取！重复数据一致性问题及检查方法
