Search data structures: inverted indexes, tries and more

An inverted index maps every term to a sorted list of the documents that contain it, so a search engine answers red kurta by reading two short lists instead of scanning 50 million product titles. Companion structures handle prefixes, typos, ranges, sorting and filters, and BM25 ranks what matched. This is part 2 of the search engines series: part 1 mapped the kinds of search; here we build the machinery, one structure at a time.

Picture it first: the index at the back of a cookbook

You want every recipe in a 600-page cookbook that uses both paneer and peas. Instead of reading every page, you turn to the index at the back: “paneer: 41, 88, 212, 340” and “peas: 12, 88, 150, 340”. Both lists are sorted, so you run a finger down each and stop where they agree: pages 88 and 340.

The index is alphabetical, so every word starting with “pan” sits together. A table at the front lists each recipe’s cooking time, so “quickest first” means scanning one column. And if you look up “panir”, you spot the right entry nearby.

Map it back: the back-of-book index is the inverted index; the finger on two lists is a postings merge; alphabetical order is the term dictionary; the table is doc values; spotting “panir” is fuzzy matching.

From text to terms: analysis

Before anything is indexed, an analyser turns raw text into terms. The same analyser must run on documents at index time and on the query at search time: if the index holds kurta and the query arrives as Kurtas, nothing matches. Elasticsearch describes an analyser as three stages:

1. Character filters clean the stream, for example stripping HTML.
2. One tokeniser splits text into tokens and records each token’s position and character offsets: “Red Cotton Kurtas” becomes Red, Cotton, Kurtas at positions 0, 1, 2.
3. Token filters lowercase, drop stop words, stem and add synonyms.

Stemming vs lemmatisation. A stemmer chops suffixes by rule (Porter’s algorithm for English), so kurtas becomes kurta: fast and crude. A lemmatiser uses a vocabulary and grammar to return the dictionary form (ran becomes run): more accurate, slower, and it needs language data. Product search usually prefers a light stemmer, because aggressive stemming hurts precision.

Stop words and synonyms. Elasticsearch’s standard analyser does not drop stop words by default, because phrases such as “the north face” need them. Synonyms (pyjama, pajama) can be added at index time (bigger index, reindex to change) or, more usually, at query time (change them any day).

Hindi and Hinglish. Elasticsearch’s hindi analyser chains Indic normalisation, Hindi stop words and a Hindi stemmer. That handles पनीर in Devanagari, not paneer in Latin letters, so for Hinglish you index both scripts (an ICU Any-Latin transform adds a Latin form of each Devanagari term) or transliterate the query. Bazaar would index titles into English and Hindi sub-fields and query both.

Brands, SKUs and sizes are not analysed: each is one exact keyword term, so brand = Khadi Co is a precise filter.

The inverted index

Take four Bazaar product titles, analyse them, then flip the result: for every distinct term, record which documents contain it. That flipped map is the inverted index. It has two parts:

• The term dictionary: every distinct term, sorted, with statistics such as document frequency (df, how many documents contain it) and a pointer to its postings.
• The postings lists: for each term, the IDs of the documents containing it, sorted ascending, optionally with the term frequency (tf), the positions of each occurrence (for phrases) and character offsets (for highlighting).

Each field stores only what it needs, and Lucene keeps the parts in separate files (.doc for IDs and frequencies, .pos for positions, .pay for offsets), so a query needing only doc IDs never reads positions. The Lucene project quotes an index of roughly 20–30% of the text’s size; the IR textbook’s rule of thumb is that positions make an index 2–4 times larger.

Doc IDs are small, dense integers assigned in insertion order (per segment, from 0), not your product IDs; that density makes gap encoding and bitsets work. They are 32-bit, so one Lucene index, and therefore one Elasticsearch shard, holds at most Integer.MAX_VALUE − 128, about 2.1 billion documents.

Answering queries by merging postings

AND: intersect, rarest term first

For silk AND cotton, walk both sorted lists together like the finger in the cookbook: compare the current IDs, advance the smaller, emit a match when they are equal. That costs O(m + n) for lists of length m and n. Two refinements make it fast:

• Start with the rarest term. The result is never longer than the shortest list, so the rare term drives and the common one only answers “what is your next ID at or after X?”.
• Skip instead of stepping. Skip pointers let the long list jump over IDs that cannot match; the IR textbook suggests about √P of them for P postings. Lucene skips per block: since Lucene 10.4, each block of 256 doc IDs carries skip data with its last doc ID, plus a second level every 32 blocks (8,192 docs). advance(target) decodes only the block that can hold the target.

