An in-memory inverted index

Step 2 of 12, and haystack gets its first data structure. By the end of this page the engine holds a handful of documents in memory and answers a query by looking a term up instead of reading every document: one hash map from term to document ids, plus the small amount of code that keeps that map honest. Nothing is written to disk yet and nothing is ranked yet — the index this step builds is what the next ten steps grow.

The starting state is an empty directory, because step 1 committed no code. If you would rather start from the finished version of this step, clone the examples repository and git checkout search-ch02; that is shown at the end.

Create the crate

cargo new haystack
cd haystack

That makes a binary crate, which is what the finished engine is: haystack index, haystack query and haystack serve are one program with three jobs, and this step writes the first lines of it. The track needs no third-party crates until step 9, so the manifest Cargo generates is already the whole manifest:

[package]
name = "haystack"
version = "0.1.0"
edition = "2024"

[dependencies]

Every article in this track is written and verified against Rust 1.99.0, where edition 2024 is what a current toolchain writes by default, so the file on your machine is probably already this one.

In the examples repository the project sits at search-engine/: the track directory is the project root, and the crate inside it is haystack. The tag at the end of this page checks out straight into it.

What the index holds

Two fields, and the engine is these two fields plus the code that fills them:

use std::collections::HashMap;

struct Index {
    /// term -> document ids. Every list is ascending and duplicate-free.
    postings: HashMap<String, Vec<u32>>,
    /// document id -> the path the document was indexed under.
    documents: Vec<String>,
}

postings is the inversion itself. Instead of each document pointing at the terms it contains, every term points at the documents that contain it. The value is the postings list: the ids, in the order the documents were added. documents is the other direction, and it earns its place immediately — a search that answers “documents 1 and 2” has answered nothing. The path is what whoever runs the query needs to see.

Three decisions are worth slowing down for:

• Ids are u32, assigned in insertion order. A few million documents fit comfortably, and the number doubles as an index into documents, so going from an id back to a path is one array access rather than another lookup.
• The map is a HashMap. Lookup is the operation that matters, and nothing needs the dictionary in sorted order until step 4 writes it to a file, where sorting the keys once is cheaper than keeping them sorted through every insertion.
• Each postings list is ascending and duplicate-free. Both properties come from how documents are added, below, and the tests pin them.

The whole file

This is src/main.rs in full — the index, the tokeniser, a main that demonstrates both, and the tests. Later steps change parts of this file; the shape stays.

src/main.rs

use std::collections::HashMap;

/// An inverted index: for each term, the documents that contain it.
struct Index {
    /// term -> document ids. Every list is ascending and duplicate-free.
    postings: HashMap<String, Vec<u32>>,
    /// document id -> the path the document was indexed under.
    documents: Vec<String>,
}

impl Index {
    fn new() -> Self {
        Index {
            postings: HashMap::new(),
            documents: Vec::new(),
        }
    }

    /// Index one document. `path` is its id; `text` is its contents.
    /// Returns the id the document was given.
    fn add_document(&mut self, path: &str, text: &str) -> u32 {
        let id = self.documents.len() as u32;
        self.documents.push(path.to_string());

        // The terms this document contributes, each at most once.
        let mut terms: Vec<&str> = tokenize(text).collect();
        terms.sort_unstable();
        terms.dedup();

        for term in terms {
            self.postings.entry(term.to_string()).or_default().push(id);
        }

        id
    }

    /// The ids of the documents containing `term`, in insertion order.
    /// Empty when the index has never seen the term.
    fn search(&self, term: &str) -> &[u32] {
        self.postings.get(term).map(Vec::as_slice).unwrap_or(&[])
    }

    /// The path a document was indexed under.
    fn path(&self, id: u32) -> &str {
        &self.documents[id as usize]
    }

    fn documents(&self) -> usize {
        self.documents.len()
    }

    fn terms(&self) -> usize {
        self.postings.len()
    }
}

/// Split text into terms. Whitespace only, for now: casing, stop words and
/// stemming arrive in step 3, and nothing outside this function changes then.
fn tokenize(text: &str) -> impl Iterator<Item = &str> {
    text.split_whitespace()
}

