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