# Inverted Index
URL: /docs/concepts/inverted-index

The core data structure behind full-text search — how Tachyon maps tokens to the documents that contain them.



A search engine that scanned every document for every query would be a
linear scan, not search. The inverted index is what avoids that: instead of
documents pointing to their words, it inverts the relationship — words point
to the documents that contain them.

## The structure [#the-structure]

For every distinct token in a collection, the inverted index holds a
**postings list**: the set of documents containing that token, along with
enough per-document information to score a match (at minimum, term
frequency). Looking up a query term means one lookup into the index, then
reading a postings list that — for most terms in a real corpus — is far
smaller than the collection itself.

```
"keyboard" → [doc 4 (tf=2), doc 19 (tf=1), doc 203 (tf=1), ...]
"wireless" → [doc 4 (tf=1), doc 87 (tf=3), ...]
```

A query for `"wireless keyboard"` intersects the two postings lists — only
documents appearing in both are candidates — rather than touching every
document in the collection.

## How Tachyon lays it out on disk [#how-tachyon-lays-it-out-on-disk]

The term-to-postings mapping itself is stored as an FST (finite-state
transducer) — a compact, sorted map from token to postings-list location,
efficient to look up and small on disk even for a large vocabulary.

Postings themselves are stored in fixed-size blocks, each carrying skip
metadata: the maximum document ID in the block and the maximum term
frequency any document in it achieves. That per-block metadata is what
makes [block-max WAND](/docs/concepts/block-max-wand) query pruning
possible — blocks can be skipped based on their metadata alone, without
being decoded.

Postings and the columnar field values used for filtering/sorting/faceting
are read lazily via mmap and decoded only for what a given query actually
touches — see [Persistence](/docs/persistence) for why that's what keeps
memory usage proportional to a workload's working set rather than to total
corpus size.

## Building the index [#building-the-index]

Every document indexed goes through the same path: text fields are
[tokenized](/docs/concepts/tokenization), each token is added to (or
updated in) the in-memory memtable's index structures, and the write is
appended to the write-ahead log before being acknowledged. The memtable's
index is periodically flushed into a new immutable, memory-mapped segment
on disk — see [Segment Merging](/docs/concepts/segment-merging) for how
segment count is kept bounded as data accumulates.

## Why this matters for query cost [#why-this-matters-for-query-cost]

Query latency in an inverted-index-based engine scales with postings-list
length for the terms involved, not with total collection size directly.
That's why the same query gets faster with more selective terms (rare words
have short postings lists) and slower with common terms — and it's the
reason [block-max WAND](/docs/concepts/block-max-wand) pruning matters most
for exactly the queries where a common term's postings list would otherwise
dominate the cost.