Difference between locate and mlocate

The locate package is the implementation of locate from GNU findutils. The mlocate package is another implementation of the same concept called mlocate. They implement the same basic functionality: quick lookup of file names based on an index that's (typically) rebuilt every night. They differ in some of their functionality beyond basic usage. In particular, GNU locate builds an index of world-readable files only (unless you run it from your account), whereas mlocate builds an index of all files but only lets the calling user see files that it could access. This makes mlocate more useful in most circumstances, but unusable in some unusual installations where it isn't run by the system administrator (because mlocate has to be setuid root), and a security risk.

Under Debian and derivatives, if you install both, locate will run the mlocate implementation, and you need to run locate.findutils to run the GNU implementation. This is managed through alternatives. If you have both installed, they'll both spend time rebuilding their respective index, but other than that they won't conflict with each other.

mlocate is a newer implemenation of locate. Once you install mlocate it

will change the /usr/bin/locate binary to point to mlocate via the alternatives mechanism.

That is why you get mlocate behaviour if you install in that order.

Details can be found here