Skips help AND, not OR: a union must visit every posting anyway.

OR and top-k

kurta OR kurti is a union, merged with a small min-heap keyed by each list’s current doc ID. Every document in a union may need a score, so ORs over common terms are the expensive queries. Since version 8.0, Lucene records per block the (frequency, length) pairs that could produce the block’s highest score (“impacts”); if that best case cannot beat the current 10th-best hit, the block is skipped. This is the idea behind block-max WAND, and why an exact total hit count is slower: counting must visit every match.

Phrases and proximity: positions

A phrase needs the words adjacent and in order. For "red cotton", intersect as usual, then check whether some position of cotton equals a position of red plus 1. In Figure 1, D1 (red at 0, cotton at 1) matches; D4 (red at 2, cotton at 0) has both words but no phrase. A proximity (slop) query relaxes “plus 1” to “within k positions”. Positions are far bulkier than doc IDs, so phrases cost noticeably more than a plain AND.

Compressing postings

Stored as raw 32-bit integers, cotton in 5 million of Bazaar’s products is 5,000,000 × 4 bytes = 20 MB, read by every query that uses it. Smaller postings fit in the page cache and need less memory bandwidth, so compression makes search faster, not just smaller.

Step 1: store gaps (d-gaps). The list is sorted, so store the first ID and then differences: 33, 36, 43 becomes 33, 3, 7. A term in 400,000 of 50 million documents has an average gap of 50,000,000 / 400,000 = 125.

Step 2: variable-byte (VB) codes. Write each gap in 7-bit groups, one per byte, with the top bit saying whether another byte follows. Gaps under 128 take 1 byte; under 16,384, 2 bytes. If that term’s gaps were random with mean 125, about e^(−128/125) ≈ 36% would need a second byte: ≈ 1.36 bytes per posting, so 0.54 MB instead of 1.6 MB. The IR textbook calls VB an excellent time–space trade-off for most systems.

Step 3: bit packing (frame of reference). Pack every gap in a block at the bit width of the block’s largest gap: a largest gap of 300 means 9 bits each. Decoding is a fixed shift-and-mask loop with no branch per value, which CPUs and SIMD units run very fast. Lucene adopted this “FOR” scheme in 4.1 and today packs blocks of 256 gaps (128 before 10.4). A list’s tail, under 256 postings, is written as VInts, and a term in exactly one document keeps that doc ID inside the term dictionary.

One large gap sets the width for the whole block, so Lucene’s term-frequency blocks “patch” outliers (storing the few exceptions separately), while its doc-ID blocks do not. The price of all this: a sorted, packed list cannot be edited in place, a big reason search indexes are written once as immutable segments and merged later, the subject of part 3.

The term dictionary

Before reading postings you must find the term: exactly (kurta), by prefix (kur), by range, or within one edit of kurtha.

• Hash table: O(1) exact lookups but no order, so no prefix, range or fuzzy queries.
• Sorted array or B-tree: O(log M) for M terms, plus prefix and range scans; what a database index uses.
• Trie: one path per term with shared prefixes stored once; lookup cost grows with the term’s length, not with M.
• FST (finite-state transducer): a trie that also shares suffixes and maps each term to an output such as a file pointer. Very compact, more CPU per lookup.

Lucene combines them. Its block-tree dictionary stores sorted terms on disk in blocks of 25–48 terms sharing a prefix, plus a small in-memory terms index mapping each prefix to its block. A lookup walks the index, then scans one block. The index also answers “this term cannot exist” without a disk read.

Tries for autocomplete

Typeahead wants the 5–10 best completions of a prefix on every keystroke, within a few milliseconds of server time. A trie has one node per prefix: k → u → r → t → a spells kurta. Walking the subtree under k on every keystroke is too slow, so the classic trick is to cache the top-k completions at each node, ranked by popularity.

You gain lookups that cost O(prefix length) plus one list read, however many suggestions exist. You pay in memory and updates: a top-10 list at each of 5 million nodes is 5,000,000 × 10 × 8-byte pointers = 400 MB before any strings, and a popularity change touches every node on its path. So production tries are compressed (a radix tree merges chains such as m-k-u-m into one edge), cache top-k only near the root, and are rebuilt offline. Lucene’s completion suggester uses a weighted FST with a best-first top-N search, which Elasticsearch’s suggester docs call fast but costly to build and held in memory. The full system is Design typeahead.

