сложность 'cd' на ext4

Question

Для хранения вложений в /path/to/atts/каталоге будет создано множество дочерних каталогов (идентификаторов продуктов) (от 1 до ~10 000 или, возможно, больше в будущем), и в каждом из этих подкаталогов будет создано от 1 до ~10 файлов вложений.

В/path/to/atts/

  1
  ├── file1.1
  ├── file1.2
  └── file1.3
  2
  └── file2.1
  ...
10000
  ├── file10000.1
  ├── file10000.2
  ├── file10000.3
  ├── file10000.4
  └── file10000.5

(на самом деле 1 .. 10000 было выбрано для простоты объяснения - идентификаторы будут числами int32)

Мне интересно, какова cdсложность (фактически разрешения пути) в файловой системе ext4 при достижении, /path/to/atts/54321/...например:

• Проверяет ли разрешение пути все inode / имена по одному в attsdir, пока 54321не будет достигнут? Значение в среднем n/2 inodes проверяется (O(n))

• Или же внутри каталога есть какая-то древовидная структура, которая сокращает поиск (например, дерево trie, алфавитный порядок...), что значительно сократит количество проверяемых inode, например, log(n) вместо n/2?

Если первое, я изменю способ реализации древовидной структуры продуктов.

Просто для ясности: вопрос не о findпоиске файла в дереве файловой системы (это O(n)). На самом деле это разрешение пути (выполняемое FS), проходящее через каталог, в котором находятся тысячи имен файлов (идентификаторы продуктов).

Answer 1

Вы можете прочитать об индексе хэш-дерева, используемом для каталоговздесь.

Линейный массив записей каталога не очень хорош с точки зрения производительности, поэтому в ext3 была добавлена ​​новая функция, обеспечивающая более быстрое (но своеобразное) сбалансированное дерево, ключом которого является хэш имени записи каталога.