Crawling and Indexing
A lot of things have to happen before you see a web page containing your Google search results. Our first step is to crawl and index the billions of pages of the World Wide Web. This job is performed by Googlebot, our “spider,” which connects to web servers around the world to fetch documents“spider,” which connects to web servers around the world to fetch documents. The crawling program doesn’t really roam the web; it instead asks a web server to return a specified web page, then scans that web page for hyperlinks, which provide new documents that are fetched the same way. Our spider gives each retrieved page a number so it can refer to the pages it fetched.

Our crawl has produces an enormous set of documents, but these documents aren’t searchable yet. Without an index, if you wanted to find a term like civil war, our servers would have to read the complete text of every document every time you searched.

So the next step is to build an index. To do this, we “invert” the crawl data; instead of having to scan for each word in every document, we juggle our data in order to list every document that contains a certain word. For example, the word “civil” might occur in documents 3, 8, 22, 56, 68, and 92, while the word “war” might occur in documents 2, 8, 15, 22, 68, and 77.

Once we’ve built our index, we’re ready to rank documents and determine how relevant they are. Suppose someone comes to Google and types in civil war. In order to present and score the results, we need to do two things:

1. Find the set of pages that contain the user’s query somewhere
2. Rank the matching pages in order of relevance

We’ve developed an interesting trick that speeds up the first step: instead of storing the entire index on one very powerful computer, Google uses hundreds of computers to do the job. Because the task is divided among many machines, the answer can be found much faster. To illustrate, let’s suppose an index for a book was 30 pages long. If one person had to search for several pieces of information in the index, it would take at least several seconds for each search. But what if you gave each page of the index to a different person? Thirty people could search their portions of the index much more quickly than one person could search the entire index alone. Similarly, Google splits its data between many machines to find matching documents faster.

How do we find pages that contain the user’s query? Let’s return to our civil war example. The word “civil” was in documents 3, 8, 22, 56, 68, and 92; the word “war” was in documents 2, 8, 15, 22, 68, and 77. Let’s write the documents across the page and look for those with both words.

Arranging the documents this way makes clear that the words “civil” and “war” appear in three documents (8, 22, and 68). The list of documents that contain a word is called a “posting list,” and looking for documents with both words is called “intersecting a posting list.” (A fast way to intersect two posting lists is to walk down both at the same time. If one list skips from 22 to 68, you can skip ahead to document 68 on the other list as well.)