要做什么：几千篇文档，毫秒级全文检索

在内存里建一个迷你全文搜索引擎：给定查询词，按相关度排序返回文档。它不做磁盘持久化、不做增量更新、分词刻意从简——但倒排索引、BM25 打分、AND/OR 查询这些搜索引擎的骨架一件不少。写完你就知道 tantivy 这类现成库在替你做什么，以及什么时候该直接用库。

倒排索引：用一次建索引的成本换无数次快查

正排是”文档 → 内容”，查询时全量扫描；倒排反过来，”词 → 出现它的文档列表”：

文档 0: "the quick brown fox jumps over the lazy dog"
文档 1: "quick quick quick dog"
文档 2: "a lazy cat sleeps"

倒排索引（posting list）：
the   → {0}
quick → {0, 1}
lazy  → {0, 2}
dog   → {0, 1}
cat   → {2}
...

查 "quick AND dog" → {0,1} ∩ {0,1} = {0,1}
查 "quick OR cat"  → {0,1} ∪ {2}   = {0,1,2}

没有索引时，每个查询都要读完全部文档做匹配，成本与语料总量成正比；有了索引，查询成本只与”词的文档列表长度”相关。搜索引擎的全部魔法从这个交换开始：写多读少的数据，值得为读重建结构。

数据结构：HashMap 与 BTreeSet 的分工

use std::collections::{BTreeSet, HashMap};

type DocId = u32;   // 索引里数量最大的数据，id 宽度决定内存上限；u32 足够 42 亿篇

#[derive(Default)]
struct Index {
    docs: Vec<String>,                            // doc_id → 原文（展示用）
    doc_len: Vec<usize>,                          // 每篇 token 总数（BM25 长度归一用）
    tfs: Vec<HashMap<String, usize>>,             // 每篇的词频表
    postings: HashMap<String, BTreeSet<DocId>>,   // 词 → 出现它的文档集合
}

impl Index {
    fn add(&mut self, text: &str) -> DocId {
        let id = self.docs.len() as DocId;
        let tokens = tokenize(text);
        self.doc_len.push(tokens.len());
        let mut tf: HashMap<String, usize> = HashMap::new();
        for t in tokens {
            *tf.entry(t.clone()).or_insert(0) += 1;
            self.postings.entry(t).or_default().insert(id);
        }
        self.tfs.push(tf);
        self.docs.push(text.to_string());
        id
    }

    fn query_and(&self, terms: &[&str]) -> Vec<DocId> {
        let mut lists: Vec<&BTreeSet<DocId>> = terms
            .iter()
            .filter_map(|t| self.postings.get(*t))
            .collect();
        if lists.len() < terms.len() {
            return vec![];                        // 任一词不存在，AND 必为空
        }
        lists.sort_by_key(|l| l.len());           // 从最短的列表开始交，尽早缩小候选
        let mut acc: BTreeSet<DocId> = lists[0].clone();
        for other in &lists[1..] {
            acc = acc.intersection(*other).copied().collect();
            if acc.is_empty() {
                break;                            // 剪枝：空交集不用再算
            }
        }
        acc.into_iter().collect()
    }

    fn query_or(&self, terms: &[String]) -> BTreeSet<DocId> {
        let mut acc = BTreeSet::new();
        for t in terms {
            if let Some(list) = self.postings.get(t) {
                acc.extend(list.iter().copied());
            }
        }
        acc
    }
}

为什么 posting list 选 BTreeSet 而不是 HashSet：求交集两者都行，但 BTreeSet 的迭代天然有序——将来做”只搜最近 7 天的文档”这类按 doc_id 范围过滤时可以直接 range，HashSet 只能全量过滤。集合与迭代器的更多取舍见《Rust 集合与迭代器》。

反模式一：查询时全量扫描 docs 做 contains。千级文档一次查询扫几百 KB 还行，万级就开始疼，而且这条路没有任何优化空间——它就是线性扫描本身。索引的意义就是把”读时扫描”变成”写时组织”。

分词：中英文的诚实边界

fn is_cjk(c: char) -> bool {
    matches!(c as u32, 0x4E00..=0x9FFF)           // 基本区汉字，够本篇演示
}

fn tokenize(text: &str) -> Vec<String> {
    let mut tokens = Vec::new();
    let mut word = String::new();
    for ch in text.to_lowercase().chars() {
        if ch.is_ascii_alphanumeric() {
            word.push(ch);                        // 英文数字：攒成一个词
        } else if is_cjk(ch) {
            if !word.is_empty() {
                tokens.push(std::mem::take(&mut word));
            }
            tokens.push(ch.to_string());          // 中文：逐字成词（unigram）
        } else if !word.is_empty() {
            tokens.push(std::mem::take(&mut word));   // 分隔符：结算当前词
        }
    }
    if !word.is_empty() {
        tokens.push(word);
    }
    tokens
}

注意一个容易写错的地方：直接按”非字母数字”切分对中文无效——汉字本身是 alphanumeric，一整句中文会被当成一个超长 token，索引直接失效，所以中文必须显式逐字切开。

逐字切分的代价要说清楚：查”上海”会拆成”上””海”两个 token，一篇只含”海上有雾”的文档同样命中这两个 token——误召回。缓解办法是二元切分（bigram）：相邻两字组合成附加 token，查询也按 bigram 匹配，精度立刻上去；再进一步就要真正的中文分词库。这是刻意留下的边界：本篇目标是索引与打分骨架，分词是另一个独立的深坑，用最诚实的方式绕开它。

