Журнал при запуске программы

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

Старые файловые системы (например, UFS, FFS , ext2 , исходный ext3 ,…) имеют тенденцию хранить каталоги в виде массива записей (каждая запись содержит имя файла, номер inode и, возможно, некоторые дополнительные метаданные) и выполнять линейный поиск. Новые файлы добавляются при первой свободной записи в массиве; если свободного входа нет, массив сначала увеличивается. Это приводит к плохой производительности с большими каталогами.

Новые файловые системы (например, ext3 с параметром dir_index , ext4 , zfs , btrfs , reiserfs , HFS , HFS + ,…) имеют тенденцию хранить каталоги в виде структуры данных с поиском по логарифмическому времени, своего рода сбалансированным деревом поиска, хеш-таблицей или комбинация двух (сбалансированное дерево поиска хэшей) - обычно это некоторый вариант B-дерева . Это делает код файловой системы более сложным, но сохраняет производительность при работе с большими каталогами.