How does searching a file (locate) or autocompletion work?

I find it surprising how fast does locate work or the autocompletion (that I know) work in linux. ... Is there any indexing being done in the background or how is this achieved?

This is actually two completely distinct questions.

locate uses an index (slocate stores it in /var/lib/slocate/), that is updated by a nightly cron job. This nightly job typically runs at about 1 or 2AM local time, and completely scans your entire system (including all connected drives). The resulting index is simply a list of filenames.

Auto-complete is handled by your shell. Most systems use bash, so bash-completion is the collection of scripts that manage how this works. (zsh has a similarly-named collection, and most of the other shells have some form of completion built-in.) When Tab is pressed, the shell runs a script that decides, based on what you've typed already, what, exactly, needs to be completed. The script then generates a list of possible completions, which may or may not be the list of files in the current directory, or the list of executable files in your $PATH. The locate command is normally not used for this.

Usually, locate uses an index which is generated once a day via a cron-job (/etc/cron.daily/mlocate on my system for example). It does nothing fancy, basically a complete filesystem traversal with some optimizations and the building of the index data structure.

Shells use probably some internal caching for command completion, but does not use a global index file. Besides, usually, Unix kernels maintain a dentry-cache, i.e.\ they cache file directory information used by directory listings etc. in memory (including the stat'ing of non-existent files - which is also called inverse caching).