Para almacenar archivos adjuntos, un /path/to/atts/directorio tendrá numerosos directorios secundarios (ID de producto) creados (de 1 a ~10 000 o tal vez más en el futuro), y en cada uno de estos subdirectorios, se crearán de 1 a ~10 archivos adjuntos.
En/path/to/atts/
1
├── file1.1
├── file1.2
└── file1.3
2
└── file2.1
...
10000
├── file10000.1
├── file10000.2
├── file10000.3
├── file10000.4
└── file10000.5
(En realidad, se eligió 1 .. 10000 para una explicación más simple: los ID serán números int32)
Me pregunto, en el sistema de archivos ext4, cuál es la cdcomplejidad (en realidad, la resolución de la ruta), cuando se alcanza, /path/to/atts/54321/...por ejemplo:
¿La resolución de la ruta verifica todos los inodos/nombres uno por uno en el
attsdirectorio hasta que54321se alcanza? Lo que significa que en promedio se verifican n/2 inodos (O(n))¿O hay alguna estructura de árbol dentro de un directorio que reduce la búsqueda (por ejemplo, un árbol de prueba, orden alfabético...), que reduciría drásticamente el número de inodos comprobados, como log(n) en lugar de n/2?
Si es lo primero, cambiaré la forma en que se implementa la estructura del árbol de productos.
Para que quede claro: la pregunta no se trata de una findbúsqueda de un archivo en un árbol del sistema de archivos (eso es O(n)). En realidad, es una resolución de ruta (realizada por el FS), que cruza un directorio donde residen miles de nombres de archivos (los ID de producto)..
Respuesta1
Puede leer sobre el índice de árbol hash utilizado para directorios.aquí.
Una matriz lineal de entradas de directorio no es excelente para el rendimiento, por lo que se agregó una nueva característica a ext3 para proporcionar un árbol equilibrado más rápido (pero peculiar) a partir de un hash del nombre de la entrada del directorio.