It is no secret that the built-in search for Windows is pretty terrible.
Enter Search Everything,
From their website: http://www.voidtools.com/faq/
For the few search queries I have run against multiple 3Tb Hard drives, response time has been amazingly fast.
I believe it indexes things in a smart fashion behind the scenes to speed up searches.
Go try it out! You will not be disappointed.
What is “Everything”?
“Everything” is search engine that locates files and folders by filename instantly for Windows.
Unlike Windows search “Everything” initially displays every file and folder on your computer (hence the name “Everything”).
You type in a search filter to limit what files and folders are displayed.