Search engine indexing

Overview

Recall questions on search engine indexes, web crawlers, how an index is built from a fetched page, why indexing makes search fast, what is stored about each word, robots files, stale results, and indexing versus ranking.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is a search engine index?

   Model answer

   A large data store, built and maintained in advance, that maps words to the pages that contain them. Rather than a list of pages each with its words, it is inverted: for each word it holds the list of pages containing it, together with information such as where in the page the word appeared, how often, and whether it was in the title or a heading. It is the same idea as the index at the back of a book - look up the term and be told immediately where it occurs - and it is what a search is actually searching.

2. 2

   What does a web crawler do?

   Model answer

   A crawler, also called a spider or bot, is a program that browses the web automatically to gather pages for the index. It begins from a list of known addresses, requests each page, hands the content on to be indexed, and extracts every hyperlink on the page. Those links are added to a queue of addresses to visit, and the process repeats, so the crawler follows links from page to page and discovers new pages continuously. It revisits pages it has already seen to detect changes, more often for pages that change frequently, and it keeps track of what it has already visited so it does not loop endlessly.

3. 3

   Describe how the index is built once a page has been fetched.

   Model answer

   The page's HTML is parsed to separate the text content from the markup. The text is broken into individual words and normalised - case is levelled and words are reduced towards a common form so that run, runs and running are treated alike - and extremely common words that would match almost everything may be discarded. For each remaining word, an entry is added or updated recording that this page contains it, along with how many times, where in the page it occurred, and whether it appeared somewhere prominent such as the title or a heading. Information about the page as a whole is stored too - its title, a description, and the outgoing links, which feed both the crawler's queue and the ranking calculation.

4. 4

   Why does indexing make searching fast? Answer in terms of what the alternative would cost.

   Model answer

   Because the expensive work has already been done, once, in advance. Answering a query from the index is a lookup of the search terms in a structure designed for lookup, and then a combination of the resulting lists - work proportional to the number of pages that actually contain those words, not to the size of the web. The alternative would be to fetch and read every page on the web at the moment the user pressed enter, searching billions of documents across the network one by one. That would take days rather than milliseconds, would consume enormous bandwidth, and would have to be repeated in full for every query by every user. The index turns an impossible search of everything into a fast lookup of a prepared answer.

5. 5

   What is stored about a word's occurrence besides the fact that the page contains it, and why does that extra information matter?

   Model answer

   Typically how many times it appears, its positions within the page, and whether it appeared in a prominent place such as the title, a heading, a link's text or an image's alternative text. It matters because the index has to support more than a yes-or-no answer. Positions allow a phrase search, since a phrase requires the words to be adjacent rather than merely present. Frequency and prominence let the engine judge whether the page is really about that word or merely mentions it in passing, which feeds ranking. And storing where the word occurred lets the engine build the short extract shown under each result.

6. 6

   Can a site influence whether a crawler indexes its pages?

   Model answer

   To a degree. A site can publish a file at a standard location on the server stating which parts of the site crawlers are asked not to visit, and can include instructions in a page's head asking that the page not be indexed or its links not be followed. Well-behaved crawlers from the major search engines respect these requests. They are requests, not enforcement: nothing prevents an ill-behaved crawler from ignoring them, and a page excluded this way is still publicly reachable by anyone with the address - so these mechanisms manage crawling, they are not a security measure. Keeping something private requires authentication, not a request not to be indexed.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.