> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/search/inverted_index.md).

# Inverted Index

## Basic idea

A map from term → posting list (the documents containing the term, often with positions). Lets a search engine answer "which docs contain word X?" in time proportional to the result size, not the corpus size.

## Key formulas

* Index size: $\sum\_t |postings(t)|$
* Query (AND): intersect posting lists in $O(\sum |L\_i|)$
* TF-IDF weight: $w(t,d) = tf(t,d) \cdot \log(N/df(t))$

For efficient storage of inverted indicies refer to ARTs (Adaptive Radix Tree)