Course contentsShow
← System Design
Lesson 1737 of 1,91942. Real-World System: Search and TypeaheadFree lesson

Index Building and Updates

Batch and incremental strategies for building indexes and handling new documents without full rebuilds.

Index Building and Updates

What You'll Learn

You'll learn how to construct and maintain inverted indexes efficiently using batch and incremental strategies, so you can add new documents without grinding search traffic to a halt.

The Core Challenge

Building an inverted index from millions (or billions) of documents is expensive—parsing text, extracting terms, sorting posting lists, and writing to disk. But search engines can't go offline for hours every time new content arrives. You need strategies that balance freshness with performance.

Batch Index Building

Initial construction typically uses batch processing:

  • Process documents in large chunks (millions at a time)
  • Build partial indexes in memory, sort them, then merge
  • Optimize for throughput over latency
  • Use MapReduce-style frameworks for parallelization

Think of this like building a library catalog from scratch—you close the library, process all books systematically, then reopen.

Incremental Updates

For ongoing updates, you have two main patterns:

Append-only logs: New documents create small auxiliary indexes that sit alongside the main index. Queries check both. Periodically merge these into the main index during off-peak hours.

In-place updates: Directly modify existing posting lists. Requires careful locking and can fragment data structures, but provides immediate visibility.

Hybrid Strategy

Modern systems typically use:

  • Fresh documents → small in-memory indexes (searchable in seconds)
  • Periodic merges → consolidate into optimized disk segments every few minutes
  • Background compaction → merge segments overnight to reduce fragmentation

This resembles LSM-trees: accept writes quickly, consolidate lazily.

Handling Deletes

Mark documents as deleted in a separate bitmap rather than immediately removing entries. The merge process cleans up tombstones.

Key Takeaway: Efficient index maintenance uses incremental updates for fresh content plus periodic batch merges for optimization—never forcing a full rebuild when documents change.