From Wikipedia:
--Quote--
An index is any data structure which improves the performance of lookup. There are many different data structures used for this purpose, and in fact a substantial proportion of Computer Science is devoted to the design and analysis of index data structures. There are complex design trade-offs involving lookup performance, index size, and index update performance. Many index designs exhibit logarithmic (O(log(N)) lookup performance and in some applications it is possible to achieve flat (O(1)) performance.
All database software includes indexing technology in the interests of improving performance. See Index (database).
One specific and very common application is in the domain of information retrieval, where the application of a full-text index enables rapid identification of documents based on their textual content.
--End Quote--
I believe this is how it is usually used.
For example, updatedb creates an index of all the files on your system, so when you search
the index is referenced, its considerably faster then
which seaches through the all the files each time.
The problem with indexing is that the index has to be recreated to reflect any changes. So if your changing your system a lot the index may show files that are no longer there or on a device that is no longer mounted, likewise not show new files.
I have updatedb scheduled to run regularly and manually run it when I'm working on something and making major changes.