> linear search will cause the same arbitrary slowness.
Let's see. My Thinkpad x220, which was built almost 10 years ago, can easily scan through 10 Gigabytes of memory per second. If we assume that visiting each list item causes a cache miss though (which is pessimistic), then (assuming a cache miss costs 100 nanoseconds) maybe we can visit roughly 10 million directory entries with the worst possible, dumb, serial implementation. Let's say we want to ensure a reasonable target of not wasting more than 1 millisecond for the search, we can still Type-Ahead through directories containing 10000 entries with incredible performance (1ms latency).
However, if the directory contents are stored only in a slightly reasonable structure (say, the developer spent the slightest thought at it, like caching the entries in a list of array chunks or so), then, I don't know, it might be closer to 100K entries per 1ms or even approach 1 million entries per 1ms with a little optimization.
It's not a problem at all, it's less than a piece of cake.