目录结构与文件分配

目录是什么？

目录（Directory） 本质上是一个特殊的文件——它的内容是<文件名, inode 号>的映射表。

目录" /home/user "的内容（简化）：
┌──────────────┬───────┬──────────────┐
│ 文件名        │ inode │ 类型          │
├──────────────┼───────┼──────────────┤
│ .             │ 123   │ 目录（自身）   │
│ ..            │ 100   │ 目录（父目录）  │
│ hello.txt    │ 456   │ 普通文件      │
│ photos/      │ 789   │ 目录          │
│ main.c       │ 321   │ 普通文件      │
└──────────────┴───────┴──────────────┘

🏫 类比：图书馆的索引卡片 图书馆的目录柜（目录文件）里有一张张卡片（目录项），每张卡片写着一本书的名字（文件名）和它的书架位置（inode 号）。你查卡片找到位置，然后去书架上拿书。

目录的实现方式

简单方式：线性列表

目录文件的内容就是一系列固定长度的条目：

| inode | 文件名（16字节） | 文件类型 | ... |
|-------|-----------------|---------|-----|
| 456   | hello.txt\0...  | file    | ... |
| 789   | photos\0......  | dir     | ... |

缺点：查找需要线性扫描——目录文件越大越慢。

现代方式：哈希表 / B 树

Linux ext4 用 哈希树（HTree） 加速大目录查找：

目录项按文件名哈希值组织成 B 树结构
查找 "hello.txt" → 计算哈希值 → B 树搜索 → O(log n)

💡 这就是为什么一个目录下有几十万个文件也不影响查找速度——小目录直接线性扫描，大目录自动启用 HTree 索引。

目录结构：从根到叶子

/                    ← 根目录（root）
├── bin/             ← 系统命令（ls, cp, mv）
│   ├── ls
│   ├── cp
│   └── ...
├── etc/             ← 配置文件
│   ├── passwd
│   ├── fstab
│   └── ...
├── home/            ← 用户目录
│   └── user/
│       ├── docs/
│       ├── photos/
│       └── main.c
├── dev/             ← 设备文件（一切皆文件）
│   ├── sda
│   ├── tty
│   └── ...
└── proc/            ← 进程信息虚拟文件系统
    ├── 1234/
    └── ...

绝对路径 vs 相对路径

# 绝对路径——从根 / 开始
cd /home/user/docs

# 相对路径——从当前工作目录开始
cd docs

每个进程有一个当前工作目录（CWD）——pwd 查看，cd 修改。

路径解析

输入路径：/home/user/main.c

1. 从根目录 / 的 inode 开始
2. 在 / 的目录中查找 "home" → inode 100
3. 访问 inode 100 → 读取目录数据 → 查找 "user" → inode 200
4. 访问 inode 200 → 读取目录数据 → 查找 "main.c" → inode 300
5. 访问 inode 300 → 文件内容！

文件分配策略

磁盘空间怎么分配给文件？有三种基本策略：

1. 连续分配

每个文件占用磁盘上一段连续的空间。

文件 A（占块 2-5）：
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ A0│ A1│ A2│ A3│   │   │ ...
└───┴───┴───┴───┴───┴───┴───┴───┘

优点：顺序读性能极好（磁盘不需要寻道）
缺点：外部碎片——删除文件后留下空洞

2. 链式分配

每个数据块中包含指向下一个块的指针。

文件 A：
块 7 → 块 3 → 块 12 → 块 5 → end
  ↓      ↓      ↓      ↓
数据    数据    数据    数据
+指针   +指针   +指针   +指针

优点：无外部碎片
缺点：随机访问慢（要顺着链找），指针占空间

3. 索引分配（ext4 等主流文件系统）

每个文件有一个索引块（inode），包含指向所有数据块的指针。

inode 的块指针数组：
[0]  → 块 7
[1]  → 块 3
[2]  → 块 12
[3]  → 块 5
...

优点：随机访问快（直接索引），无碎片
缺点：小指针数组对大文件不够用 → 多级索引

💡 ext4 使用**区段（Extent）**代替块指针——一个 extent 可以表示一段连续的块范围（起始块 + 长度），减少了指针数量。对于大文件，extent 比指针数组高效得多。

空闲空间管理

文件系统需要跟踪哪些块是空闲的：

位图法（主流方式）

用一位（bit）表示一个块是否空闲：

位图（每 1 位 = 1 个块）：
块 0  1  2  3  4  5  6  7  8  9 ...
1  1  0  1  0  0  1  1  0  0 ...

1 = 已用，0 = 空闲

分配：在位图中找到第一个 0，设为 1，返回块号。 释放：在位图中设对应位为 0。

空闲链表

把所有空闲块用链表串起来——Linux 早期的 ext2 用过，现在已淘汰。

目录操作的系统调用

#include <stdio.h>
#include <sys/stat.h>
#include <dirent.h>
#include <unistd.h>

int main() {
    // 创建目录
    mkdir("mydir", 0755);
    
    // 遍历目录
    DIR* dir = opendir(".");
    struct dirent* entry;
    while ((entry = readdir(dir)) != NULL) {
        printf("  %s (inode: %lu)\n", entry->d_name, entry->d_ino);
    }
    closedir(dir);
    
    // 删除文件
    unlink("oldfile.txt");
    
    // 删除目录（必须为空）
    rmdir("emptydir");
    
    return 0;
}

输出示例：

  . (inode: 12345)
  .. (inode: 10000)
  hello.txt (inode: 45678)
  mydir (inode: 78901)

小结

概念	要点
目录	文件名→inode 的映射表
路径解析	按 / 分割，逐级查找目录
连续分配	性能好，有碎片
索引分配	ext4 等主流文件系统使用
空闲空间	位图管理，O(1)分配释放
硬链接	多个目录项指向同一 inode

为什么先学这个？ 理解了目录和分配策略，你就知道文件在磁盘上是怎么”摆放”的了。下一节看看磁盘调度——操作系统如何优化对机械硬盘的访问。