Dies ist der Beginn einer Antwort. Jeder Datei ist ein Inode-Objekt zugeordnet. Der Inode ist dateisystemspezifisch. Aus diesem Grund können Sie normalerweise keine festen Verknüpfungen haben, die sich über Dateisysteme erstrecken. Der Kernel unterhält einen Inode-Cache, der aktualisiert werden kann, wenn das Betriebssystem eine Datei öffnen / referenzieren muss, die sich nicht im Cache befindet. Auf die Inode-Nummer wird nach dem ersten Besuch über einen "Index" oder einen Hash zugegriffen.
Ein einfacher lsBefehl könnte also alle Verzeichniseinträge lesen, um eine Datei zu erhalten (lineare Zeit), oder den Inode-Cache verwenden. Ich glaube, dass die Implementierung von BSD ffs von McKusick die erste war, die das Caching so einsetzte.
Neuere Dateisysteme sind mit gigantischen Verzeichnissen viel besser. Sobald jedoch die Anzahl der Objekte sehr groß wird, wie bei Millionen, können die lsAntwortzeiten nach unten gehen. Wegen Cache-Größenbeschränkungen. Oder weil die Datei nicht zwischengespeichert wird. ufs (neuere Version von ffs) macht dies. ext4 (Linux) ist viel besser, IMO. In den meisten Betriebssystemen werden Statistiken zur Effizienz der Suche gespeichert - testen Sie Ihre Version von Iostat. Dies ist Teil der Dateisystemoptimierung, dh der Größenänderung des Inode-Caches.
Unterm Strich passt also keine Antwort überall. Und normalerweise gibt es Caching. Es wird jedoch LRU beibehalten, da die meisten Kernel eine Inode-Cachegrößenbegrenzung haben. Daher kann ein Inode, der einmal im Monat verwendet wird, aus dem Cache verschoben werden.