There is no Linux equivalent of Everything on Windows. All search tools have no incremental search funtion like that in Everthing.
The fastest filename search tool is "find" command and catfish. Pay attention that you have to do a "Deep Search" in catfish to perform a "real" search, or it only use "locate" command to search in the database.
This bug will be fixed in next release of catfish. By default catfish will not search files in hidden directories. So you have to use "find" command if you want getting all results including those in hidden directories.
Some Window Manager like Konqueror, Dolphin have filename search function, but they are too slow.