目录查询技术-线性检索法（顺序检索法）
\usr\ast\mbox1.1..4bin7Dev14Lib9Etc6Usr8tmp根目录132结点6是\usr的目录6.1..19Dick30Erik51Jim26Ast45bal132#块是\usr的目录结点26是\usr\ast目录49626.6..64grants92books60mbox81minix17src496#块是\usr\ast目录*目录查询技术-Hash方法建立一个Hash索引文件目录，系统利用用户提供的文件名，将它变换为文件目录的索引值，再利用该索引值到目录中去查找，从而找到文件的物理地址。注：1）当文件名中用了*，？时，系统无法利用Hash法检索目录，这时须用线性检索法查找目录。2）在Hash法中须对“冲突”进行处理。3）若在Hash索引文件目录中查询时，相应的目录项为空，则表“文件未找到”。返回*6.5文件存储空间管理如何为新建的文件分配存储空间 连续分配方式 离散分配方式1.空闲表法和空闲链表法2.位示图法3.成组链接法*1.空闲表法和空闲链表法空闲表法是一种连续分配方法。序号起始空闲盘块号空闲盘块数目12621233207分配方法回收方法首次适应循环首次适应最佳适应最坏适应*1.空闲表法和空闲链表法空闲链表法将所有空闲盘组织成一条空闲链空闲盘块链空闲盘区链*2.位示图法利用二进制的一位来表示磁盘中一个盘块的使用情况。1234567……n111100010200111001……m*2.位示图法盘块的分配顺序扫描位示图，从中找出一个或一组值为0的二进制位。根据找到的二进制位的行列数，转换成与之相应的盘块号：b=n(i-1)*j。修改位示图：map[i][j]=1。*2.位示图法盘块的回收根据回收的盘块号，转换成位示图中相应的行号和列号：i=(b-1)/n+1j=(b-1)%n+1修改位示图：map[i][j]=0。*2.位示图法优点查找空闲块容易；占用空间少；速度快。*3.成组链接法*本章作业1、P247第24题2、设某系统磁盘共有1600块，块号从0-1599，若用位示图管理这1600块磁盘空间，问位示图需要多少个字节？3、假定盘块的大小为1KB，硬盘的大小为500MB，采用显式链接分配方式时，其FAT（32位）需占用多少存储空间？*索引文件的特点优点通过索引表可方便地实现直接存取，具有较快的检索速度。易于进行文件的增删。缺点索引表的使用增加了存储费用；索引表的查找策略对文件系统的效率影响很大。若索引表很大怎么办？*4.索引顺序文件为解决变长记录文件的直接存取低效且存储费用增加的问题。为顺序文件建立一张索引表。索引号长度m指针ptr0m01m1…imi…r0r1…ri…逻辑文件索引表*索引顺序文件的特点通过索引表可方便地实现直接存取，具有较快的检索速度。易于进行文件的增删。*6.3外存分配方式文件存储单位：簇（cluster）文件的存储空间通常由多个分立的簇组成，而每个簇包含若干个连续的扇区(sector)/块。目前常用的外存分配方法：1.连续分配（顺序分配）2.链接分配3.索引分配*1.连续/顺序分配Figure6-7为每一个文件分配一片连续的磁盘块/簇只需要起始块/簇号和长度，适用于预分配方法可以随机存取文件不能增长从逻辑地址映射到物理地址较简单浪费空间：动态存储分配问题可以通过紧缩(compact)将外存空闲空间合并成连续的区域。*连续/顺序分配的主要优缺点主要优点顺序访问容易顺序访问速度快缺点要求有连续的存储空间必须事先知道文件的长度存在外部碎片*2.链接分配Figure6-8每个文件是一个磁盘块的链接列表：块可以分散在磁盘各处按所需分配磁盘块，链接在一起在每个块中有指向下一个块的指针只需要起始地址可以通过合并(consolidation)将一个文件的各个簇连续存放，以提高I/O访问性能。block=pointer*链接分配的优点1)无外部碎片，没有磁盘空间浪费2)无需事先知道文件大小。文件动态增长时，可动态分配空闲块。对文件的增、删、改十分方便。3)不需紧缩磁盘空间。*链接分配的