外存组织方式.ppt

目前常用的外存分配方法有：目前常用的外存分配方法有：（（1 1）连续组织方式）连续组织方式（（2 2）链接组织方式）链接组织方式（（3 3）索引组织方式）索引组织方式8.1 外存的组织方式外存的组织方式8.1.1　连续组织方式　连续组织方式①①要求为每一个文件分配一组相邻接的盘块要求为每一个文件分配一组相邻接的盘块②②把逻辑记录中的记录，顺序地存储到邻接的各物把逻辑记录中的记录，顺序地存储到邻接的各物理盘块中，这样形成的物理文件称为理盘块中，这样形成的物理文件称为顺序文件顺序文件countcount311457282420161283291317212529610141822263011151923270mailmaillistlistf ftrtr目录目录Filecounttrmaillistfstart01419286length23642图图8-1 磁盘空间的连续组织磁盘空间的连续组织8.1.1　连续组织方式　连续组织方式•主要优点：主要优点：①①顺序访问容易顺序访问容易②②支持直接存取支持直接存取③③访问速度快访问速度快8.1.1　连续组织方式　连续组织方式①①要求有连续的存储空间。

要求有连续的存储空间②②必须事先知道文件的长度必须事先知道文件的长度③③不能灵活地删除和插入记录不能灵活地删除和插入记录④④不利于动态增长的文件不利于动态增长的文件•主要缺点：主要缺点：8.1.2　链接组织方式　链接组织方式 Linked Allocation•链接组织方式链接组织方式消除了外部碎片消除了外部碎片，故可以显著地，故可以显著地提高提高外存空间的利用率外存空间的利用率，且，且无需事先知道文件长度无需事先知道文件长度此外，文件的外，文件的插入、删除，也十分方便插入、删除，也十分方便•这样形成的物理文件称为这样形成的物理文件称为链接文件链接文件•链接方式又可分为链接方式又可分为隐式链接隐式链接和和显式链接显式链接两种方式两种方式•在文件目录的每个目录项中，都须含有指向连接文在文件目录的每个目录项中，都须含有指向连接文件第一个盘块和最后一个盘块的指针件第一个盘块和最后一个盘块的指针•在每个盘块中都含有一个指向下一个盘块的指针在每个盘块中都含有一个指向下一个盘块的指针1. 隐式链接隐式链接 Implicit Link8.1.2　链接组织方式　链接组织方式2218141062312723191511730481216202428159131721252930261 110101616-1-12525目录File start endjeep 9 25图图8-2　磁盘空间的链接组织方式磁盘空间的链接组织方式1. 隐式链接隐式链接隐式链接组织方式的主要问题隐式链接组织方式的主要问题隐式链接组织方式的主要问题隐式链接组织方式的主要问题：•只适合于顺序访问，对随机访问极其低效；•通过链接指针将一大批离散的盘块链接起来，可靠性差。

8.1.2　链接组织方式　链接组织方式1. 隐式链接隐式链接2.显式链接显式链接 Explicit Link•把把用用于于链链接接文文件件物物理理块块的的指指针针放放在在内内存存的的一一张张链链接接表表中中整个磁盘仅设置一张整个磁盘仅设置一张•表的序号是物理盘块号在每个表项中，存放链接指针表的序号是物理盘块号在每个表项中，存放链接指针•凡凡是是属属于于某某一一文文件件的的第第一一个个盘盘块块号号，，均均作作为为文文件件地地址址被被填入相应文件的填入相应文件的FCBFCB的的““物理地址物理地址””字段中 此表为此表为文件分配表文件分配表文件分配表文件分配表FATFATFATFAT（（File Allocation Table) File Allocation Table) 8.1.2　链接组织方式　链接组织方式MS-DOS的文件物理结构的文件物理结构•对于对于200MB200MB的硬盘，若盘的硬盘，若盘块的大小为１块的大小为１KB,KB,•每个表项需每个表项需2.52.5个字节，个字节，•故需占用故需占用500KB500KBFCB A2.显式链接显式链接４９FCB BFAT6 65 5EOFEOFEOFEOF1010111101234567891011图图8-3 8-3 显式链接方式显式链接方式两个问题：两个问题：•不能支持高效的直接存取。

不能支持高效的直接存取•FATFAT需占用较大的内存空间需占用较大的内存空间2.显式链接显式链接8.1.3 8.1.3 索引分配方式索引分配方式索引分配方式索引分配方式(Index Allocation)(Index Allocation)1.单级索引分配单级索引分配 索引分配方法索引分配方法为每个文件分配一索引块（表）索引块（表），把分配给该文件的所有盘块号，都记录在该索引块中在建立一个文件时，须在为之建立的目录项中，填上指向该索引块的指针 这样形成的物理文件称为这样形成的物理文件称为链接文件链接文件File 块序号 jeep 19目录91611025-1-1-119048121628242016312723191511732510141822263091317212529图图8-6 索引组织方式索引组织方式1.单级索引分配单级索引分配8.1.4 小结小结(1)连续组织方式连续组织方式• 可随机存取，访问速度快，顺序访问容易可随机存取，访问速度快，顺序访问容易• 要求连续存储空间，需事先知道文件长度要求连续存储空间，需事先知道文件长度。

2)链接组织方式链接组织方式•不要求连续存储空间，插入删除方便，无需知道文件不要求连续存储空间，插入删除方便，无需知道文件长度长度•随机存取效率低，随机存取效率低，FATFAT表占较大内存空间表占较大内存空间3)索引分配方式索引分配方式•可随机存取，不要求连续存储空间，无需知道文件长可随机存取，不要求连续存储空间，无需知道文件长度 •文件较小时浪费存储空间文件较小时浪费存储空间。