Build an inverted index (Lucene-style)
The data structure underneath every search engine. Build a postings-list-based inverted index that survives ingest, merge, and query — term dictionary, skip lists, segment merges, deletes via tombstone. Internalize the per-segment immutable design before you scale it across shards in the Elasticsearch chapter.Enter to send · Shift+Enter for a new line
About Build an inverted index (Lucene-style)
The data structure underneath every search engine. Build a postings-list-based inverted index that survives ingest, merge, and query — term dictionary, skip lists, segment merges, deletes via tombstone. Internalize the per-segment immutable design before you scale it across shards in the Elasticsearch chapter.
- Difficulty
- beginner
- Time
- about 75 minutes
- Stages
- 9
- Topic
- Search, Indexing & Retrieval
How this problem is worked
Nine stages, from what the thing is for to how it compares with the real implementations. Each asks one question, and the simulator runs the architecture you draw against the requirements you wrote.
- 01Purpose & invariantsWhat is this for, and what must always be true of it?
- 02Workload characterizationWho writes, who reads, and in what shapes?
- 03Data model & on-disk formatWhat does the data look like at rest?
- 04Core algorithmsHow do the write path and the read path actually work?
- 05Distribution & replicationHow does this scale out and survive losing a machine?
- 06Consistency & correctnessUnder concurrency and failure, what is guaranteed?
- 07Failure modes & recoveryWhat actually happens when each part fails?
- 08Operational characteristicsCan a human run this at three in the morning?
- 09Trade-offs & comparisonWhere does this sit against the alternatives?
Primary sources for this problem
- Manning, Raghavan, Schütze — Introduction to Information Retrieval (Ch. 1–7)
- McCandless, Hatcher, Gospodnetić — Lucene in Action
- Lucene source — IndexWriter, SegmentMerger, PostingsFormat
- Sigurd Schneider — Lucene's nutshell explanations on Elastic blog
- Zobel & Moffat — Inverted Files for Text Search Engines (ACM CSUR 2006)
- Adrien Grand — Lucene performance talks (Devoxx, Lucene Revolution)
More in Search, Indexing & Retrieval
Finding a needle: inverted indexes, distributed search, vector and ANN retrieval, crawling, and the query box itself.
- Build Build a distributed search engine (Elasticsearch / OpenSearch style)Five million books, a search box, and a 100 ms budget. Build the engine from the inverted index up — segment, refresh, shard, replica, scatter-gather, BM25 — and feel why every guarantee that lives across shards is paid for in either an extra round trip or a small lie about the rankings.
- Build Build a vector database (Pinecone / Weaviate / pgvector style)Approximate nearest-neighbor over a billion 1536-dim vectors in 10 ms. Build the index from scratch (HNSW, IVF, PQ), pay the recall-vs-latency tax explicitly, support filtered + hybrid search, and feel why every LLM stack in 2026 has a vector store next to its KV store.
- Web CrawlerPolitely traverse the web at scale. Don't crawl yourself in circles.
Browse the full problem catalog, or see what the simulator does and does not model.