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