Skip to content
Tutorials Center
My learning

Topics

Lesson 57 of 79 ยท Storage and Indexing

Inverted Indexes and Text Retrieval

Build an inverted index from scratch, answer AND and OR text queries, rank results with TF-IDF and cosine similarity, and see how databases and search engines use them.

A B-tree is excellent when you know the exact key or a range of keys. It is useless for the question people actually ask a search box: "which documents mention inverted index?" The condition WHERE body LIKE '%index%' cannot use a B-tree, because the match can start anywhere in the text, so the database has to read every row. For millions of documents that is far too slow.

Text retrieval turns the problem around. Instead of storing, for each document, the words it contains, we store, for each word, the documents that contain it. That structure is the inverted index, and it powers web search engines, Lucene and Elasticsearch, and the full-text features of PostgreSQL, MySQL and SQLite. This lesson builds one from scratch, then adds ranking with TF-IDF and the vector space model. It extends the index types you already know and is a first step toward data mining over text.

Turn the index around

Forward index Document, then its words.
Inverted index Word, then its documents.

Looking up a word is now one dictionary lookup.

1 / 2

The structure of an inverted index

An inverted index has two parts:

  • The dictionary (vocabulary): every distinct term, kept sorted or in a hash table so a term can be found quickly.
  • The postings lists: for each term, the list of documents that contain it, usually with extra data such as the term frequency (how often the term occurs in that document) and sometimes the positions of each occurrence.
TEXT
term        postings (doc_id: term frequency)
database    1:2   4:1
index       1:1   2:1   3:1   4:1
inverted    2:1   3:1

Postings lists are kept sorted by document id. That makes combining them cheap: to find the documents that contain both terms, walk two sorted lists side by side, like the merge step of a merge sort. Real engines also compress the lists: instead of the ids 1000, 1005, 1011 they store the gaps 1000, 5, 6 (delta encoding), which are small numbers that need few bits.

Building the index

Before indexing, text goes through analysis:

  1. Tokenization: split the text into words.
  2. Normalization: lowercase everything, perhaps remove accents.
  3. Stop-word removal: drop extremely common words such as "a", "the" and "and" that carry little meaning (many modern engines keep them and rely on weighting instead).
  4. Stemming or lemmatization (optional): reduce "takes", "taking" and "took" to a common form so that they match each other.

The same analysis must be applied to queries, otherwise "Indexes" in a query would never find "indexes" in a document. The first example indexes five tiny documents and answers boolean queries by intersecting postings lists.

Python Build an inverted index and run AND queries

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The term index occurs in four documents, but inverted index together only in documents 2 and 3. Notice what the lookup did not do: it never touched document 5 or scanned any text. The cost of a query depends on the length of the postings lists of the query terms, not on the size of the collection.

