Inverted indexes
A map from each term to the sorted list of documents that contain it, built by turning the document-to-words relation around. It makes full-text search fast; the price is paid when a document is added.
What it is
An inverted index maps each term (a word, a tag, a number) to the places it occurs: the documents, or the rows, that contain it. A forward index runs the other way, from a document to its terms, and answering "which documents contain X" from one means reading each document in turn. The inverted index exists to skip that scan, and it pays for the speed when a document is added, because each of the document's distinct terms gets a new entry.
Building one is mostly a sort. Each document gets an integer number. Its text is split into tokens and, depending on how the analyzer is set up, normalized, for instance lowercased so that "Friends" and "friends" become one term; an identifier field can instead be indexed literally as a single term. The result is a list of document and term pairs grouped by document, which is the forward index. Sorting those pairs by term instead groups all occurrences of a term together, and the grouped result splits into two parts: a dictionary of terms, kept in sorted order so a term can be found quickly, and one postings list per term holding the matching document numbers. Postings lists get large, so engines compress them, for instance by storing the gap from the previous document number rather than the number itself.
A posting can carry more than a doc ID, and what it carries decides which queries the index can answer. A record-level index stores just the document list. A word-level index also stores the position of each occurrence, which is what a phrase query needs, at the cost of more space and more work at index time. Lucene 10.1 keeps these as separate parts of each segment: a term dictionary with each term's document count and pointers into the frequency data (which documents, and how often the term occurs in each) and the proximity data (positions).
| Stored per posting | Query it answers | Cost |
|---|---|---|
Doc ID | Does this term appear in this document; boolean AND, OR, NOT filters, with no ranking | Smallest index |
Doc ID and term frequency | Rank a document higher when the term repeats in it | A count per posting |
Doc ID, frequency and positions | Phrase and proximity queries: words next to each other or within a distance | A list of integers per posting |
Doc ID, frequency, positions and character offsets | Mapping a hit back to its characters in the source text, for highlighting | Largest index |
Answering a query starts in the dictionary: look up each term, follow its pointer to the postings, then combine the lists, an intersection for AND and a union for OR. Because each list is in ascending doc ID order, an AND can walk two lists in step and keep the IDs they share. Our advice: begin with the rarest term, which the document count stored in the dictionary tells you, so the working set stays small; that count also feeds ranking later.
Writes are where the shape bites. Adding a document means an insert into one posting list per distinct term, so engines avoid editing lists in place. Lucene 10.1 writes new documents into fresh segments, each an independent index that can be searched on its own, and merges segments over time; a deleted document is marked in a live-documents file and dropped at the next merge of its segment, and an update is a delete followed by a fresh insert of the whole document. PostgreSQL 17's GIN index (Generalized Inverted Index) takes a similar route: with fastupdate on, new entries go into an unsorted pending list and are moved into the main structure in bulk when the table is vacuumed, when the list grows past gin_pending_list_limit, or when you call the cleanup function. A search must scan the pending list as well as the index, so a long list slows reads, and the update that trips the limit pays for the cleanup itself.
When to use it
Reach for one when the question is "which items contain this value" and each item holds many values: words in a document, tags on a post, keys in a JSON object, elements of an array. GIN is built for that shape, composite items searched by element, and stores each key once, so it stays compact when the same key appears in many rows. The same structure serves faceted filters (all products tagged "waterproof") and log search, where the term is a field value rather than a word.
Decide early what each posting carries, since that fixes the queries you can serve: doc IDs for filters, frequencies for ranking, positions for phrases, offsets for highlighting. Lucene 10.1 lets a field omit frequencies, and skips the proximity data entirely when no field keeps positions, so the choice is per field rather than per index. A strong answer names the level and why: a tag filter does not need positions; a search box that offers phrase or proximity matching over article bodies does.
When not to
Equality and range lookups on one value per row (a user by ID, orders in a date range) belong to an ordinary B-tree index. With one key per row there is nothing to turn around: GIN is designed for composite items searched by element, and its main advantage, storing a key once for the many rows that share it, does not apply when each row brings its own key. An inverted index there adds write cost for little gain.
A heavy write stream where each row must be searchable at once is a poor fit. In PostgreSQL 17, GIN inserts are slow because one row yields many keys; the usual advice is to drop the index before a bulk load and rebuild it after, and to turn fastupdate off when steady response time matters more than update speed. If the data set is small, a scan over a forward index is simpler and fast enough; add the inverted index when the scan, not the write, is the bottleneck.
Typo tolerance and meaning-based similarity are not what the structure is built for: a lookup finds the term that matches after normalization. Prefixes are a partial exception, since a sorted term dictionary can be scanned from a prefix, and the same dictionary can be walked with an automaton for fuzzy matches; GIN can match a range of keys rather than one exact key. Each of these turns one query term into many candidate terms, so the work per query grows with the width of the match. For autocomplete as the main workload, tries are the structure made for prefixes; for "documents about the same topic in other words", the job belongs to an embedding index, the retrieval step in retrieval-augmented generation.
Compared
| Structure | Best at | Weak at | Pick it when |
|---|---|---|---|
Forward index or full scan | Cheap writes, nothing extra to maintain | A query reads each document in turn | The set is small or searches are rare, so the scan costs less than the upkeep |
B-tree on a column | Equality and ranges on one value per row | Finding rows by an element inside text, an array or a JSON value | Each row has one key and you need ordering or ranges; see database indexes |
Inverted index, doc IDs per posting | Which items contain a term; boolean filters over tags and fields | Phrases, and ranking by how often a term repeats | The term either matches or it doesn't, as with tags, statuses and log fields |
Inverted index with frequencies and positions | Ranked text search, phrase and proximity queries | A larger index and more work per insert | A search box over bodies of text where word order matters |
In a picture
Step 1 of 4
Analyze the documents
Each document is split into tokens and normalized: lowercased, stemmed, stop words dropped if the engine is set to. The output is the stream of terms the index will know about.