Edge n-grams are the inverted-index alternative: index every prefix of every word as a term (kurta → k, ku, kur, kurt, kurta). A prefix query becomes a plain term lookup that works with filters and BM25 and completes any word in the title. The cost is a bigger index, and the n-gram filter must run at index time only, or the query kurta would match everything starting with k. Elasticsearch’s search_as_you_type field sets this up.

Substrings, wildcards and typos

n-gram and trigram indexes

Infix patterns such as *shirt* (for tshirt and sweatshirt) cannot use a sorted dictionary, because matching terms are scattered. A k-gram index indexes every run of k characters (shirt → shi, hir, irt). A substring query becomes an AND of its trigrams plus a post-filter against the real pattern, since sharing trigrams does not prove the substring is present. PostgreSQL’s pg_trgm builds GIN or GiST indexes this way, so LIKE '%kurta%', ILIKE and regex matches avoid a full scan. Code and log search use n-grams because identifiers like ErrTimeout do not split into words. The cost: one trigram per character position, so the index can approach the text’s size.

Edit distance and Levenshtein automata

A shopper types kurtha. Levenshtein distance counts the insertions, deletions and substitutions between two strings: kurtha to kurta is 1. It is an O(m × n) dynamic program, and before 4.0 Lucene ran it against every term in the dictionary.

The fix is a Levenshtein automaton, a state machine accepting exactly the strings within N edits of kurtha, intersected with the sorted dictionary. The walk descends only into regions the automaton can still accept, skipping whole ranges (everything starting with b). McCandless’s 2011 write-up is titled “Lucene’s FuzzyQuery is 100 times faster in 4.0”; the same machinery runs wildcard and regex queries.

Lucene supports at most 2 edits. Elasticsearch’s fuzziness: AUTO allows 0 edits for terms of 1–2 characters, 1 for 3–5 and 2 above that. So for the 6-letter kurtha, kurti (h → i, drop the a) matches too: a different garment. An exact prefix (prefix_length) and ranking exact matches first keep this in check.

Numbers and locations: BKD trees

price 300 to 500 is a range. Indexing each price as a term means OR-ing every value in the range: 201 terms for whole rupees, 20,001 in paise, 86.4 million for one day of millisecond timestamps, each a lookup plus a postings list to merge.

Lucene instead indexes numbers and coordinates as points in a BKD tree (block k-d tree), added in Lucene 6.0. Sort the values and split at the median, again and again, until each leaf holds at most 512 points (Lucene’s default); with latitude and longitude, splits switch between dimensions. Each inner node knows the range of values below it, so a range query walks down and, for each cell:

• fully inside the range: takes all its documents without checking values;
• fully outside: skips it;
• crossing the boundary: opens the leaf and checks each point.

Only leaves along the range’s edges are checked one by one. With 50 million prices there are about 97,700 leaves, so the tree is about 17 levels deep (log₂ 97,700 ≈ 16.6). The Bkd-tree paper (Procopiuc, Agarwal, Arge and Vitter, 2003) handles updates by keeping several static, fully packed trees and merging them as they grow, just as Lucene merges immutable segments. Numeric, date and geo filters all use BKD trees; Geospatial indexes compares the alternatives.

Doc values: the column view

The inverted index answers “which documents contain this value?”. Sorting and facet counts ask the reverse: “what is this field’s value for documents 2, 5 and 7?”. So engines also keep a forward index: per field, a column of values indexed by doc ID. Lucene calls these doc values; Elasticsearch builds them at index time as on-disk columns, on by default for every field type that supports them except analysed text. Columns compress well and scan sequentially, the reason analytics databases are columnar too (OLTP vs OLAP).

A typical Bazaar query uses both: the inverted index finds kurta from brand Khadi Co, and doc values sort by price and count sizes. Disable doc values on fields you never sort or aggregate on to save disk; Elasticsearch also allows doc-value-only fields (no inverted index), at the cost of slow filters. A third copy, stored fields (_source), holds the original document for display.

Filters as bitsets

Filters such as in_stock = true do not affect scores and repeat across queries, so engines cache their results. A plain bitset spends one bit per document, 50,000,000 bits = 6.25 MB per filter, and combining filters becomes word-wide AND and OR: ideal for dense filters, wasteful for sparse ones.

