locate is fast because there's a cron job that does the heavy lifting of scanning and indexing the filesystem. Without that, find is about as fast as PS.
Yes and it puts it in a database updated regularly for fast access. I'm not sure why this isn't default on Windows. How often does one need to search for a random file in the OS?