磁盘空间分配的主要常用方法有三个：连续分配、链接分配和索引分配。本文主要讨论索引分配中处理索引块大小的问题。

文件实际上是一种抽象数据类型，文件的实现就是研究文件的物理结构，即文件数据在物理存储设备上是如何分布和组织的。同一个问题有两个方面的回答：一是文件的分配方式，讲的是对磁盘非空闲块的管理；二是文件存储空间管理，将的是对磁盘空闲块的管理。


索引分配解决了连续分配和链式分配中的许多问题。对于索引分配，每个文件在文件分配表中有一个一级索引，索引包含分配给文件的每个分区入口。典型地，文件索引在物理上并不是作为文件分配表的一部分存储的，相反，文件索引保存在一个单独的块中，文件分配表中改文件的入口指向这一块。分配可以基于大小固定的块，也可以基于大小可变的块。索引分配支持顺序访问和直接访问文件，因而是最普遍的一种文件分配方式。

索引分配解决了连接分配不能有效支持直接访问（FAT除外）的问题，它把每个文件的所有的盘块号都集中放在一起构成索引块（表），如下图所示。

每个文件都有其索引块，这是一个磁盘块地址的数组。索引表记录了文件的各个逻辑块对应的物理块。索引块的第i个条目指向文件的第i个块。目录条目包括索引块的地址。要读第i块，通过索引块的第i个条目的指针来查找和读入所需的块。
创建文件时，索引块的所有项目都设为空。首次写入第i块时，先从空闲空间中取得一个块，再将其地址写到索引块的第i个条目。索引分配支持直接访问（随机访问），且没有外部碎片的问题，易于文件拓展。其缺点是由于索引块的分配，增加了系统存储空间的开销。索引块的大小是一个重要的问题，每个文件必须有一个索引块，因此需要索引块尽可能小，但索引块太小就无法支持大文件。可采用以下机制来处理这个问题。

1. 链接方案

• 一个块通常为一个磁盘块，因此它本身能直接读写。为了处理大文件，可以将多个索引块链接起来。

2. 多层索引：使第一层索引块指向第二层索引块，第二层文件块指向文件块。根据实际要求可以继续到第三层或第四层。

• 最大文件长度 = 每层索引项个数之积 × 单个文件大小；
• 每层索引表最大不能超过一个磁盘块大小；
• K层索引，顶级索引表未调入内存，则访问K级索引需要K+1次读磁盘。
  【注：文件分配方式之链接分配的隐式分配，读入i号逻辑块，总共需要i+1次读磁盘I/O操作】

3. 混合索引：多重索引分配方式相结合。
   • UNIX的文件系统采用三级索引机制。在文件控制块（FCB）中，设置了一个索引表，共有13个索引地址。其中，前10个为直接索引地址，后3个为间接索引地址，包括1个一级索引地址、1个二级索引地址和1个三级索引地址。
   • 每一块中能记录的数据块数=512/4≈128
     一级索引时文件最大长度的字节数 = 128 × 512
     二级索引时文件最大长度的字节数 = 128×128 × 512
     三级索引时文件最大长度的字节数 = 128×128×128 × 512
     最大搜索文件的长度 = (10 + 128 + 128×128 + 128×128×128) × 512
     
     与多层索引方式不同，混合索引有个主索引表（13个地址项）【主索引表是索引节点的一部分】，若题目告知主索引表在内存中【主索引表在FCB中，FCB在内存中】，访问k级间址需要读磁盘k+1次（读取数据块1次）；若主索引表不在内存中，访问k级间址需要读磁盘k+2次。
     而多层索引没有主索引表，因此相当于直接从混合索引的一级间址开始读磁盘，故k层索引读磁盘k+1次。
     【以上是使用索引结点的次数】
     注：
     • 与单个文件长度无关的因素：索引结点的总数【索引结点个数仅与文件个数有关，一个索引结点对应一个文件】
     • 一个盘块号就有一个索引项
     • 将文件描述信息从目录项中分离出来，有利于减少查找文件时的I/O信息量
     • 各级索引表最大不能超过一个块
     • 判断读磁盘次数时，注意顶级索引块是否已调入磁盘
       文件物理地址指的就是主索引表的始址

       例题：

       
       
       
       如有错误，欢迎指正！