Why does the `updatedb` program run so fast?

The answer depends on the version of locate you’re using, but there’s a fair chance it’s mlocate, whose updatedb runs quickly by avoiding doing full disk scans:

mlocate is a locate/updatedb implementation. The 'm' stands for "merging": updatedb reuses the existing database to avoid rereading most of the file system, which makes updatedb faster and does not trash the system caches as much.

(The database stores each directory’s timestamp, ctime or mtime, whichever is newer.)

Like most implementations of updatedb, mlocate’s will also skip file systems and paths which it is configured to ignore. By default there are none in mlocate’s case, but distributions typically provide a basic updatedb.conf which ignores networked file systems, virtual file systems etc. (see Debian’s configuration file for example; this is standard practice in Debian, so GNU’s updatedb is configured similarly).

In addition to checking modification times, mlocate also ignores certain subtrees of the file system that have lots of uninteresting or potentially duplicate files, as specified in /etc/updatedb.conf (and described in man updatedb.conf):

• Bind mounts
• Some kinds of file systems (9p, afs, bdev, etc)
• VCS repository databases (.git, .hg, etc)
• Some hard-coded directories (/media, /tmp, /var/spool/cups, etc).