Imagine the billions of web pages in the world. Typing a word or phrase into a search engine interface returns us a long list of results in less than a second. The speed at which a search engine processes so many web pages is miraculous. How does it find the correct document so quickly? To answer this question, we will do the wisest thing a programmer can do design an engine of our own.
The following diagram shows the basic idea behind a search engine:
The User types in words using the search engine's user interface. The Search engine scans all the documents, filters them, sorts them by relevance, and responds to the user as fast as it can. Our main interest lies in the web search engine's implementation. Looking for something will require searching for it among billions of documents.
Let's try to devise an approach...