I can see nautilus is using 'find' like slow search methodology. 

Please see the video:
http://www.youtube.com/watch?v=gor5l2_Yw34

on an ext4 partition, the folder/file name which is right at the TOP Level directory is not shown until the whole filesystem is searched, which took 2 minutes!!!


How to reproduce:

1. open nautilus
2. go to / (root) (especially single root with /usr and /home (requirement is too many files) )
3. click search
4. type 'usr' or 'boot' (any top level folder name)
5. click reading glass (seach icon) or press enter

Result:
6. search results appear only after the full filesystem is searched, which is roughly at least a minute. in my case it is 2 minutes to output 'boot' folder.

7. unfortunately, all next searches, the whole process will again take full 2 minutes to complete. Which is bad. the searches should be 'cached' 

Expected Behavior:

7. Just like the output of 'find / -iname "*boot*" -print' (supposing searching boot at /)
8. the results appear as soon as file/folder matches.

9. Alternately, integrating updatedb/mlocate /cached searches would speed nautilus search.

thanks.