That's why it is so fast in practice, it's instantaneous (as far as screen refreshs go) on every file manager I've ever used.
Recursive search however, does have to touch the filesystem, and does have to touch it massively for directories that contain thousands of subdirectories. That's what a "search" is, the user expects the search results to be fresh from the file system, not just scraped from a cache internal to the File Manager.
That's why recursive search is so disturbingly slow, to the point where it routinely takes seconds, or could even minutes depending on the setup (spinning drive + bad filesystem + large directory tree...).
And that is why Nautilus is basically unusable for me and a lot of other people.
By the way, there are other semantical problems with search vs Type-Ahead. For example, I cannot type a prefix in the current directory to see whether there is a file with that prefix in the current directory. Nautilus' recursive search will just pull up a completely unrelated and unexpected file from somewhere in this tree.
That means, that if I mistype, I don't get any reasonable feedback from Nautilus, but instead get a warm "thank you" and a huge diskload. It's about as depressing as browsing some websites that bombard you with ads and never show the contents you searched for.