silk AND cotton: let the rare list drive.
Cotton just answers “next ID at or after 49?”. Block 2 ends at 46, so it’s never decoded.
0.54 MB
instead of 1.6 MB: store gaps
A term in 400,000 of 50 million products has gaps averaging 125, ≈ 1.36 bytes each. Smaller lists stay in the page cache, so queries get faster.
A hash table for the term dictionary?
Bad: O(1) hash lookups
Exact terms only. No order, so no prefix, range or fuzzy.
Good: A sorted prefix structure
Sorted 25–48-term blocks on disk, found via a small in-memory trie.
Typing “ku”? Walk two edges, read a cached top 3.
Each node stores its best completions, ranked offline. The cost: top-10 lists at 5 million nodes take 400 MB before strings.
Shoppers type kurtha. Before 4.0, Lucene ran edit distance against every term.
The trick
Intersect a Levenshtein automaton, accepting strings within 2 edits, with the sorted dictionary. Whole ranges get skipped, “100 times faster”.
₹300 to ₹500: not 201 term lookups, one tree walk
A BKD tree splits prices at medians into 512-point leaves. Inside cells come whole, outside ones are skipped; only edges are checked.
Filtering asks term → docs. Sorting asks doc → value.
So engines keep both: the inverted index finds Khadi Co’s products; doc values, a column per field, sort them by price.
Remember
An inverted index of sorted, compressed postings, intersected rarest first. Around it, a trie for prefixes, an automaton for typos, BKD trees for ranges, doc values for sorting. BM25 ranks.