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
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
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 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 for why that's what keeps memory usage proportional to a workload's working set rather than to total corpus size.
Building the index
Every document indexed goes through the same path: text fields are tokenized, 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 for how segment count is kept bounded as data accumulates.
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 pruning matters most for exactly the queries where a common term's postings list would otherwise dominate the cost.