系统目录的实现方式

可以使用多种算法来实现目录。但是, 选择适当的目录实现算法可能会严重影响系统的性能。

目录实现算法根据其使用的数据结构进行分类。这些天主要使用两种算法。

在这种算法中, 目录中的所有文件都保留为单行列表。每个文件都包含指向分配给它的数据块的指针以及目录中的下一个文件。

特点

创建新文件时, 将检查整个列表, 以确定新文件名是否与现有文件名匹配。万一它不存在, 可以在文件的开头或结尾创建文件。因此, 搜索唯一名称是一个大问题, 因为遍历整个列表需要花费时间。

在文件上的每个操作(创建, 删除, 更新等)的情况下, 都需要遍历该列表, 因此系统效率低下。

为了克服目录的单链列表实现的缺点, 有一种替代方法是哈希表。此方法建议将哈希表与链接列表一起使用。

生成目录中每个文件的键值对并将其存储在哈希表中。可以通过在文件名上应用哈希函数来确定密钥, 而密钥则指向存储在目录中的相应文件。

现在, 由于现在不会在每个操作上都搜索整个列表, 因此搜索变得高效。使用密钥仅检查哈希表条目, 如果找到了条目, 则将使用该值获取相应的文件。