The same idea fits in a relational table. The next example stores the postings as rows (term, doc_id, tf) and answers OR and AND searches in SQL. A real database does this for you inside its full-text index (PostgreSQL's GIN index over a tsvector, MySQL's FULLTEXT, SQLite's FTS5 module); the site's browser SQL engine has no FTS5, so we build the table by hand.

SQL Postings as a table: OR search, AND search, document frequency

Press Run (or Ctrl + Enter) to see the result here.

The primary key (term, doc_id) is itself a B-tree over the postings, so finding every document for a term is an index range scan. The HAVING COUNT(DISTINCT term) = 2 trick is the SQL version of intersecting two lists. The last query shows the document frequency (df), the number of documents that contain a term, which the next section needs.

Ranking with TF-IDF

Boolean matching returns a set. Users want an ordered list with the best results first. The oldest practical idea is TF-IDF, built on two observations:

  • A document that mentions a term many times is probably more about it. This is the term frequency (tf).
  • A term that occurs in nearly every document tells you nothing, while a rare term is a strong clue. This is captured by the inverse document frequency: idf(t) = ln(N / df(t)), where N is the number of documents and df(t) is how many contain the term.

The weight of a term in a document is tf x idf. Words like "index" in a collection about databases get a small weight; "pasta" gets a large one. (Variants exist: sublinear tf such as 1 + ln(tf), smoothed idf, and length normalization. This lesson uses the plain form.)

The vector space model and cosine similarity

The vector space model treats every document as a point in a space with one dimension per term, and the coordinates are the TF-IDF weights. A query is turned into a vector the same way. Documents whose vectors point in nearly the same direction as the query are relevant. Direction, not length, is what matters, so we use the cosine of the angle between the two vectors:

TEXT
cosine(q, d) = (q . d) / (|q| x |d|)

The dot product multiplies the weights of terms the two vectors share. Dividing by the lengths stops long documents from winning just because they contain more words. A cosine of 1 means identical direction; 0 means no terms in common.

Python TF-IDF weights and cosine-ranked search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the three results. For "database index", document 1 scores far above document 4, because it says "database" twice and "database" has a higher idf than "index" (which appears in four of the five documents, so its idf is only 0.223). Document 3 also scores a tiny amount because it shares the nearly worthless word "index". The pasta query finds document 5 only through "pasta": the document says "takes" and the query says "take", so without stemming those two do not match. That is exactly why real engines add stemming and other analysis steps.

From the toy to real systems

Production search engines refine every part of this picture:

  • BM25 replaces plain TF-IDF in Lucene, Elasticsearch and PostgreSQL extensions. It saturates term frequency (the tenth occurrence matters much less than the first) and normalizes by document length with tunable parameters.
  • Positional postings store where each word occurs, which allows phrase queries ("inverted index" as adjacent words) and proximity searches.
  • Skip pointers and compression make intersecting huge postings lists fast.
  • Segment-based indexing: new documents go into small immutable segments that are merged in the background, an idea shared with the LSM trees used for write-heavy storage.
  • Distribution: an index is split into shards across servers and the partial results are merged, as in partitioning. The Elasticsearch inverted index lesson shows this from the search server's side.
  • Embeddings: newer systems add vector similarity on learned embeddings. The cosine idea is the same, but the dimensions are learned meanings instead of words.

In SQL databases you rarely build postings yourself. You declare a full-text index and use its operators, for example to_tsvector and to_tsquery in PostgreSQL, MATCH ... AGAINST in MySQL or MATCH on an FTS5 table in SQLite (read-only illustrations here, because they need a server or a module our runner lacks):

SQL
-- PostgreSQL: GIN index over a tsvector, read-only illustration
CREATE INDEX docs_fts ON docs USING GIN (to_tsvector('english', body));
SELECT id FROM docs
WHERE to_tsvector('english', body) @@ to_tsquery('english', 'inverted & index');

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why can a B-tree not speed up WHERE body LIKE '%index%'?

    A B-tree is ordered by the beginning of the value. A pattern with a leading wildcard has no fixed prefix, so every row must be examined. An inverted index looks up whole terms instead.
  2. 2. What does a postings list contain?

    The inverted index maps each term to its postings list, sorted by document id so that lists can be merged quickly.
  3. 3. A term that appears in every document of the collection gets what idf (using ln(N / df))?

    When df equals N, N / df is 1 and ln(1) is 0. A word that occurs everywhere cannot help distinguish documents.
  4. 4. Why divide by the vector lengths in cosine similarity?

    Cosine compares direction only. Without length normalization a long document would collect large dot products simply by containing many terms.
  5. 5. Why did the query "pasta take" not match the word "takes" in the demo?

    Terms are matched exactly after analysis. Stemming or lemmatization maps word forms to one term.

Summary

  • An inverted index maps each term to a sorted postings list of documents (with term frequencies or positions), so a text query costs about the size of its postings lists, not of the collection.
  • Text is analyzed first: tokenize, normalize, optionally remove stop words and stem, and queries use the same analysis.
  • AND queries intersect postings lists, OR queries unite them; both are easy to express with GROUP BY and HAVING COUNT(DISTINCT term) over a postings table.
  • TF-IDF weighs a term by how often it occurs in the document and how rare it is in the collection; rare terms score higher.
  • In the vector space model documents and queries are weighted vectors, and cosine similarity ranks them by direction.
  • Real engines use BM25, positions, compression, segments and sharding; databases expose this through full-text indexes.

Next: Query Processing Pipeline.