'cd' no ext4

Question

Para armazenar anexos, um diretório /path/to/atts/ terá vários diretórios filhos (IDs de produto) criados (de 1 a 10.000 ou talvez mais no futuro) e, em cada um desses subdiretórios, de 1 a 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 por uma explicação mais simples - os IDs serão números int32)

Gostaria de saber, no sistema de arquivos ext4, qual é a complexidade cd (na verdade, resolução do caminho) ao alcançar /path/to/atts/54321/... , por exemplo:

• A resolução do caminho verifica todos os inode / nomes um por um no atts dir até que 54321 seja atingido? Significado em média n / 2 inodes são verificados (O (n))

• Ou há alguma estrutura de árvore dentro de um diretório que reduza a pesquisa (por exemplo, uma árvore trieira, ordem alfabética ...), que reduziria drasticamente o número de inodes verificados, como log (n) em vez de n / 2?

Se for o primeiro, alterarei a maneira como a estrutura da árvore de produtos é implementada.

Apenas para ficar claro: a questão não é sobre uma pesquisa find 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) .

    

Answer 1

Você pode ler sobre o índice da árvore de hash usado nos diretórios aqui .

A linear array of directory entries isn't great for performance, so a new feature was added to ext3 to provide a faster (but peculiar) balanced tree keyed off a hash of the directory entry name.