BM25：给”命中”排个序

布尔查询只回答”有没有”，不回答”哪个更相关”。拿词频直接排序是错的——一篇十万字的文章几乎必然包含任何查询词更多次。反模式二：拿 tf 排序不做事后校正。BM25 用两个旋钮治这个病：k1 让词频的贡献饱和（出现 3 次和出现 300 次差别不大），b 让文档长度归一（长文档不占便宜）：

const K1: f64 = 1.5;   // 词频饱和度
const B: f64 = 0.75;   // 长度归一强度

impl Index {
    fn avgdl(&self) -> f64 {
        if self.doc_len.is_empty() {
            return 1.0;
        }
        let total: usize = self.doc_len.iter().sum();
        (total as f64 / self.doc_len.len() as f64).max(1.0)
    }

    fn bm25(&self, terms: &[String], doc: DocId) -> f64 {
        let n = self.docs.len() as f64;
        let dl = self.doc_len[doc as usize] as f64;
        let avgdl = self.avgdl();
        let mut score = 0.0;
        for term in terms {
            let df = self.postings.get(term).map_or(0, |s| s.len()) as f64;
            if df == 0.0 {
                continue;
            }
            // idf：越少见的词信息量越大（与 tantivy/Lucene 同款公式）
            let idf = ((n - df + 0.5) / (df + 0.5) + 1.0).ln();
            let tf = self.tfs[doc as usize].get(term).copied().unwrap_or(0) as f64;
            score += idf * tf * (K1 + 1.0)
                / (tf + K1 * (1.0 - B + B * dl / avgdl));
        }
        score
    }

    fn search(&self, query: &str, top_k: usize) -> Vec<(DocId, f64)> {
        let terms = tokenize(query);
        let mut scored: Vec<(DocId, f64)> = self
            .query_or(&terms)                     // 候选集：任一词命中
            .into_iter()
            .map(|id| (id, self.bm25(&terms, id)))
            .collect();
        scored.sort_by(|a, b| b.1.total_cmp(&a.1));   // 分数降序
        scored.truncate(top_k);
        scored
    }
}

跑起来

fn main() {
    let mut idx = Index::default();
    idx.add("the quick brown fox jumps over the lazy dog");
    idx.add("quick quick quick dog");
    idx.add("a lazy cat sleeps");
    idx.add("上海花园的樱花开了，海上有雾");
    for (id, score) in idx.search("quick dog", 3) {
        println!("{score:.3}  #{}  {}", score, idx.docs[id as usize]);
    }
    for (id, score) in idx.search("上海", 3) {
        println!("{score:.3}  #{}  {}", score, idx.docs[id as usize]);
    }
}

Cargo.toml 不需要任何依赖。单元测试验证三条硬语义：

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

    #[test]
    fn and_query_requires_all_terms() {
        let mut idx = Index::default();
        idx.add("quick brown");
        idx.add("quick dog");
        assert_eq!(idx.query_and(&["quick", "dog"]), vec![1]);
    }

    #[test]
    fn missing_term_means_empty_and() {
        let idx = Index::default();
        assert!(idx.query_and(&["nope"]).is_empty());
    }

    #[test]
    fn bm25_prefers_relevant_short_doc() {
        let mut idx = Index::default();
        idx.add("dog");
        idx.add("dog dog dog cat elephant giraffe zebra lion tiger");   // 长且稀释
        assert_eq!(idx.search("dog", 1)[0].0, 0);   // 短而准的排第一
    }
}

测试的组织方式（单测贴着代码、cargo test 怎么跑）见《Cargo 与测试》。本篇代码全程没用到 Result——所有操作都不可失败；等你把索引落盘、读取外部文件时它就会登场，系统讲法见《Rust 错误处理》。

与 tantivy 对比：什么时候直接用库

诚实结论：这个迷你引擎的合理活动范围是”几千到几万篇文档、单进程、可全量重建索引”——配置项检索、小型站内搜索、内存里的过滤层。超出范围（百万文档、要持久化、要增量更新、中文分词质量要求高），直接用 tantivy，别自己补课；它尚处 1.0 之前的活跃开发期，小版本间有破坏性变更，所以这里不钉版本号，用法以官方文档为准。想把这个引擎挂到 HTTP 上变成搜索服务，《Axum 入门》是当前 Rust 后端的默认入口。

总结

• 搜索引擎的本质是时间换空间再换时间：写时组织 posting list，读时只碰候选集
• posting list 用 BTreeSet：有序性是免费送的，范围过滤和有序归并将来都用得上
• 中文按”非字母数字”切分是错的——汉字是 alphanumeric，必须显式处理，逐字切分是最诚实的起点
• BM25 的 k1 和 b 分别治”词频无限加权”与”长文档偏置”，比裸 tf 排序合理得多
• 知道什么时候该换库，比会用库更重要：规模、持久化、分词质量任何一项越界，就去用 tantivy

版本核实（以官方文档为准）：本篇代码仅用 Rust 标准库（std::collections），不依赖第三方 crate，近期稳定版工具链均可编译；对比对象 tantivy 处于 1.0 之前的活跃开发期，小版本间存在破坏性变更，故不钉具体版本号。文中性能数字均为估算口径，本站未实测。