用 Rust 从零实现倒排索引:全文搜索的底座只有三个数据结构
"搜索"这个词被用得太随便了。数据库的
LIKE '%关键词%'也叫搜索,Elasticsearch 也叫搜索,但它们的本质完全不同。
前者是扫描:逐行检查有没有子串。后者是索引:预先建立起"词 → 文档"的映射,查询时直接查表。
这篇从零实现倒排索引。写完你会发现,搜索引擎的骨架比想象中朴素得多。
先看正排和倒排的区别
假设有三篇文档:
doc 1: "rust 异步编程 入门"
doc 2: "rust 所有权 详解"
doc 3: "异步 编程 实践"正排索引是"文档 → 它包含的词",这也是文档本来的样子。要查"哪些文档包含 rust",只能遍历所有文档。
倒排索引把这个关系反过来:
rust -> [1, 2]
异步 -> [1, 3]
编程 -> [1, 3]
入门 -> [1]
所有权 -> [2]
详解 -> [2]
实践 -> [3]于是查"包含 rust 的文档"变成了一次哈希查找,O(1)。
倒排索引的本质就是"反向的正排索引"。 一句话说完了。
三个核心结构
一个完整的倒排索引由三部分组成:
pub struct InvertedIndex {
/// 1. 词典:词 -> 倒排表在 postings 里的位置
dictionary: std::collections::HashMap<String, TermInfo>,
/// 2. 倒排表:doc_id 的列表(有序列,用于求交集)
postings: Vec<Posting>,
/// 3. 位置表:每个词在文档里的位置(用于短语查询)
/// 这里直接放在 Posting 里
doc_count: usize,
}
#[derive(Debug, Clone)]
pub struct TermInfo {
/// 有多少文档包含这个词
pub doc_freq: u32,
/// 指向 postings 的起始位置
pub postings_start: u32,
pub postings_len: u32,
}
#[derive(Debug, Clone)]
pub struct Posting {
pub doc_id: u32,
/// 这个词在这篇文档里出现的次数(term frequency)
pub term_freq: u32,
/// 出现的位置,用于短语查询
pub positions: Vec<u32>,
}为什么 postings 是独立的 Vec 而不是 HashMap<String, Vec<Posting>>?
因为放在一起会导致大量分散的小分配,缓存不友好。把倒排表连续存放,查询"rust"时读到的是一段连续内存——这对于动辄几百万个 posting 的场景,性能差异是数量级的。
第一步:分词
分词(tokenization)把文本切成词。英文很简单,中文才是真难点。
先做通用部分:转小写、去掉标点、按空白切。
fn tokenize_en(text: &str) -> Vec<String> {
text.to_lowercase()
.split(|c: char| !c.is_alphanumeric())
.filter(|s| !s.is_empty())
.map(|s| s.to_string())
.collect()
}英文还要做词干还原(stemming),否则 running 和 run 是两个不同的词:
/// 极简的英语后缀剥离(真实实现用 Porter Stemmer)
fn stem_en(word: &str) -> String {
for suffix in ["ing", "ed", "s", "ly"] {
if word.len() > suffix.len() + 2 && word.ends_with(suffix) {
return word[..word.len() - suffix.len()].to_string();
}
}
word.to_string()
}中文分词的现实
中文没有空格,"异步编程入门" 要怎么切?三种主流方案:
| 方案 | 原理 | 优点 | 缺点 |
|---|---|---|---|
| 按字切 | 每个汉字一个 token | 简单,召回高 | 精度差,索引大 |
| 二元切分(bigram) | 每两个相邻字 | 简单,召回高 | 索引更大 |
| 词典 + 统计 | 词库匹配 + HMM | 精度好 | 需要词典 |
工程上最省事、效果也不差的是二元切分:
fn tokenize_zh_bigram(text: &str) -> Vec<String> {
let chars: Vec<char> = text
.chars()
.filter(|c| !c.is_whitespace() && !c.is_ascii_punctuation())
.collect();
let mut tokens = Vec::with_capacity(chars.len());
for w in chars.windows(2) {
tokens.push(w.iter().collect());
}
tokens
}"异步编程" 切出来是 ["异步", "步编", "编程"]——windows(2) 是滑动窗口,依次取 异+步、步+编、编+程。
查询时同样切:查"异步"这个词,会变成 ["异步"](只有一个 bigram),然后去索引里找。
bigram 的好处是"不需要词典也能召回":用户搜"编程入门",切出 ["编程", "程入", "入门"],只要文档里有"编程"和"入门"(无论中间隔了什么),就能匹配上。
代价是索引膨胀:每个汉字都参与两个 bigram,索引大小大约是按词切分的 2-3 倍。
中文分词没有免费的午餐:要精度就要词典,要简单就要牺牲索引体积。 生产系统(如 Elasticsearch 的 IK 分词器)选的是"词典 + 统计",因为索引体积换得回来。
第二步:构建倒排表
遍历所有文档,切词,往倒排表里塞:
pub struct IndexBuilder {
/// 临时结构:词 -> (doc_id -> positions)
temp: std::collections::HashMap<String, std::collections::HashMap<u32, Vec<u32>>>,
doc_count: usize,
/// 每篇文档的长度(词数),BM25 需要
doc_lengths: Vec<u32>,
}
impl IndexBuilder {
pub fn add_document(&mut self, doc_id: u32, text: &str) {
let tokens = tokenize(text);
for (pos, token) in tokens.iter().enumerate() {
self.temp
.entry(token.clone())
.or_default()
.entry(doc_id)
.or_default()
.push(pos as u32);
}
self.doc_lengths.push(tokens.len() as u32);
self.doc_count += 1;
}
}为什么要用两层的 HashMap? 因为构建阶段最重要的是"能按 doc_id 聚合位置"。最后再展开成扁平的 postings 列表。
构建完成后展开:
pub fn build(self) -> InvertedIndex {
let mut dictionary = std::collections::HashMap::new();
let mut postings = Vec::new();
for (term, docs) in self.temp {
let start = postings.len() as u32;
// doc_id 必须排序!这是后面求交集的前提
let mut doc_ids: Vec<u32> = docs.keys().copied().collect();
doc_ids.sort_unstable();
for doc_id in &doc_ids {
let mut positions = docs[doc_id].clone();
positions.sort_unstable();
postings.push(Posting {
doc_id: *doc_id,
term_freq: positions.len() as u32,
positions,
});
}
dictionary.insert(
term,
TermInfo {
doc_freq: doc_ids.len() as u32,
postings_start: start,
postings_len: (postings.len() as u32) - start,
},
);
}
InvertedIndex {
dictionary,
postings,
doc_count: self.doc_count,
doc_lengths: self.doc_lengths,
}
}"doc_id 必须排序"是一条硬要求,不是优化。后面所有集合运算都建立在"有序"这个前提上。
倒排表按 doc_id 有序,是搜索引擎能用 O(n+m) 做多词交集的基础。 没排序就只能用哈希集合,那会丢掉位置信息的顺序性。
第三步:查询——多词求交集
查 "rust 异步" 要返回"同时包含两个词的文档"。这就是有序列表求交集:
/// 两个有序列表求交集,O(n + m)
fn intersect(a: &[u32], b: &[u32]) -> Vec<u32> {
let mut result = Vec::new();
let (mut i, mut j) = (0, 0);
while i < a.len() && j < b.len() {
match a[i].cmp(&b[j]) {
std::cmp::Ordering::Equal => {
result.push(a[i]);
i += 1;
j += 1;
}
std::cmp::Ordering::Less => i += 1,
std::cmp::Ordering::Greater => j += 1,
}
}
result
}这一步就是"跳表/有序列表求交"的经典实现,复杂度 O(n+m) 而非 O(n×m)。
工程上有个重要优化:先按 doc_freq 从小到大排序,再依次求交。
pub fn search_and(&self, terms: &[String]) -> Vec<u32> {
// 把词按出现文档数升序排列
let mut lists: Vec<Vec<u32>> = terms
.iter()
.filter_map(|t| self.postings_for(t))
.collect();
if lists.is_empty() {
return Vec::new();
}
lists.sort_by_key(|l| l.len());
// 从最短的开始交,让中间结果尽快变小
let mut result = lists[0].clone();
for list in &lists[1..] {
if result.is_empty() {
break; // 空集,不用再算
}
result = intersect(&result, list);
}
result
}为什么先交最短的? 因为中间结果会越来越小。假设三个词分别出现在 100 万、1000、10 篇文档里——先交 10 和 1000,得到最多 10 个候选,再和 100 万求交时,几乎不用遍历。
反过来先交 100 万和 1000,中间结果可能还是很大,白白浪费。
第四步:短语查询
"异步编程" 作为短语(而不是两个独立的词)要相邻才算匹配。这就是位置表的用途:
pub fn search_phrase(&self, terms: &[String]) -> Vec<u32> {
if terms.len() == 1 {
return self.search_and(terms);
}
// 先求交集拿到候选文档
let candidates = self.search_and(terms);
let mut result = Vec::new();
for doc_id in candidates {
// 逐个检查:第 i 个词的位置 +1 是否等于第 i+1 个词的位置
if self.positions_match(doc_id, terms) {
result.push(doc_id);
}
}
result
}
fn positions_match(&self, doc_id: u32, terms: &[String]) -> bool {
let positions: Vec<&Vec<u32>> = terms
.iter()
.filter_map(|t| self.get_positions(t, doc_id))
.collect();
if positions.len() != terms.len() {
return false;
}
// 以第一个词的位置为锚点,检查后续词是否依次相邻
for &start in positions[0] {
let matched = positions[1..].iter().enumerate().all(|(i, pos)| {
let expected = start + i as u32 + 1;
pos.binary_search(&expected).is_ok()
});
if matched {
return true;
}
}
false
}位置表是"短语查询"和"邻近度评分"的唯一依赖。 没有它,倒排索引只能做"词袋"检索。代价是索引体积大约翻倍——因为每个词都要存它的所有位置。
第五步:排序——BM25
拿到候选文档后,要按相关性排序。最经典的是 TF-IDF,而 BM25 是它的改进版,几乎是所有现代搜索引擎的默认选择。
先理解直觉:
- TF(词频):一个词在文档里出现越多,文档越相关。但边际递减——出现 100 次不比出现 10 次相关 10 倍。
- IDF(逆文档频率):一个词在越少的文档里出现,它越有区分度。"的"出现在所有文档里,等于没用;"所有权"只在少数文档里出现,很有价值。
- 文档长度归一化:长文档天然更容易命中词,要打个折扣。
BM25 的公式:
score(D, Q) = Σ IDF(qi) * (tf * (k1 + 1)) / (tf + k1 * (1 - b + b * |D| / avgdl))
其中:
IDF(qi) = ln(1 + (N - df + 0.5) / (df + 0.5))
tf = 词在文档中的出现次数
|D| = 文档长度
avgdl = 平均文档长度
k1 = 1.2 ~ 2.0(TF 饱和速度)
b = 0.75(长度归一化程度)代码:
const K1: f32 = 1.2;
const B: f32 = 0.75;
impl InvertedIndex {
pub fn bm25(&self, term: &str, posting: &Posting, avgdl: f32) -> f32 {
let Some(info) = self.dictionary.get(term) else {
return 0.0;
};
// IDF
let n = self.doc_count as f32;
let df = info.doc_freq as f32;
let idf = (1.0 + (n - df + 0.5) / (df + 0.5)).ln();
// TF 饱和
let tf = posting.term_freq as f32;
let dl = self.doc_lengths[posting.doc_id as usize] as f32;
let norm = 1.0 - B + B * (dl / avgdl);
idf * (tf * (K1 + 1.0)) / (tf + K1 * norm)
}
}两个参数的作用值得单独说:
k1控制"词频饱和速度"。k1越大,词频的影响越持久;越小,出现几次就饱和了。b控制"长度归一化的强度"。b = 0完全不做归一化(长文档占便宜),b = 1完全归一化。
b 是非常容易被忽略、但对排序质量影响巨大的参数。 短文档集合(比如商品标题)可以设 b = 0.3 左右,长文档(论文全文)用默认 0.75。
完整查询流程
pub fn search(&self, query: &str, top_k: usize) -> Vec<(u32, f32)> {
let terms = tokenize(query);
if terms.is_empty() {
return Vec::new();
}
let avgdl = self.doc_lengths.iter().sum::<u32>() as f32 / self.doc_count as f32;
// 1. 求候选集(多词交集)
let candidates = self.search_and(&terms);
// 2. 对每个候选打分
let mut scored: Vec<(u32, f32)> = candidates
.into_iter()
.map(|doc_id| {
let mut score = 0.0;
for term in &terms {
if let Some(posting) = self.get_posting(term, doc_id) {
score += self.bm25(term, posting, avgdl);
}
}
(doc_id, score)
})
.collect();
// 3. 按分数排序,取 top k
scored.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap());
scored.truncate(top_k);
scored
}注意这里用的是"交集"(AND 语义)。 真实搜索引擎用的是 OR + 打分:任何词命中都可能相关,只是分数不同。AND 更适合"精确查找"场景。
想改成 OR,只需把 intersect 换成 union,其他不变。打分环节本来就是按每个词独立算再加总的,天然支持 OR。
压缩:倒排表可以小很多
倒排表的空间瓶颈在 doc_id 列表。有两种经典的压缩:
1. 差值编码(delta encoding)。 存相邻 doc_id 的差,而不是绝对值:
// [1, 5, 100, 102] -> [1, 4, 95, 2]
fn delta_encode(ids: &[u32]) -> Vec<u32> {
let mut out = Vec::with_capacity(ids.len());
let mut prev = 0;
for &id in ids {
out.push(id - prev);
prev = id;
}
out
}2. 变长整数(varint)。 小数字只占 1 字节:
fn write_varint(mut n: u32, out: &mut Vec<u8>) {
while n >= 0x80 {
out.push((n as u8) | 0x80); // 最高位 1 表示"还有后续"
n >>= 7;
}
out.push(n as u8);
}两者结合,一个 doc_id 平均可以从 4 字节压到 1 字节以内。实际系统(Lucene)还会用位图、跳跃表进一步优化。
搜索引擎的空间优化集中在倒排表上,因为它是整个索引里最大的部分。 词典本身虽然有几十万词条,但每个词只有几十字节。
缓存与合并:工业系统的两个额外话题
到这里功能完整了。但生产级搜索引擎还差两块:
1. 跳跃表(skip list)加速交集。 两个列表求交时,如果每次都逐格前进,遇到稀疏匹配会很慢。在倒排表里每隔若干项插一个"跳跃点",可以快速跳过不可能匹配的区间。
2. 索引分段与合并(segment merge)。 增量索引不能每次都重建——主流做法是"新文档写进内存小段,满了就刷成不可变段,后台定期合并多个段"。
这和 LSM-Tree 的 compaction 是同一个思路:不可变段 + 后台合并。区别只是合并的是倒排表而不是 SSTable。
结论
倒排索引的骨架只有三样东西:
词典(词 → 倒排表位置);倒排表(有序 doc_id + 词频);位置表(用于短语和邻近度)。
围绕它们展开的所有工作都是工程优化:分词策略(中文的 bigram vs 词典)、高效求交(有序列表 + 短列表优先 + 跳跃表)、相关性排序(BM25 的 k1 和 b)、空间压缩(差值 + 变长整数)、增量更新(分段 + 合并)。
理解了这三个结构,再看 Elasticsearch 的那些配置项,你会知道每一个都在调什么。 下一篇我们去看另一个"前缀检索"的场景——自动补全,那里需要的是另一种结构:Trie。