python:ext4文件系统存在os.path.exists的复杂性吗? [英] python: complexity of os.path.exists with a ext4 filesystem?

问题描述

有人知道带有ext4文件系统的python中os.path.exists函数的复杂性吗?

Does anyone know what the complexity of the os.path.exists function is in python with a ext4 filesystem?

推荐答案

Ext4 (和 Ext3 )使用的基本目录结构与中的完全相同Ext2 . Ext3 添加日记， Ext4 改进日记.日记与您的问题无关.

Underlying directory structure used by Ext4 (and Ext3) is exactly the same as in Ext2. Ext3 adds journaling, Ext4 improves that journaling. Journaling is irrelevant to your question.

最初，Ext2曾将其存储为列表，但对于大型目录而言，效率当然较低.因此，它已更改为B树的调整版本，称为 HTree .与标准B树不同，HTree具有恒定的深度并在每个节点上使用哈希映射，因此其查找复杂度为 O(1).

Originally Ext2 used to store that as list, but that of course was inefficient for large directories. So it's has been changed to tweaked version of B-tree called HTree. Unlike standard B-tree, HTree has constant depth and uses hash-map per node, thus it's lookup complexity is O(1).

Ext2的方案，我们称之为 "HTree"，使用32位哈希作为密钥， 每个哈希键都引用一个范围 叶块中存储的条目数. 由于内部节点只有8个字节， HTree具有很高的扇出系数 (可以引用超过500个块 使用4K索引块)，两个级别的 索引节点足以支持 超过1600万个52个字符 文件名.为了进一步简化 实现，HTrees是恒定的 深度(一个或两个级别).这 高扇出因子的组合 以及文件名哈希的使用， 加上一个特定于文件系统的秘密 用作HTree的搜索关键字， 避免了实施的需要 进行平衡操作.

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

这篇关于python:ext4文件系统存在os.path.exists的复杂性吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！