一、连续分配算法
原理：为文件分配连续的磁盘块，通过FCB记录起始块号和长度
优势：
- 顺序访问性能最佳（磁头移动距离最短）
- 目录结构简单，仅需存储起始地址和长度
缺陷： - 产生外部碎片，需定期磁盘整理
- 文件扩展困难，需预先声明大小
案例：早期FAT32文件系统采用该方案
二、链式分配算法
实现形式：
- 隐式链接：每个块末存储下一块指针，形成单向链表
- 显式链接：单独建立文件分配表(FAT)集中管理指针
优势：
- 完全消除外部碎片
- 支持文件动态增长
缺陷： - 随机访问需遍历链表，效率低（O(n)复杂度）
- 指针占用4-8%存储空间
案例：Windows的FAT文件系统采用显式链接
三、索引分配算法
多级索引结构：
- 一级索引：直接指向数据块
- 二级索引：指向一级索引块
- 混合索引：结合直接/间接索引（如Unix inode）
优势： - 支持随机访问（O(1)复杂度）
- 大/小文件均可高效存储
缺陷： - 索引块占用额外空间
- 超大文件需多级索引，增加IO次数
案例：Ext4文件系统的extent树结构
四、现代优化方案
- 位示图管理：
- 用二进制位表示块状态，快速定位空闲块
- 典型应用：Linux的ext系列文件系统
- 成组链接法：
- 将空闲块分组，通过栈结构管理
- 解决大型文件系统的表过长问题
五、性能对比表
以下是文件系统存储分配算法对比表，包含随机访问效率、空间利用率、扩展性及典型应用系统：
算法类型 | 随机访问效率 | 空间利用率 | 扩展性 | 典型系统 | 技术原理 |
连续分配 | 高 | 低 | 差 | FAT32 | 文件占用连续磁盘块，通过起始块号+偏移量直接定位 |
隐式链接 | 低 | 高 | 优 | 早期DOS系统 | 离散分配磁盘块，通过链式指针串联文件块，仅支持顺序访问 |
多级索引 | 中 | 高 | 良 | Ext4/NTFS | 采用分层索引结构（如Ext4的extent树），支持大文件快速定位 |
位示图 | 极高 | 高 | 优 | Linux文件系统 | 通过bitmap标记块状态，配合B+树等结构实现高效空间管理 |
关键特性补充说明
- 连续分配
- 优势：直接访问性能最佳（寻道时间最短）
- 缺陷：外部碎片严重，文件扩容需整体移动数据
- 隐式链接
- 优势：动态扩展灵活，无碎片问题
- 缺陷：指针占用存储空间，故障易导致链断裂
- 多级索引
- Ext4采用extent连续块管理，相比传统索引减少元数据开销
- NTFS通过MFT（主文件表）实现混合索引结构
- 位示图
- Linux内核结合Btrfs/ZFS等现代文件系统，支持动态空间分配与去重
该表格综合了不同文件系统的底层存储策略与工程实践，实际性能需结合具体硬件环境评估。