Roaring bitmaps (Chambi, Lemire et al.) split IDs into chunks of 65,536 and store each chunk as a sorted array of 16-bit values if it holds at most 4,096 IDs, or as an 8 KB bitmap otherwise (later versions add run-length containers). A brand filter matching 20,000 products costs about 20,000 × 2 bytes ≈ 40 KB instead of 6.25 MB; an in-stock filter matching 30 million fills all 763 chunks (50,000,000 / 65,536) with bitmaps, ≈ 6.25 MB, because dense sets do not compress. Lucene’s query cache uses the same rule: a Roaring-style set below 1% density, a plain bitset above.

Scoring with BM25

Matching decides which documents qualify; scoring decides their order. BM25, the default in Lucene and Elasticsearch, sums over the query terms t:

score(D, Q) = Σ  IDF(t) × tf / (tf + k1 × (1 − b + b × dl / avgdl))

IDF(t)      = ln(1 + (N − n + 0.5) / (n + 0.5))

• IDF makes rare terms count more (N documents, n containing the term); the “1 +” keeps it positive for very common terms.
• Saturation (k1): tf / (tf + K) climbs towards 1 but never passes it, so repeating a word 20 times cannot buy the top spot. Default k1 = 1.2.
• Length normalisation (b): K grows with the document’s length dl relative to the average avgdl, since a match in a short title is stronger evidence. Default b = 0.75; b = 0 ignores length.

Robertson and Zaragoza’s survey notes that many versions also multiply by (k1 + 1), a constant that does not change the ranking; Lucene’s implementation computes the formula above without it.

A worked example

Bazaar’s title field: N = 50,000,000, avgdl = 8 terms. Query red kurta; red is in 5,000,000 titles, kurta in 400,000.

• IDF(red) = ln(1 + 45,000,000.5 / 5,000,000.5) = ln(10.0) ≈ 2.303
• IDF(kurta) = ln(1 + 49,600,000.5 / 400,000.5) = ln(125.0) ≈ 4.828

kurta is 12.5 times rarer, so it is worth about twice as much. Doc A is “Red cotton kurta for women” (5 terms, each query term once); doc B is a keyword-stuffed listing of 16 terms with red once and kurta three times.

Naive tf × IDF ranks the stuffed listing more than twice as high. BM25 puts the honest title first: three occurrences of kurta in B are worth 0.588 / 0.323 ≈ 1.8 times one, not 3 times, and B’s length shrinks both parts.

Two practical notes. Lucene squeezes each field length into one byte, so dl is approximate for long fields. And each shard computes N, n and avgdl from its own documents, so scores differ slightly between shards (Elasticsearch in depth). In product search, BM25 is only the first-stage scorer before popularity, stock and learning-to-rank re-order the top (Search end to end).

Choosing the right structure

The last row is a different family: semantic search swaps terms for embedding vectors and the inverted index for an approximate nearest-neighbour graph such as HNSW, which Lucene added in its 9.x releases. See Vector databases and Embeddings and semantic search.

Going deeper: costs and failure modes

Frequent terms dominate cost. Cost tracks postings touched: cotton in 5 million titles costs far more than ikat in 2,000. Block skipping helps top-k queries, but an unfiltered OR of common words with an exact hit count reads everything.

Leading wildcards. *kurta cannot use the sorted dictionary, so without a trigram or reversed-term index it scans every term. Many deployments disable leading wildcards in user-facing search.

Fuzzy on short words explodes. Two edits on a three-letter word match a large slice of the dictionary; scale edits with word length and require an exact prefix.

Updates are expensive. A doc ID cannot be slotted into a packed block, so engines write new segments and merge later; an update is a delete plus a re-add. Check fast-changing values such as live stock at query time instead (part 3).

Analyser changes need a reindex. Terms are baked in at write time.

Aggregating on analysed text exhausts memory. text fields have no doc values by default, so sorting or aggregating on one un-inverts the index onto the heap (Elasticsearch’s fielddata). Use a keyword sub-field.

Cheat sheet

How to say it in the interview

