Arqly
Sign in
#21Build an inverted index (Lucene-style)
stub
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.

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.

This problem is a stub. Suggested approaches haven't been authored yet — ask the staff engineer in the right panel for any stage and they'll generate one tuned to your draft.
Reading: 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)
tokens, terms, postings (term → list of doc IDs)
term dictionary: FST / hash / sorted array — pick your trade
postings list compression: variable-byte, FOR, PFOR-Delta
skip lists for fast intersection (AND queries)
doc-id-ordered vs frequency-ordered postings
the per-segment immutable design (one segment = one mini-index)
merge policy: tiered, log-byte-size, no-merge
deletes as tombstones; reclaim only at merge
positional indexes for phrase queries
stored fields vs doc values vs indexed fields (column vs row vs index)
No scenes authored for this problem yet.