For an experience similar to locate on Windows + NTFS systems, there is Everything [1]. It also has a command line tool that you can use (well) from the command line.

[1] http://www.voidtools.com/