Home / Keyword search / What Is an Inverted Index?

What Is an Inverted Index?

An inverted index is a data structure that maps each term to the list of documents containing it, so a search engine can find every document with a given word without scanning the collection. It is the core of keyword search, from library catalogues to the BM25 side of Weaviate’s hybrid search and engines such as Elasticsearch. Building one means tokenizing every document, then recording, for each term, which documents contain it and often how often and where. Those per-term lists are called postings lists. A query looks up its terms and combines their postings: intersecting them for AND, merging them for OR, and checking positions for phrases. Because the work depends on the number of matching postings rather than the size of the collection, lookups stay fast as data grows. Compression and skipping techniques keep the lists small and let scoring skip documents that cannot make the top results.

What is an inverted index in search?

An inverted index in search is a lookup table from terms to the documents that contain them, the reverse of storing each document with its list of words. The name comes from that reversal.

A normal document store is a forward index: document 1 contains these words, document 2 contains those. To find every document mentioning “refunds” with a forward index, you must read every document. An inverted index flips the relationship. It stores “refunds” once, followed by the IDs of the documents that contain it.

Weaviate’s documentation describes inverted indexes as mapping values, such as words or numbers, to the objects that contain them, enabling fast keyword search and filtering. The same structure serves both purposes. A keyword query looks up its words; a filter such as category equals billing looks up a value.

Inverted indexes predate computers in spirit: the index at the back of a book maps terms to pages. In search engines they are the foundation of keyword search, covered in what is keyword search, and of the full-text features described in full-text search. The structure is easiest to see in a small example.

How is an inverted index built?

An inverted index is built by tokenizing each document into terms, then adding the document’s ID, and optionally the term’s positions, to each term’s postings list. The result is a dictionary of terms, each pointing to its postings.

Take three documents. Document 1 says “Refunds are issued within 14 days”. Document 2 says “Refunds for digital goods are not issued”. Document 3 says “Shipping takes 3 to 5 days”. Lowercasing and splitting on non-alphanumeric characters gives 15 distinct terms across the three.

The index then lists, for each term, where it appears. “refunds” appears in documents 1 and 2, both at position 0. “days” appears in document 1 at position 5 and document 3 at position 5. “issued” appears in document 1 at position 2 and document 2 at position 6. “shipping” appears only in document 3.

Tokenization decides what the terms are, so it decides what can match. Weaviate’s documentation explains that text is tokenized according to each property’s configured method, and each token gets an entry pointing to the object containing it. The tokenizer options are compared in full-text search. With the index built, queries become list operations.

How does an inverted index answer a query?

An inverted index answers a query by fetching the postings list for each query term and combining the lists: intersection for AND, union for OR, and position checks for phrases. Only documents in those lists are ever touched.

In the example, the query “refunds AND days” fetches the postings for refunds, documents 1 and 2, and for days, documents 1 and 3. Their intersection is document 1. The query “refunds OR days” takes the union: documents 1, 2 and 3. Document 3 never needed to be read to rule it in or out for refunds.

Phrase queries use positions. “14 days” matches only where “14” is at position p and “days” at position p plus 1 in the same document, which is true for document 1. Without positions an index can say which documents contain both words, but not whether they are adjacent.

The cost of a query depends on how long the relevant postings lists are, not on how many documents exist. A rare term has a short list and is cheap. A very common term has a list nearly as long as the collection, which is one reason engines treat stopwords specially. Ranked queries go one step further than matching.

How does an inverted index support BM25 ranking?

An inverted index supports BM25 ranking by storing term frequencies in each posting and keeping document lengths and document counts, which are the inputs BM25 needs. Scores are computed from the postings at query time.

BM25 rewards documents where a query term appears often, discounts terms that appear in many documents, and adjusts for document length. The term frequency comes from the posting. The number of documents containing the term is the length of its postings list. Document lengths are stored separately. Weaviate’s keyword search documentation describes the score as based on the frequency of query tokens in the object properties and on the length of the properties.

The formula is explained in the BM25 algorithm, and its predecessor in TF-IDF. Weaviate uses BM25F, which scores each property separately so a title can weigh more than a body.

Scoring every document in every postings list would be slow for common terms. Engines therefore use algorithms that skip documents which cannot reach the top results. That is where the structure of the lists themselves becomes important.

How do engines keep inverted indexes small and fast?

Engines keep inverted indexes small and fast by compressing postings lists, storing them in blocks, and skipping blocks that cannot change the top results. These techniques matter most for long lists of common terms.