“I’d build an inverted index over titles and descriptions, analysed with tokenising, lowercasing, light stemming, query-time synonyms and a Hindi sub-field. Each term gets a sorted, compressed postings list of doc IDs with frequencies and positions. A query for red cotton kurta intersects three lists, rarest first, skipping blocks via skip data; phrases check positions. Brand and size are keyword terms whose results I cache as bitsets, price ranges use a BKD tree, and sorting and facets read columnar doc values. BM25 ranks matches before a re-ranker adds popularity and stock. Autocomplete is a separate in-memory trie with top-k per prefix, and typos go through a Levenshtein automaton capped at two edits.”

Why not a B-tree index on the title column? A B-tree matches values that equal or start with a string. It cannot find a word mid-title, does not stem or rank, and LIKE '%kurta%' scans every row. An inverted index keys on every word; PostgreSQL’s full-text search uses one (GIN).

How do you make an AND of a rare and a common term fast? Drive from the rare term’s list and advance the long one with skip data (the last doc ID of every 256-doc block in Lucene), jumping whole blocks without decoding. Cost tracks the short list.

How would you support typos? A Levenshtein automaton over the term dictionary, 1 or 2 edits by word length, an exact short prefix, exact matches scored higher, and a rewrite map for the commonest misspellings.

Why are search indexes hard to update? Postings are sorted and packed, so new documents go into new immutable segments merged in the background, and an update is delete plus re-add. For live stock, check at query time.

What does BM25 add over tf-idf? Saturation and length normalisation: our stuffed 16-term title scored 3.58 against 3.83 for an honest 5-term one, while naive tf-idf scored them 16.79 and 7.13.

Where to go next

• Next in the series: Disk I/O and durability for search: segments, merging, caching and crash safety for these structures.
• Types of search: part 1, the search types these structures serve.
• How search engines work: the one-page overview.
• Elasticsearch in depth: shards, per-shard scoring and aggregations.
• Design typeahead: the autocomplete trie as a full system.
• Database indexes: B-trees, and why they are not enough for text.
• Vector databases: HNSW and the vector half of hybrid search.

References and further reading

1. Introduction to Information Retrieval (Manning, Raghavan and Schütze, Cambridge University Press, 2008), online editionnlp.stanford.eduChapters 1–3, 5 and 11: postings intersection, skip pointers and the √P heuristic, positional indexes and their size, k-gram indexes, variable-byte codes and Okapi BM25.
2. The Probabilistic Relevance Framework: BM25 and Beyond (Robertson and Zaragoza, 2009)staff.city.ac.ukThe BM25 term weight, term-frequency saturation, document-length normalisation and why the (k1 + 1) factor does not change the ranking.
3. Apache Lucene 10.5.2: Lucene 10.4 index file formatslucene.apache.orgWhat a segment stores (terms, postings, positions, norms, doc values, points), 32-bit doc IDs, and the format history: FOR blocks in 4.1, impacts in 8.0, the trie terms index in 10.3, 256-doc blocks in 10.4.
4. Apache Lucene 10.5.2: Lucene104PostingsFormatlucene.apache.orgPacked blocks of 256 d-gaps, the VInt tail, two levels of skip data, singleton doc IDs inlined in the term dictionary, and the split into .doc, .pos and .pay files.
5. Apache Lucene 10.5.2: Lucene103BlockTreeTermsWriterlucene.apache.orgThe block-tree term dictionary: blocks of 25–48 terms on disk and a per-field trie that maps prefixes to blocks.
6. Using Finite State Transducers in Lucene (Michael McCandless, 2010)blog.mikemccandless.comWhat an FST is, why it suits a sorted term dictionary, and the 9.8-million-term, 69 MB Wikipedia example.
7. Lucene’s FuzzyQuery is 100 times faster in 4.0 (Michael McCandless, 2011)blog.mikemccandless.comBrute-force fuzzy matching before 4.0, Levenshtein automata intersected with the term dictionary, and support for 1 and 2 edits.
8. Elasticsearch reference: doc_valueselastic.coWhy sorting and aggregations need a columnar doc-to-value structure, defaults per field type, and doc-value-only fields.
9. Bkd-Tree: A Dynamic Scalable kd-Tree (Procopiuc, Agarwal, Arge and Vitter, SSTD 2003)users.cs.duke.eduThe block kd-tree and the logarithmic method: a set of static, fully packed trees merged as data grows.
10. Better bitmap performance with Roaring bitmaps (Chambi, Lemire, Kaser and Godin, 2016)arxiv.orgChunks of 2^16 IDs stored as sorted 16-bit arrays (up to 4,096 values) or 8 KB bitmaps, and how set operations work on them.