一、连续分配算法

原理：为文件分配连续的磁盘块，通过FCB记录起始块号和长度
优势：

• 顺序访问性能最佳（磁头移动距离最短）
• 目录结构简单，仅需存储起始地址和长度
  缺陷：
• 产生外部碎片，需定期磁盘整理
• 文件扩展困难，需预先声明大小
  案例：早期FAT32文件系统采用该方案

二、链式分配算法

实现形式：

1. 隐式链接：每个块末存储下一块指针，形成单向链表
2. 显式链接：单独建立文件分配表(FAT)集中管理指针
   优势：

• 完全消除外部碎片
• 支持文件动态增长
  缺陷：
• 随机访问需遍历链表，效率低（O(n)复杂度）
• 指针占用4-8%存储空间
  案例：Windows的FAT文件系统采用显式链接

三、索引分配算法

多级索引结构：

• 一级索引：直接指向数据块
• 二级索引：指向一级索引块
• 混合索引：结合直接/间接索引（如Unix inode）
  优势：
• 支持随机访问（O(1)复杂度）
• 大/小文件均可高效存储
  缺陷：
• 索引块占用额外空间
• 超大文件需多级索引，增加IO次数
  案例：Ext4文件系统的extent树结构

四、现代优化方案

1. 位示图管理：
2. 用二进制位表示块状态，快速定位空闲块
3. 典型应用：Linux的ext系列文件系统
4. 成组链接法：
5. 将空闲块分组，通过栈结构管理
6. 解决大型文件系统的表过长问题

五、性能对比表

以下是文件系统存储分配算法对比表，包含随机访问效率、空间利用率、扩展性及典型应用系统：

关键特性补充说明

1. 连续分配

• 优势：直接访问性能最佳（寻道时间最短）
• 缺陷：外部碎片严重，文件扩容需整体移动数据

2. 隐式链接

• 优势：动态扩展灵活，无碎片问题
• 缺陷：指针占用存储空间，故障易导致链断裂

3. 多级索引

• Ext4采用extent连续块管理，相比传统索引减少元数据开销
• NTFS通过MFT（主文件表）实现混合索引结构

4. 位示图

• Linux内核结合Btrfs/ZFS等现代文件系统，支持动态空间分配与去重

该表格综合了不同文件系统的底层存储策略与工程实践，实际性能需结合具体硬件环境评估。