有谁知道 os.path.exists 函数在带有 ext4 文件系统的 python 中的复杂性是什么？
user63899
问问题
780 次
2 回答
9
Ext4（和Ext3 ）使用的底层目录结构与Ext2中的完全相同。Ext3添加了日志，Ext4改进了日志。日记与您的问题无关。
最初 Ext2 用于将其存储为列表，但对于大型目录来说，这当然是低效的。因此，它已更改为 B-tree 的调整版本，称为HTree。与标准 B-tree 不同，HTree 具有恒定的深度并使用每个节点的 hash-map，因此它的查找复杂度是O(1)。
Ext2 的方案，我们称之为“HTree”，使用 32 位散列作为键，其中每个散列键引用存储在叶块中的一系列条目。由于内部节点只有 8 个字节，HTree 具有非常高的扇出因子（使用 4K 索引块可以引用超过 500 个块），两级索引节点足以支持超过 1600 万个 52 个字符的文件名。为了进一步简化实现，HTree 的深度是恒定的（一层或两层）。高扇出因子和使用文件名哈希的组合，加上文件系统特定的秘密作为 HTree 的搜索键，避免了实现需要进行平衡操作。
见：http ://ext2.sourceforge.net/2005-ols/paper-html/node3.html
于 2011-05-30T13:14:11.950 回答
0
很有可能复杂性在于O(n)n 是文件系统中的深度（例如 / 将具有 n=1，/something n=2，...）
于 2011-05-30T12:58:00.330 回答