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