Время нахождения файла в каталоге
При поиске файла в каталоге с большим количеством файлов (n), каково наихудшее время выполнения поиска этого файла? Я имею в виду, ОС (Linux) последовательно проверяет все имена файлов в каталоге, чтобы найти совпадение (O(n)) или он поддерживает своего рода более интеллектуальную индексацию словаря?
1 ответ
Это начало ответа. С каждым файлом связан объект inode. Индод зависит от файловой системы, поэтому у вас обычно не может быть жестких ссылок, которые охватывают файловые системы. Ядро поддерживает кэш-память узла, которая может обновляться всякий раз, когда ОС должна открывать / ссылаться на файл, не находящийся в кеше. Доступ к номеру индекса осуществляется после первого посещения через "индекс" или хэш.
Так просто ls Команда может прочитать все записи каталога, чтобы получить файл - линейное время - или она может использовать кэш-память. Я полагаю, что реализация BSD ffs McKusick была первой, кто использовал такое кэширование.
Более новые файловые системы намного лучше с гигантскими каталогами, однако, как только количество элементов становится действительно большим, как миллионы, ls время отклика может идти вниз по трубам. Из-за ограничений размера кэша. Или потому что файл не кешируется. UFS (более новая версия FFS) делает это. ext4 (Linux) намного лучше, IMO. Большинство ОС ведут статистику эффективности поиска - попробуйте свою версию iostat. Это является частью настройки файловой системы, то есть определения размера кэша inode.
Итак, суть в том, что ни один ответ не подходит везде. И там обычно кеширование. Но поддерживается LRU, потому что большинство ядер имеют ограничение размера кэша инода, поэтому инод, который используется один раз в месяц, может быть перемещен из кэша.