有人知道在使用 ext4 文件系统时，Python 中 os.path.exists 函数的复杂度是多少吗？
2个回答
9
Ext4（和Ext3）使用的底层目录结构与Ext2完全相同。 Ext3添加了日志记录，Ext4改进了该日志记录。 日志记录与您的问题无关。
最初，Ext2将其存储为列表，但这对于大型目录来说效率低下。 因此，它已更改为称为HTree的B-tree的调整版本。 与标准B-tree不同，HTree具有恒定深度并使用每个节点的哈希映射，因此其查找复杂度为O（1）。
引用：“HTree”被我们称为Ext2的方案，其中使用32位哈希作为密钥，其中每个哈希键引用存储在叶块中的条目范围。 由于内部节点仅为8字节，因此HTree具有非常高的扇出因子（可以使用4K索引块引用500多个块），两级索引节点足以支持超过16,000,000个52个字符的文件名。 为了进一步简化实现，HTree是恒定深度（一级或两级）。 高扇出因子的组合和使用文件名的哈带，以及特定于文件系统的秘密作为HTree的搜索键，避免了实现进行平衡操作的需要。
参见：http://ext2.sourceforge.net/2005-ols/paper-html/node3.html
最初，Ext2将其存储为列表，但这对于大型目录来说效率低下。 因此，它已更改为称为HTree的B-tree的调整版本。 与标准B-tree不同，HTree具有恒定深度并使用每个节点的哈希映射，因此其查找复杂度为O（1）。
引用：“HTree”被我们称为Ext2的方案，其中使用32位哈希作为密钥，其中每个哈希键引用存储在叶块中的条目范围。 由于内部节点仅为8字节，因此HTree具有非常高的扇出因子（可以使用4K索引块引用500多个块），两级索引节点足以支持超过16,000,000个52个字符的文件名。 为了进一步简化实现，HTree是恒定深度（一级或两级）。 高扇出因子的组合和使用文件名的哈带，以及特定于文件系统的秘密作为HTree的搜索键，避免了实现进行平衡操作的需要。
参见：http://ext2.sourceforge.net/2005-ols/paper-html/node3.html
- vartec
0
很有可能的是，复杂度为O(n)，其中n是文件系统的深度（例如， / 的深度为n=1，/something的深度为n=2，...）
- ThiefMaster
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接