'locate' command in terminal. Why is it so fast?

Searching a keyword in linux terminal using the locate command gives answer in a short time. What is the search algorithm used?

The system creates a data base of all the files in the computer. So when you search trough locate the command doesn't really checks the whole file-system but only the database, it does a binary search algorithm which is fast like looking up a word in a dictionary. That's why it's so fast (and handy).

Such database is updated regularly; you may have seen it work sometimes when you install a new package: updating mlocate.... You can find more information about how it works by executing in a terminal:

man locate

man updatedb

It uses a database. The database searched by default is located at:

/var/lib/mlocate/mlocate.db

Downside of locate is that it is NOT real time.

From the man page:

DESCRIPTION locate reads one or more databases prepared by updatedb(8) and writes file names matching at least one of the PATTERNs to standard output, one per line.