Este é o começo de uma resposta. Cada arquivo tem um objeto inode associado a ele. O inode é específico do sistema de arquivos, e é por isso que normalmente não é possível ter hard links que se estendam pelos sistemas de arquivos. O kernel mantém um cache de inode que pode ser atualizado sempre que o sistema operacional tiver que abrir / referenciar um arquivo que não esteja no cache. O número do inode é acessado após a primeira visita por meio de um "índice" ou um hash.
Portanto, um simples comando ls poderia ler todas as entradas de diretório para obter um arquivo - tempo linear - ou poderia usar o cache de inode. Acredito que a implementação BSD ffs de McKusick foi a primeira a usar o cache dessa forma.
Os sistemas de arquivos mais recentes são muito melhores com diretórios gigantescos, no entanto, uma vez que o número de itens se torne realmente grande, como milhões, ls dos tempos de resposta pode diminuir. Por causa dos limites de tamanho do cache. Ou porque o arquivo não está em cache. ufs (nova versão do ffs) faz isso. ext4 (Linux) é muito melhor, IMO. A maioria dos sistemas operacionais mantém estatísticas sobre as eficiências de pesquisa - tente sua versão do iostat. Isso faz parte do ajuste do sistema de arquivos, ou seja, o dimensionamento do cache de inodes.
Portanto, ninguém responde em todos os lugares. E geralmente há cache. Mas é mantida a LRU porque a maioria dos kernels tem um limite de tamanho de cache inode, então um inode que é usado uma vez por mês pode ser movido para fora do cache.