目录结构
目录结构是文件系统组织和管理文件的重要方式。通过合理的目录结构，用户可以高效地组织、查找和管理文件。本章将详细介绍各种目录结构类型及其特点。
目录的基本概念
什么是目录
**目录（Directory）**是文件系统中用于组织和分类文件的特殊文件，它包含其他文件和子目录的引用信息。目录本身也是一种文件，但具有特殊的结构和功能。
目录的作用
- 文件组织：将相关文件组织在一起，便于管理
- 命名空间管理：避免文件名冲突
- 访问控制：为目录及其内容设置统一的访问权限
- 路径导航：提供文件定位的路径信息
目录结构类型
1. 单级目录结构
单级目录结构是最简单的目录组织方式，所有文件都放在同一个目录下。
特点
- 简单性：结构简单，易于理解
- 快速访问：所有文件在同一层级，访问速度快
- 实现简单：文件系统实现相对简单
缺点
- 命名冲突：不同用户可能使用相同的文件名
- 管理困难：文件数量多时难以管理
- 安全性差：无法为不同用户提供隔离
示例
根目录
├── file1.txt
├── file2.txt
├── program1.exe
├── program2.exe
├── user1_data.dat
└── user2_data.dat
适用场景
- 简单的嵌入式系统
- 早期操作系统
- 文件数量较少的系统
2. 两级目录结构
两级目录结构在根目录下为每个用户创建独立的目录，解决单级目录的命名冲突问题。
特点
- 用户隔离：每个用户有独立的目录空间
- 命名安全：不同用户的文件不会产生命名冲突
- 权限管理：可以为每个用户目录设置不同的权限
结构示例
根目录
├── user1/
│ ├── file1.txt
│ ├── program1.exe
│ └── data1.dat
├── user2/
│ ├── file2.txt
│ ├── program2.exe
│ └── data2.dat
└── system/
├── kernel.exe
└── config.ini
实现方式
// 简化的两级目录结构实现
struct directory_entry {
char name[32];
int user_id;
int file_type;
int file_size;
int first_block;
};
struct user_directory {
int user_id;
struct directory_entry entries[MAX_FILES];
int file_count;
};
优缺点
优点：
- 解决了命名冲突问题
- 提供了基本的用户隔离
- 实现相对简单
缺点：
- 缺乏层次化组织
- 用户间文件共享困难
- 扩展性有限
3. 树形目录结构
树形目录结构是现代操作系统最常用的目录组织方式，支持多级子目录。
特点
- 层次化组织：支持无限层级的目录嵌套
- 灵活性强：用户可以根据需要创建任意深度的目录结构
- 路径导航：通过路径可以精确定位文件
- 共享能力：支持文件在不同目录间的共享
结构示例
根目录 (/)
├── home/
│ ├── user1/
│ │ ├── documents/
│ │ │ ├── work/
│ │ │ │ ├── report1.doc
│ │ │ │ └── report2.doc
│ │ │ └── personal/
│ │ │ ├── photos/
│ │ │ └── music/
│ │ ├── downloads/
│ │ └── desktop/
│ └── user2/
│ ├── projects/
│ └── data/
├── etc/
│ ├── config/
│ └── system/
├── var/
│ ├── log/
│ └── tmp/
└── bin/
├── ls
├── cp
└── mv
路径表示
- 绝对路径：从根目录开始的完整路径
- 示例：
/home/user1/documents/work/report1.doc
- 示例：
- 相对路径：从当前目录开始的路径
- 示例：
./documents/work/report1.doc - 示例：
../user2/projects/
- 示例：
实现方式
// 树形目录结构的节点表示
struct directory_node {
char name[256];
int type; // 0: 文件, 1: 目录
struct directory_node *parent;
struct directory_node *children[MAX_CHILDREN];
int child_count;
struct file_metadata *file_info;
};
// 路径解析函数
struct directory_node* find_path(const char* path) {
char* path_copy = strdup(path);
char* token = strtok(path_copy, "/");
struct directory_node* current = root_directory;
while (token != NULL) {
current = find_child(current, token);
if (current == NULL) {
free(path_copy);
return NULL;
}
token = strtok(NULL, "/");
}
free(path_copy);
return current;
}
目录操作
// 创建目录
int mkdir(const char* path) {
struct directory_node* parent = get_parent_directory(path);
char* dir_name = get_last_component(path);
if (parent == NULL || find_child(parent, dir_name) != NULL) {
return -1; // 父目录不存在或目录已存在
}
struct directory_node* new_dir = create_directory_node(dir_name);
add_child(parent, new_dir);
return 0;
}
// 删除目录
int rmdir(const char* path) {
struct directory_node* dir = find_path(path);
if (dir == NULL || dir->type != 1 || dir->child_count > 0) {
return -1; // 目录不存在、不是目录或非空
}
remove_child(dir->parent, dir);
free_directory_node(dir);
return 0;
}
优缺点
优点：
- 支持复杂的文件组织
- 提供灵活的路径导航
- 支持文件共享和链接
- 便于权限管理
缺点：
- 实现复杂度较高
- 路径解析开销
- 需要处理循环引用问题
4. 无环图结构
无环图结构允许文件或目录被多个目录引用，形成共享关系，但不允许循环引用。
特点
- 文件共享：一个文件可以被多个目录引用
- 节省空间：共享文件只存储一份数据
- 一致性：对共享文件的修改对所有引用都可见
- 无循环：不允许形成循环引用
实现方式
硬链接（Hard Link）
// 硬链接的实现
struct inode {
int inode_number;
int link_count; // 引用计数
int file_size;
int blocks[12];
// 其他元数据...
};
// 创建硬链接
int link(const char* old_path, const char* new_path) {
struct inode* inode = get_inode(old_path);
if (inode == NULL) return -1;
// 在目标目录中创建新的目录项
struct directory_entry* entry = create_directory_entry(new_path, inode->inode_number);
if (entry == NULL) return -1;
// 增加引用计数
inode->link_count++;
return 0;
}
符号链接（Symbolic Link）
// 符号链接的实现
struct symlink_data {
char target_path[256];
int target_inode;
};
// 创建符号链接
int symlink(const char* target, const char* link_path) {
// 创建符号链接文件
struct inode* link_inode = create_file(link_path);
if (link_inode == NULL) return -1;
// 存储目标路径
struct symlink_data* data = malloc(sizeof(struct symlink_data));
strcpy(data->target_path, target);
link_inode->data = data;
link_inode->type = SYMLINK;
return 0;
}
结构示例
根目录 (/)
├── home/
│ ├── user1/
│ │ ├── documents/
│ │ │ └── shared_doc.txt ← 硬链接
│ │ └── link_to_shared -> ../user2/shared_doc.txt ← 符号链接
│ └── user2/
│ └── shared_doc.txt ← 硬链接
└── etc/
└── config -> /home/user1/documents/config ← 符号链接
硬链接与符号链接的区别
| 特性 | 硬链接 | 符号链接 |
|---|---|---|
| 存储方式 | 目录项直接指向 inode | 存储目标路径字符串 |
| 跨文件系统 | 不支持 | 支持 |
| 删除原文件 | 不影响链接 | 链接失效 |
| 空间开销 | 小 | 较大 |
| 解析速度 | 快 | 较慢 |
目录的实现
目录项结构
// 目录项的基本结构
struct directory_entry {
char name[256]; // 文件名
int inode_number; // 对应的inode号
int file_type; // 文件类型
int name_length; // 文件名长度
char padding[4]; // 填充字节
};
// 目录文件的内容
struct directory_content {
struct directory_entry entries[MAX_ENTRIES];
int entry_count;
int free_space;
};
目录操作实现
1. 目录创建
int create_directory(const char* path) {
// 1. 解析路径，找到父目录
struct inode* parent_inode = get_parent_inode(path);
if (parent_inode == NULL) return -1;
// 2. 创建新的inode
struct inode* new_inode = allocate_inode();
if (new_inode == NULL) return -1;
// 3. 初始化目录inode
new_inode->type = DIRECTORY;
new_inode->size = 0;
new_inode->link_count = 2; // . 和 ..
// 4. 在父目录中添加目录项
char* dir_name = get_last_component(path);
add_directory_entry(parent_inode, dir_name, new_inode->number);
// 5. 创建 . 和 .. 目录项
create_dot_entries(new_inode, parent_inode->number);
return 0;
}
2. 目录遍历
// 遍历目录内容
int list_directory(const char* path) {
struct inode* dir_inode = get_inode(path);
if (dir_inode == NULL || dir_inode->type != DIRECTORY) {
return -1;
}
struct directory_content* content = read_directory_content(dir_inode);
if (content == NULL) return -1;
printf("目录: %s\n", path);
printf("总条目数: %d\n", content->entry_count);
printf("\n");
for (int i = 0; i < content->entry_count; i++) {
struct directory_entry* entry = &content->entries[i];
struct inode* entry_inode = get_inode_by_number(entry->inode_number);
printf("%s\t", entry->name);
if (entry_inode->type == DIRECTORY) {
printf("DIR\t");
} else {
printf("FILE\t");
}
printf("%d bytes\n", entry_inode->size);
}
free(content);
return 0;
}
3. 路径解析
// 解析绝对路径
struct inode* resolve_path(const char* path) {
if (path[0] != '/') return NULL; // 必须是绝对路径
struct inode* current = root_inode;
char* path_copy = strdup(path);
char* token = strtok(path_copy, "/");
while (token != NULL) {
if (current->type != DIRECTORY) {
free(path_copy);
return NULL; // 当前节点不是目录
}
struct inode* next = find_in_directory(current, token);
if (next == NULL) {
free(path_copy);
return NULL; // 找不到下一个组件
}
current = next;
token = strtok(NULL, "/");
}
free(path_copy);
return current;
}
目录结构的优化
1. 哈希表优化
// 使用哈希表加速目录查找
struct directory_hash {
char name[256];
int inode_number;
struct directory_hash* next;
};
struct directory_cache {
struct directory_hash* hash_table[HASH_SIZE];
int entry_count;
};
// 哈希查找函数
struct inode* hash_find(struct directory_cache* cache, const char* name) {
int hash = hash_function(name);
struct directory_hash* entry = cache->hash_table[hash];
while (entry != NULL) {
if (strcmp(entry->name, name) == 0) {
return get_inode_by_number(entry->inode_number);
}
entry = entry->next;
}
return NULL;
}
2. B 树优化
// 使用B树组织目录项
struct btree_node {
char* keys[MAX_KEYS];
int inode_numbers[MAX_KEYS];
struct btree_node* children[MAX_KEYS + 1];
int key_count;
int is_leaf;
};
// B树查找
struct inode* btree_find(struct btree_node* root, const char* key) {
if (root == NULL) return NULL;
int i = 0;
while (i < root->key_count && strcmp(key, root->keys[i]) > 0) {
i++;
}
if (i < root->key_count && strcmp(key, root->keys[i]) == 0) {
return get_inode_by_number(root->inode_numbers[i]);
}
if (root->is_leaf) {
return NULL;
}
return btree_find(root->children[i], key);
}
总结
目录结构是文件系统的核心组织方式，不同的目录结构类型适用于不同的应用场景。现代操作系统主要采用树形目录结构，它提供了灵活的文件组织能力和强大的路径导航功能。
理解目录结构的实现原理对于开发文件系统、进行系统编程和深入学习操作系统都具有重要意义。在后续章节中，我们将学习文件分配方式、访问控制等更高级的文件系统概念。