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-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
locate command is normally not used for this.