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.