Search and inverted indexes
Do the reading once, when a document arrives, and file every word it holds. A search then reads only the short lists for its own words, never the documents themselves.
Problems worked on this page, and more to practise
What is an inverted index, in one sentence?
A map from each word to the sorted list of documents that contain it. It is called inverted because a document naturally lists its words, and the index turns that around so each word lists its documents. A search for several words fetches their lists by key and intersects them. The documents themselves are only read when they are added, never when someone searches.
Why are posting lists kept sorted by document id?
Because two sorted lists can be intersected in one pass with a pointer on each, moving whichever points at the smaller id. That makes an AND query linear in the lengths of the lists it reads, with no hashing and no extra memory. If ids are handed out in increasing order, appending keeps a list sorted for free. Real engines also compress sorted lists well, by storing the gaps between ids instead of the ids.
When do I need Elasticsearch rather than a hand-built index?
Say the numbers first. A hundred thousand short articles make an index of tens of megabytes, which fits in one process, and one box answers thousands of searches a second. You want a search engine when you need what comes with it: stemming and language analysis, relevance tuning, faceting, replication, and an index that is updated while it serves. In a round, name it as the product you would run and explain the index underneath, because the index is what they are asking about.
How does autocomplete differ from full-text search?
Autocomplete matches the start of a key, not a word anywhere inside a document, so the index is a sorted list of past queries or a trie rather than posting lists. Every completion of a prefix sits in one contiguous run of the sorted keys, and two binary searches find the run. The hard part is ranking: a one-letter prefix matches a large share of the keys, so the top suggestions for short prefixes are precomputed rather than ranked per keystroke.
How is a new document made searchable without rebuilding the index?
Write it to a small in-memory index, and search that alongside the big one. Periodically flush the small index to an immutable segment on disk and merge segments in the background, much like the log-structured storage engine. A delete is recorded as a mark and dropped at the next merge. The delay between a write and its first appearance in results is a number to state in a round, and the prompt decides how long it may be.