![UNIX 是否使用二分搜索来搜索目录?](https://linux22.com/image/95080/UNIX%20%E6%98%AF%E5%90%A6%E4%BD%BF%E7%94%A8%E4%BA%8C%E5%88%86%E6%90%9C%E7%B4%A2%E6%9D%A5%E6%90%9C%E7%B4%A2%E7%9B%AE%E5%BD%95%EF%BC%9F.png)
我目前正在阅读 W. Richard Stevens 所著的《高级 UNIX 编程》一书,在那里我读到 UNIX 上的所有文件都有一个编号,并且创建文件名只是为了方便用户。输入目录后,系统会在号码中搜索输入的名称。
我心想,他们怎么查这个号码呢?文件是否按名称排序存储,以便可以通过二分搜索找到它们?或者他们只是将新文件附加到列表末尾?
答案1
有许多不同的文件系统格式,它们在不同场景下的性能(大目录与小目录、读取与写入、并发访问等)、设计简单性(错误的可能性、开发工作量等)、磁盘开销(空间)之间做出了不同的折衷用于文件内容以外的东西)等。
较旧的文件系统(例如UFS、FFS,外部2, 原来的外部3,...)倾向于将目录存储为条目数组(每个条目包含文件名、索引节点号以及可能的一些附加元数据)并进行线性搜索。新文件将添加到数组中的第一个空闲条目处;如果没有空闲条目,则首先扩大数组。这会导致大型目录的性能不佳。
较新的文件系统(例如外部3与dir_index
选项,外部4,兹夫斯,BTFS,赖塞尔夫斯,高频FS,高频FS+,...)倾向于将目录存储为具有对数时间查找的数据结构,某种平衡搜索树,哈希表或两者的组合(哈希的平衡搜索树) - 通常是B树。这使得文件系统代码更加复杂,但在大型目录下保持良好的性能。
答案2
该数字称为索引节点。 Ext4 是更流行的 Linux 文件系统类型之一,它使用哈希树,请参阅kernel.org - Ext4 磁盘布局。
哈希树的更多详细信息位于维基百科。
答案3
这取决于文件系统。很久以前,Unix目录本质上是一个由16字节记录组成的文件,其中两个字节为内部编号,14个字节为文件名。这就是旧时文件名 14 个字符限制的原因。记录未排序,因此需要对文件进行线性搜索。
更现代的文件系统(例如 Linux 的 Ext4)具有哈希表来加速搜索。
答案4
学究警告:描述不完整。文件名不能仅仅描述为方便用户。文件名已被证明是极其在基于 UNIX 的系统中很重要。
索引节点号没有意义,因为它们是由文件系统模块选择的。最初,他们在存储在磁盘上的索引节点表中确定了一个插槽。系统的其他部分需要访问具有特定含义的文件,例如/dev/tty1
或/etc/passwd
。
如果不让您使用特定的词,“便利”就太微不足道了,无法描述该机制,该机制用于提供用户界面来选择命令(例如cat
或ed
按名称)。
如果没有文件名目录,您很快就必须为索引节点号发明一些非常相似的名称注册表来支持这些用途。
目录条目.
也..
有特殊的含义。虚拟文件系统例如proc
使用文件名提供它们自己的含义,例如/proc/1/comm
提供有关进程1的信息。VFS还允许使用不同的文件系统,这些文件系统不必基于unix,并且可能无法使用相同的确切概念索引节点号。
ZFS 似乎认为文件名和 inode 元数据(如权限)都属于单独的层。我还不明白这有什么好处。当用于存储嵌套文件系统时,它似乎更像是一种为文件等效对象提供不同性能旋钮的方法。
此外,用户通常无法通过索引节点号打开文件。如果可以,您将无法通过包含director{y,ies}的权限来控制对文件的访问...
也许看待最后一点的另一种方式是它是目录的一个特性。目录的整个原理是映射文件名,因此如果没有它,它们就不会产生任何效果。
等等,你说,它们仍然可以作为文件引用的容器,即“硬链接”。您可以在多个目录中列出文件;如果文件仍保留在另一目录中,则从一个目录中删除文件 ( unlink
) 并不会真正删除该文件。硬链接是 unix 实现中一个有趣的部分,但据我所知,他们从未真正找到任何实用程序!它们通常被认为只是造成混乱的机会。这是一个公开实现细节的示例,因为它使提供有趣的功能变得非常容易,而无需真正考虑该功能是否必要。与“十亿美元的错误”类似,尽管这种特殊的设计缺陷并没有那么危险。
也就是说,值得注意的是目录保证其包含的文件存在的方式。如果您想实现其他一些系统来识别文件,则必须考虑删除文件可能会留下一个引用不存在文件的条目,甚至是一个被分配了相同 inode 的新的不相关文件。稍后编号。