python: complejidad de os.path.existen con un sistema de archivos ext4?

¿Alguien sabe cuál es la complejidad de la función os.path.exists en python con un sistema de archivos ext4?

La estructura de directorios subyacente utilizada por Ext4 (y Ext3 ) es exactamente la misma que en Ext2 . Ext3 agrega journaling, Ext4 mejora ese journaling. El diario es irrelevante para su pregunta.

Originalmente, Ext2 solía almacenar eso como una lista, pero eso, por supuesto, era ineficiente para los directorios grandes. Así que se ha cambiado a una versión modificada de B-tree llamada HTree . A diferencia del árbol B estándar, HTree tiene una profundidad constante y utiliza hash-map por nodo, por lo que su complejidad de búsqueda es O (1) .

El esquema de Ext2, que denominamos “HTree”, utiliza hashes de 32 bits para las claves, donde cada clave de hash hace referencia a un rango de entradas almacenadas en un bloque de hojas. Dado que los nodos internos tienen solo 8 bytes, los HTrees tienen un factor de fanout muy alto (se puede hacer referencia a más de 500 bloques utilizando un bloque de índice 4K), dos niveles de nodos de índice son suficientes para admitir más de 16 millones de nombres de archivo de 52 caracteres. Para simplificar aún más la implementación, los HTrees son de profundidad constante (uno o dos niveles). La combinación del alto factor de fanout y el uso de un hash del nombre de archivo, más un secreto del sistema de archivos que sirve como clave de búsqueda para el HTree, evita la necesidad de que la implementación realice operaciones de balanceo.

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

Hay muchas posibilidades de que la complejidad sea O(n) siendo n la profundidad en el sistema de archivos (por ejemplo, / tendría n = 1, / algo n = 2, …)