python:os.path.exists 的复杂性存在于 ext4 文件系统中？

Question

有谁知道在带有 ext4 文件系统的 python 中 os.path.exists 函数的复杂性是什么？

Answer 1

Ext4(和 Ext3)使用的底层目录结构与 Ext2 完全相同。 Ext3 添加了日记功能，Ext4 改进了日记功能。日记与您的问题无关。

最初 Ext2 用于将其存储为列表，但这对于大型目录来说当然效率低下。所以它已更改为 B 树的调整版本，称为 HTree .与标准 B 树不同，HTree 具有恒定的深度并且每个节点使用 HashMap ，因此它的查找复杂度为 O(1)。

Ext2's scheme, which we dubbed "HTree", uses 32-bit hashes for keys, where each hash key references a range of entries stored in a leaf block. Since internal nodes are only 8 bytes, HTrees have a very high fanout factor (over 500 blocks can be referenced using a 4K index block), two levels of index nodes are sufficient to support over 16 million 52-character filenames. To further simplify the implementation, HTrees are constant depth (either one or two levels). The combination of the high fanout factor and the use of a hash of the filename, plus a filesystem-specific secret to serve as the search key for the HTree, avoids the need for the implementation to do balancing operations.

参见:http://ext2.sourceforge.net/2005-ols/paper-html/node3.html