Para armazenar anexos, um /path/to/atts/diretório terá vários diretórios filhos (IDs de produtos) criados (de 1 a aproximadamente 10.000 ou talvez mais no futuro) e em cada um desses subdiretórios, de 1 a aproximadamente 10 arquivos anexos serão criados.
Em/path/to/atts/
1
├── file1.1
├── file1.2
└── file1.3
2
└── file2.1
...
10000
├── file10000.1
├── file10000.2
├── file10000.3
├── file10000.4
└── file10000.5
(na verdade, 1 .. 10000 foi escolhido para uma explicação mais simples - os IDs serão números int32)
Estou me perguntando, no sistema de arquivos ext4, qual é a cdcomplexidade (na verdade, resolução do caminho), ao alcançar, /path/to/atts/54321/...por exemplo:
A resolução do caminho verifica todos os inodes/nomes um por um no
attsdiretório até54321ser alcançado? Significa que em média n/2 inodes são verificados (O(n))Ou existe alguma estrutura de árvore dentro de um diretório que reduza a pesquisa (por exemplo, uma árvore trie, ordem alfabética...), que reduziria drasticamente o número de inodes verificados, como log(n) em vez de n/2?
Se for o primeiro, mudarei a forma como a estrutura da árvore de produtos é implementada.
Só para ficar claro: a questão não é sobre a findpesquisa de um arquivo em uma árvore do sistema de arquivos (isso é O(n)). Na verdade, é uma resolução de caminho (feita pelo FS), cruzando um diretório onde residem milhares de nomes de arquivos (os IDs do produto).
Responder1
Você pode ler sobre o índice de árvore hash usado para diretóriosaqui.
Uma matriz linear de entradas de diretório não é ótima para desempenho, então um novo recurso foi adicionado ao ext3 para fornecer uma árvore balanceada mais rápida (mas peculiar) com base em um hash do nome da entrada de diretório.