Google Web Search Index Architecture

An inverted index maps every word to the list of documents containing it, along with positions and metadata (TF-IDF scores, font size, anchor text). Building this index requires processing every crawled page — extracting tokens, computing relevance scores, and writing billions of posting lists. The trade-off is deliberate: index construction is expensive (hours of MapReduce), but query-time lookups are blazing fast — intersecting posting lists for multi-word queries takes milliseconds. This write-heavy/read-optimized structure is the foundation of all modern search engines.

Google's original indexing pipeline used MapReduce: mappers parse pages and emit (word → doc_id) pairs, reducers build sorted posting lists. A full rebuild of the web index took days. The Caffeine system replaced this with an incremental architecture where newly crawled pages are indexed within minutes rather than days. Caffeine uses Percolator — a system for incremental processing on top of Bigtable — that watches for new crawl data and triggers localized index updates. This shift from batch to near-real-time indexing was critical for freshness-sensitive queries like news.

PageRank treats the web as a directed graph where each hyperlink is a vote. A page's score is the sum of scores from pages linking to it, divided by their outgoing link count — essentially a random-walk probability over the web graph. Computing PageRank requires multiple iterations over the entire link graph (billions of edges), originally done via MapReduce. The algorithm converges after 50–100 iterations. Modern Google combines PageRank with hundreds of other signals (click-through rates, content quality, freshness) in a learned ranking model.

The search index is sharded across thousands of machines by document ID range. When a query arrives, a root server fans it out to all index shards in parallel. Each shard returns its top-K results locally, and the root server merges these partial results into a global top-K. To meet the 200ms latency budget, Google uses techniques like speculative execution (sending the query to multiple replicas and taking the fastest response) and graceful degradation (returning partial results if some shards are slow). Tail latency management is critical at this fan-out factor.

Googlebot cannot crawl the entire web simultaneously, so the crawl frontier prioritizes URLs by expected value: high-PageRank sites are crawled more frequently, newly discovered domains are prioritized for freshness, and previously-seen pages are re-crawled based on their historical change rate. The frontier must also respect robots.txt, handle politeness policies (rate-limiting per domain), detect and avoid crawler traps (infinite URL spaces), and deduplicate content across mirror sites. This prioritization engine determines which of the web's trillions of URLs are worth indexing.