Postings lists are sorted by document ID, so engines store the gaps between IDs instead of the IDs themselves. Small gaps compress well with variable-length encodings. Lists are split into blocks with summary information, which lets a query jump ahead without decoding everything.

WAND, introduced by Andrei Broder and colleagues in 2003, uses an upper bound on each term’s possible score contribution to skip documents that cannot enter the top k. BlockMax WAND refines this with a bound per block. Weaviate’s documentation explains that it added BlockMax WAND in version 1.30. The index is organized in blocks, so blocks not relevant to the query can be skipped and far fewer documents need scoring.

Weaviate’s documentation also notes a side effect: scores with BlockMax WAND can differ slightly from the earlier algorithm, which it describes as expected behaviour. Index size and speed trade off against features such as positions. Engines also keep more than one kind of inverted index.

Which kinds of inverted index does Weaviate use?

Weaviate uses three kinds of inverted index: a searchable index for BM25 and hybrid search, a filterable index for match-based filters, and a range index for numeric and date comparisons. Each can be turned on or off per property.

Weaviate’s inverted index documentation describes indexSearchable as a map index suited to BM25 or hybrid search, applicable to text properties. indexFilterable is a roaring bitmap index for match-based filtering. indexRangeFilters, added in version 1.26, is a roaring bitmap index for range filters on int, number and date properties. The first two are on by default and the third is off.

Weaviate creates individual inverted indexes for each property and each index type, and combines them at query time rather than at index time. A title with both searchable and filterable indexes has two separate structures. The documentation notes that enabling more index types increases storage and indexing work, and that a property never queried can have its indexes turned off.

Roaring bitmaps suit filters because they represent sets of document IDs compactly and support fast set operations. A filter on category and year intersects two bitmaps. The schema decisions that follow are covered in search index schema design. Building an index by hand shows the core idea in a few lines.

How do you build a simple inverted index in Python?

You build a simple inverted index in Python with a dictionary that maps each term to a dictionary of document IDs and positions. AND and OR queries then become set operations on the keys.

import re
from collections import defaultdict

def tokenize(text):
    return re.findall(r"[a-z0-9]+", text.lower())

def build_index(docs):
    index = defaultdict(dict)                 # term -> {doc_id: [positions]}
    for doc_id, text in docs.items():
        for pos, term in enumerate(tokenize(text)):
            index[term].setdefault(doc_id, []).append(pos)
    return index

docs = {1: "Refunds are issued within 14 days",
        2: "Refunds for digital goods are not issued",
        3: "Shipping takes 3 to 5 days"}
index = build_index(docs)

print(set(index["refunds"]) & set(index["days"]))   # AND: {1}
print(set(index["refunds"]) | set(index["days"]))   # OR: {1, 2, 3}

The code reproduces the example: refunds maps to documents 1 and 2, days to documents 1 and 3, and the index holds 15 distinct terms. The AND query returns document 1 and the OR query returns all three. It was run as a check and prints those sets.

Real engines add much more: on-disk storage, compression, deletes and updates, stopword handling, stemming, BM25 scoring and concurrency. The structure underneath is the same. Its limits explain why semantic search exists.

What are the limits of an inverted index?

The main limit of an inverted index is that it matches exact tokens, so it cannot find documents that use different words for the same idea. A query for “cancel subscription” misses “end membership”.

The index only knows the terms it stored. Stemming and synonym lists widen matches, but each must be built and maintained by hand. Misspellings miss unless fuzzy matching or trigram tokenization is added. The problem is described in the vocabulary mismatch problem, and the word-form fixes in stemming and lemmatization.

Vector indexes take the opposite approach. They store an embedding per document and find nearest neighbours, so meaning can match without shared words. They are weaker on rare exact tokens such as product codes, where the inverted index excels.

That is why many semantic search systems keep both. Weaviate’s hybrid search runs a BM25 search on the inverted index and a vector search together and fuses the results, as explained in hybrid search. The comparison of the two index types is in semantic indexing and vector indexes.

An inverted index maps each term to the documents that contain it, so keyword search reads only the postings for the query’s terms. Tokenization decides the terms, positions enable phrase matching, and term frequencies and lengths feed BM25. Compression, blocks and BlockMax WAND keep large indexes fast. Weaviate keeps separate searchable, filterable and range indexes per property. The structure matches exact tokens, which makes it precise for names and codes and blind to synonyms, so semantic systems pair it with a vector index in hybrid search.