外存的组织方式

文件是存放在磁盘上的，而磁盘是以盘块为基本的分配单位的，那么一个文件是怎么存放在磁盘上的呢，这就是外存的组织方式，主要有以下三种： 
（1）连续组织方式：要求为每一个文件分配一组相邻接的盘块。就好像分配一个连续的数组给文件使用一样，不过数组元素是磁盘的盘块。它的优点在于顺序访问容易，访问速度快，因为都放在相邻磁道上，寻道时间很小。缺点为容易产生外部碎片，难以知道文件长度，难以为其分配空间，不利于删除和插入记录。 
（2）链接组织方式：为每个文件分配不连续的磁盘空间，通过链接指针将一个文件的所有盘块链接在一起，由此形成链式文件结构。这种方式可以克服连续组织方式的缺点，分为隐式链接和显示链接两种形式。 
其中隐式链接的目录项需要包含文件的第一个盘块和最后一个盘块号，每一个盘块都有一个指向下一块盘块的指针（最后一个盘块除外）。但是这样只能顺序查找，速度慢。 
而现实链接指用于链接文件的各物理块的指针显式地存放在内存的一张链接表中，该表在整个磁盘中仅设置一张。而文件第一个盘块号作为文件的物理地址存放在FCB（文件控制块中，详情见文件管理一文）。而那个链接表则叫做文件分配表（FAT:file allocation table）。 
那么查找的时候，将会把该表拷贝至内存中，大大减少访问磁盘速度，提高了检索的速度。 

（3）索引组织方式：链接组织方式虽然克服了连续组织方式的弊端，但是仔细一看，我们可以发现，FAT技术并没有解决掉查找文件必须要顺序访问的问题，同时为了查找一个文件，必须将整个FAT加载到内存中，因此是需要占用内存空间的。 
其实，在打开一个文件时，只需要把该文件占用的盘块编号调入内存即可，而不是整个FAT，因此，我们可以将分配给一个文件的所有盘块号集中在一起，按顺序放入一个磁盘块中（称为索引块），这就是索引组织方式。 
索引组织方式中，分直接索引分配和多级索引分配，直接索引分配中索引盘块号就是文件内容：

二级索引中，一级索引中的盘块仍然存放索引信息，第二级索引的盘块才是真正存放文件内容： 
 

直接索引的缺点在于不能够存放大文件的信息，而多级索引大大加快大型文件的查找速度，但是启动磁盘的次数也增多，对于小文件也是如此。在Unix系统中，通常采用直接索引和多级索引混合的方式，以适应不同大小文件的空间需求。

磁盘空闲盘块的管理

在上面的外存组织方式中，为一个文件分配空闲盘块，就需要知道哪些盘块是空闲的，记录磁盘有哪些空闲盘块有以下方法： 
（1）空闲表法：为外存上所有区域建立一张空闲表，每个空闲区对应于一个空闲表项，空闲表项里面有表项的序号、空闲区的第一个盘块号、空闲盘块数等信息： 

对于空闲表法的空间分配和回收跟内存空间的动态分区分配类似，同样可以采用首次适应、最佳适应等算法，回收时，也会考虑回收区间相邻的空间，进行适当的拼接。 
（2）空闲链表法：将所有空闲盘块区拉成一条空闲链。这种方法对分配和回收比较简单，但是空闲盘块链可能会很长。 
（3）位示图法：利用磁盘空间的每一位来表示磁盘一个盘块是否空闲： 
 

位示图法的分配和回收就是把相应的位置为0或者1，这种方法占用的空间小，适合保存在内存中，就不需要每次都访问磁盘。 
（4）成组链接法：参见这篇文章：成组链接法。

提高磁盘I/O速度-磁盘高速缓存

磁盘的读取速度跟内存的读取速度相差4~6个数量级，为了提高磁盘访问速度，我们可以在内存中为磁盘盘块设置一个缓冲区，称为磁盘高速缓存，在缓冲区中保存一些盘块的副本，当有一个磁盘请求时，先在缓冲区里面查找是否有该盘块，若有，直接从缓冲区获取数据；如果没有再启动磁盘读入，并将内容送至缓冲区，以便下次访问。

廉价磁盘冗余阵列（RAID）

设置多台磁盘存储器，并行地读取磁盘内容，加快I/O速度，同时采用容错技术提高可靠性。