fn main() {
    let documents = [
        (
            "docs/ownership.md",
            "Ownership and borrowing are the two ideas Rust is built on. Every value has one owner, and the owner going out of scope drops it.",
        ),
        (
            "docs/borrow-checker.md",
            "The borrow checker enforces the borrowing rules at compile time. A borrow must not outlive the owner of the borrowed value.",
        ),
        (
            "docs/lifetimes.md",
            "A lifetime is the region of code for which a reference is valid. The borrow checker uses lifetimes to keep every reference in scope.",
        ),
        (
            "docs/iterators.md",
            "Iterators are lazy: each call to next advances the iterator by one. An adapter such as map borrows the iterator it wraps.",
        ),
        (
            "docs/error-handling.md",
            "Recoverable errors are values of type Result. The question mark operator returns an error to the caller early.",
        ),
    ];

    let mut index = Index::new();
    for (path, text) in &documents {
        index.add_document(path, text);
    }
    println!(
        "{} documents, {} distinct terms",
        index.documents(),
        index.terms()
    );

    println!("\npostings for \"borrow\": {:?}", index.search("borrow"));

    println!("\nquery \"borrow\":");
    for id in index.search("borrow") {
        println!("  {}", index.path(*id));
    }

    println!("\nthe same documents from a scan:");
    for (path, text) in &documents {
        if tokenize(text).any(|term| term == "borrow") {
            println!("  {}", path);
        }
    }

    println!("\nqueries that miss:");
    for query in ["ownership", "valid"] {
        let hits = index.search(query);
        if hits.is_empty() {
            println!("  {:?} -> no documents", query);
        } else {
            for id in hits {
                println!("  {:?} -> {}", query, index.path(*id));
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn sample() -> Index {
        let mut index = Index::new();
        index.add_document("a.md", "the quick brown fox");
        index.add_document("b.md", "the lazy dog, the quick cat");
        index
    }

    #[test]
    fn add_document_returns_the_id_it_gave() {
        let mut index = Index::new();
        assert_eq!(index.add_document("a.md", "fox"), 0);
        assert_eq!(index.add_document("b.md", "fox"), 1);
    }

    #[test]
    fn a_term_in_two_documents_lists_both() {
        let index = sample();
        assert_eq!(index.search("the"), &[0, 1]);
        assert_eq!(index.search("quick"), &[0, 1]);
    }

    #[test]
    fn a_term_repeated_in_one_document_lists_it_once() {
        let mut index = Index::new();
        index.add_document("a.md", "fox fox fox");
        assert_eq!(index.search("fox"), &[0]);
    }

    #[test]
    fn ids_are_in_insertion_order() {
        let index = sample();
        assert_eq!(index.path(0), "a.md");
        assert_eq!(index.path(1), "b.md");
        assert_eq!(index.search("dog,"), &[1]);
    }

    #[test]
    fn a_missing_term_is_empty_not_an_error() {
        let index = sample();
        assert!(index.search("wolf").is_empty());
    }

    #[test]
    fn casing_and_punctuation_stay_part_of_the_term_for_now() {
        let index = sample();
        assert!(index.search("Fox").is_empty());
        assert_eq!(index.search("fox"), &[0]);
        assert!(index.search("dog").is_empty());
    }
}

▶Run this in the Rust Playground

One id per term per document

add_document starts by collecting the document’s own terms, then sorts and deduplicates them:

fn main() {
    let text = "fox fox fox";
    let mut terms: Vec<&str> = text.split_whitespace().collect();
    terms.sort_unstable();
    terms.dedup();
    println!("{terms:?}");
}

▶Run this in the Rust Playground

["fox"]

A document that says “fox” three times contributes “fox” once — those are the three lines from add_document, with tokenize inlined so the snippet runs on its own. Doing this once per document, rather than checking the postings list on every append, is what keeps each list duplicate-free for free: ids arrive in ascending order because documents are numbered as they are added, so appending is all the loop has to do. Step 5 swaps this deduplication for a count, when term frequency becomes something the index stores.

The tokeniser is one function, and it is the part step 3 replaces

fn tokenize(text: &str) -> impl Iterator<Item = &str> {
    text.split_whitespace()
}

Whitespace, and nothing else. “Borrow” and “borrow” are different terms, “scope.” is not “scope”, and “the” is indexed like any other word. That is wrong in every way a search engine can be wrong, and it is deliberate: step 3 replaces the body of this one function — case folding, stop words, stemming — and nothing else in the file changes. Seams like that are why this track is twelve small articles rather than one large one.

One detail edition 2024 buys: the returned iterator borrows text without the + '_ that an older edition asks for in the return type.

What a query is at this stage

search is a dictionary lookup, and nothing more. No ranking, no merging of several terms’ lists, no phrase handling — those arrive in steps 5 to 7. What it already promises is the shape later steps keep: an unknown term is an empty result rather than an error, and the ids come back in a stable order.

The slice is borrowed from the index, so holding it freezes the index: no add_document while a search result is alive. Adding one more document while the results are in hand is a borrow error, not a surprise at runtime:

use std::collections::HashMap;

fn main() {
    let mut postings: HashMap<String, Vec<u32>> = HashMap::new();
    postings.entry("borrow".to_string()).or_default().push(1);

    let hits = postings.get("borrow").map(Vec::as_slice).unwrap_or(&[]);
    postings.entry("checker".to_string()).or_default().push(2);
    println!("{hits:?}");
}

▶Run this in the Rust Playground

error[E0502]: cannot borrow `postings` as mutable because it is also borrowed as immutable
 --> src/main.rs:8:5
  |
7 |     let hits = postings.get("borrow").map(Vec::as_slice).unwrap_or(&[]);
  |                -------- immutable borrow occurs here
8 |     postings.entry("checker".to_string()).or_default().push(2);
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here
9 |     println!("{hits:?}");
  |                ---- immutable borrow later used here

For more information about this error, try `rustc --explain E0502`.

When the hits need to outlive the search, collect them first: index.search("borrow").to_vec() hands back an owned Vec<u32> and releases the borrow.

Why entry() wants an owned key

The line in add_document that looks like it carries a stray allocation is self.postings.entry(term.to_string()).or_default().push(id);. entry takes the key by value and the map’s key type is String, so the term has to become owned on the way in. Dropping the conversion is the obvious thing to try:

use std::collections::HashMap;

fn main() {
    let mut postings: HashMap<String, Vec<u32>> = HashMap::new();
    postings.entry("borrow").or_default().push(1);
    println!("{postings:?}");
}

▶Run this in the Rust Playground

error[E0308]: mismatched types
    --> src/main.rs:5:20
     |
5 |     postings.entry("borrow").or_default().push(1);
     |              ----- ^^^^^^^^ expected `String`, found `&str`
     |              |
     |              arguments to this method are incorrect
     |
help: the return type of this call is `&'static str` due to the type of the argument passed
    --> src/main.rs:5:5
     |
5 |     postings.entry("borrow").or_default().push(1);
     |     ^^^^^^^^^^^^^^^--------^
     |                    |
     |                    this argument influences the return type of `entry`
note: method defined here
    --> /Users/rango/.rustup/toolchains/1.99.0-aarch64-apple-darwin/lib/rustlib/src/rust/library/std/src/collections/hash/map.rs:1012:12
     |
1012 |     pub fn entry(&mut self, key: K) -> Entry<'_, K, V, A> {
     |            ^^^^^
help: try using a conversion method
     |
5 |     postings.entry("borrow".to_string()).or_default().push(1);
     |                            ++++++++++++

For more information about this error, try `rustc --explain E0308`.

The map owns its keys — that is what lets search take a borrowed &str and still find the term — and every insertion pays for one String to keep it that way.

What the tokeniser does to real text

One sentence through the step 2 tokeniser, to see both of its failures at once:

fn tokenize(text: &str) -> impl Iterator<Item = &str> {
    text.split_whitespace()
}

fn main() {
    let sentence = "A lifetime is the region of code for which a reference is valid.";
    for term in tokenize(sentence) {
        println!("{term}");
    }
}

▶Run this in the Rust Playground

A
lifetime
is
the
region
of
code
for
which
a
reference
is
valid.

“valid.” is a term of its own, so a query for “valid” finds nothing even though the word sits right there in the sentence. “A” is a different term from “a”, and the same failure means a reader typing “ownership” gets nothing back, because the only occurrence in the corpus starts a sentence with a capital O. Step 3 fixes both.

See it run

From the haystack directory:

cargo run

5 documents, 82 distinct terms

postings for "borrow": [1, 2]

query "borrow":
  docs/borrow-checker.md
  docs/lifetimes.md

the same documents from a scan:
  docs/borrow-checker.md
  docs/lifetimes.md

queries that miss:
  "ownership" -> no documents
  "valid" -> no documents

Five documents, 82 distinct terms. The postings list for “borrow” is [1, 2], and the query prints the paths of the two documents that contain the word. The scan underneath is the same answer the slow way, re-read from the raw text; it is there to make the point of the index visible. The scan’s cost grows with the corpus, and the lookup’s does not.

The last two lines are the tokeniser’s misses, printed rather than hidden.

The tests:

cargo test

running 6 tests
test tests::a_term_repeated_in_one_document_lists_it_once ... ok
test tests::a_missing_term_is_empty_not_an_error ... ok
test tests::add_document_returns_the_id_it_gave ... ok
test tests::a_term_in_two_documents_lists_both ... ok
test tests::casing_and_punctuation_stay_part_of_the_term_for_now ... ok
test tests::ids_are_in_insertion_order ... ok

test result: ok. 6 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

Six tests, and they pin invariants rather than implementation: one id per term per document, ascending ids, a missing term is empty, and the casing and punctuation behaviour that step 3 will change. The test order is shuffled on every run, so the names come out in a different order each time and nothing should be read into it.

Where this lands in the repository

This step’s state is tagged search-ch02 in the examples repository:

git clone https://github.com/hackingwithrust/examples
cd examples/search-engine
git checkout search-ch02

The tag contains the Cargo.toml above, src/main.rs in full, and a README. If your build misbehaves, diff your files against the tag’s — the drifting line is usually findable that way. The track overview keeps the step list current.

Next

Step 3, Tokenising and normalising text, replaces the body of tokenize: case folding, a stop word list, and a small stemmer, so that “borrow”, “borrowing”, “borrows” and “borrowed” stop being four unrelated terms. The index does not change; the terms going into it do.