简介：这份资源围绕C++实现倒排索引与搜索功能展开，面向正在学习数据结构、搜索引擎原理或准备相关课程设计的学习者。包内共13个文件，以10个txt文档作为待索引语料，配合2个cpp源文件与1个头文件构成完整工程，压缩包约4KB，体量轻巧便于快速上手。项目完整覆盖从文件读取、分词解析到索引构建与查询的流程：使用fstream读取文本，借助unordered_map建立单词到文档编号列表的映射，并通过排序与双指针求交集，实现输入两个词后返回共同出现的文档。代码中涉及字符串处理、哈希表、向量容器与异常处理等知识点，适合作为理解倒排索引原理的实践范例。目前已有998人学习下载，读者可借此掌握索引构建思路、搜索算法实现及内存与效率优化的基本方法。
1. 倒排索引到底解决什么问题，为什么值得用 C++ 手写一遍
如果你手上有几十万篇文档，想做一个「输入关键词，毫秒级返回相关文档」的搜索功能，第一反应可能是上 Elasticsearch。但真到了嵌入式设备、离线工具、或者对延迟和内存有硬要求的场景，外部服务往往塞不进去。这时候用 C++ 从零构建一个倒排索引，反而是最直接的路子。
倒排索引的核心思路很朴素：正排是「文档 → 包含哪些词」，倒排把它翻过来，变成「词 → 出现在哪些文档里」。查询时不再逐篇扫描，而是直接查词典拿到文档列表，再做交集合并。这个结构决定了它的查询复杂度跟文档总量关系不大，主要取决于命中词对应的文档数量。
这篇文章面向两类人：一是想理解搜索引擎底层结构、准备自己动手写一个的开发者；二是已经会用现成库，但遇到性能瓶颈想搞清楚内部机制的工程师。我会从数据结构选型讲到可编译运行的完整代码，再到参数调优和踩坑记录，每一步都给出能直接抄的代码块。
2. 倒排索引的数据结构选型：词典、倒排表和文档属性怎么定
2.1 词典用什么容器：哈希表还是有序数组
词典（term dictionary）负责把词映射到倒排表。最常见的两种选择是std::unordered_map和std::map。前者查询平均 O(1)，后者 O(log n) 但天然有序。
如果你的查询只需要精确匹配单个词，unordered_map是首选。但如果要支持前缀查询（比如输入「数据」能匹配「数据库」「数据结构」），有序结构配合二分查找会更方便。我一般会先用unordered_map把功能跑通，确认没有前缀需求后再定下来。
#include <unordered_map> #include <string> #include <vector> // 倒排表：每个词对应一组文档ID using PostingList = std::vector<int>; // 词典：词 -> 倒排表 std::unordered_map<std::string, PostingList> invertedIndex;这里PostingList用std::vector<int>存文档 ID。选vector而不是list的原因是：查询时要做交集合并，vector内存连续、缓存友好，而且可以排序后归并。文档 ID 用int而非size_t，是因为实际文档量很少超过 21 亿，用int能省一半内存。
2.2 倒排表里存什么：只存文档 ID 够不够
只存文档 ID 能完成基本检索，但要做相关性排序就不够了。实际工程里通常还会存词频（term frequency）和位置信息（position）。
词频用于 TF-IDF 或 BM25 打分，位置信息用于短语查询。存储方式有两种：并行数组（文档 ID 一个数组，词频一个数组）和结构体数组。并行数组对缓存更友好，结构体可读性更好。
struct Posting { int docId; // 文档编号 int termFreq; // 该词在文档中出现次数 }; // 带词频的倒排表 std::unordered_map<std::string, std::vector<Posting>> indexWithFreq;如果暂时不需要排序，先用纯vector<int>把检索跑通，等确实需要打分时再升级结构。过早引入词频和位置，会让内存翻好几倍，调试也麻烦。
2.3 文档属性单独存：正排记录的必要性
倒排索引只告诉你「哪些文档命中了」，但用户要看的是文档标题、摘要、URL。这些属性必须单独用一张正排表存，键是文档 ID。
struct DocumentMeta { std::string title; std::string url; int length; // 文档总词数，用于归一化打分 }; std::vector<DocumentMeta> docStore; // 下标即文档ID用vector而不是map，因为文档 ID 是连续分配的整数，直接下标访问最快。每加入一篇新文档，就往docStore尾部 push 一条记录，同时把返回的索引作为该文档的 ID。
3. 从零构建索引：分词、建表、持久化的完整代码路径
3.1 分词器的最小实现：按非字母数字切分
英文场景下，最简单的分词就是按空格和标点切分，再统一转小写。中文需要额外接入分词库，这里先用英文规则把流程跑通。
#include <cctype> #include <sstream> // 将输入文本切分为小写词项 std::vector<std::string> tokenize(const std::string& text) { std::vector<std::string> tokens; std::string current; for (char ch : text) { if (std::isalnum(static_cast<unsigned char>(ch))) { current += std::tolower(static_cast<unsigned char>(ch)); } else { if (!current.empty()) { tokens.push_back(current); current.clear(); } } } if (!current.empty()) tokens.push_back(current); return tokens; }std::isalnum的参数必须先转unsigned char，否则遇到负值字符是未定义行为，这是很多人翻车的地方。分词结果统一转小写，保证「Data」和「data」能命中同一个倒排表。
3.2 建索引主流程：遍历文档、更新倒排表
建索引的过程就是：对每篇文档分词，统计每个词的出现次数，然后把文档 ID 追加到对应词的倒排表里。
// 向索引中添加一篇文档，返回分配的文档ID int addDocument(const std::string& title, const std::string& body) { int docId = static_cast<int>(docStore.size()); docStore.push_back({title, "", static_cast<int>(tokenize(body).size())}); auto tokens = tokenize(body); std::unordered_map<std::string, int> freq; for (auto& t : tokens) freq[t]++; for (auto& [term, count] : freq) { indexWithFreq[term].push_back({docId, count}); } return docId; }先用局部freq统计词频，再一次性写入倒排表，避免同一个词在同一篇文档里被重复追加。docStore的size()在建表前取，保证文档 ID 从 0 开始连续分配。
3.3 索引落盘与加载：二进制格式最省事
内存索引重启就没了，必须持久化。文本格式可读但体积大、解析慢，二进制格式是更实际的选择。写入时先写词项数量，再逐个写词项长度、词项内容、倒排表大小和每条记录。
#include <fstream> void saveIndex(const std::string& path) { std::ofstream out(path, std::ios::binary); size_t termCount = indexWithFreq.size(); out.write(reinterpret_cast<const char*>(&termCount), sizeof(termCount)); for (auto& [term, postings] : indexWithFreq) { size_t len = term.size(); out.write(reinterpret_cast<const char*>(&len), sizeof(len)); out.write(term.data(), len); size_t psize = postings.size(); out.write(reinterpret_cast<const char*>(&psize), sizeof(psize)); out.write(reinterpret_cast<const char*>(postings.data()), psize * sizeof(Posting)); } }写入顺序必须和读取顺序严格一致，否则解析全乱。Posting是 POD 类型，可以直接按字节块写入。如果结构体里有std::string成员，就不能这么干，必须逐字段序列化。
4. 查询与排序：多词交集、TF-IDF 打分和 Top-K 截断
4.1 单词查询与多词交集：归并两个有序数组
单词查询直接查词典返回倒排表。多词查询（AND 语义）需要对多个倒排表求交集。因为倒排表里的文档 ID 是递增的，可以用双指针归并。
// 求两个有序倒排表的交集 PostingList intersect(const PostingList& a, const PostingList& b) { PostingList result; size_t i = 0, j = 0; while (i < a.size() && j < b.size()) { if (a[i].docId == b[j].docId) { result.push_back(a[i]); i++; j++; } else if (a[i].docId < b[j].docId) { i++; } else { j++; } } return result; }双指针归并的复杂度是 O(m+n)，比用哈希集合求交集快得多，因为不需要额外内存分配。多个词时，从倒排表最短的那个词开始依次求交，能最快缩小候选集。
4.2 TF-IDF 打分：让相关文档排前面
交集只给出「命中了哪些文档」，顺序还是文档 ID 顺序。要按相关性排序，需要打分。TF-IDF 是最经典的方案：词频越高、该词越罕见，得分越高。
#include <cmath> // 计算某文档对某词的TF-IDF得分 double tfIdf(int termFreq, int docLength, int totalDocs, int docFreq) { double tf = static_cast<double>(termFreq) / docLength; double idf = std::log(static_cast<double>(totalDocs) / (docFreq + 1)); return tf * idf; }docFreq是该词出现在多少篇文档里，也就是倒排表的长度。+1是平滑项，防止某个词在所有文档都出现时 IDF 变成 0。docLength做归一化，避免长文档因为词多而占便宜。
4.3 Top-K 截断：别把命中文档全返回
查询「data」可能命中几万篇文档，全排序再返回前 10 条是浪费。用一个大小为 K 的最小堆，遍历过程中只保留得分最高的 K 条。
#include <queue> // 返回得分最高的K篇文档 std::vector<std::pair<int, double>> topK( const std::vector<std::pair<int, double>>& scored, int k) { // 小顶堆，堆顶是当前K个里得分最低的 auto cmp = [](auto& a, auto& b) { return a.second > b.second; }; std::priority_queue<std::pair<int, double>, std::vector<std::pair<int, double>>, decltype(cmp)> heap(cmp); for (auto& item : scored) { if (heap.size() < static_cast<size_t>(k)) { heap.push(item); } else if (item.second > heap.top().second) { heap.pop(); heap.push(item); } } std::vector<std::pair<int, double>> result; while (!heap.empty()) { result.push_back(heap.top()); heap.pop(); } return result; }堆的比较器用>构造小顶堆，堆顶始终是当前保留的 K 条里最差的。新元素比堆顶好就替换。最终结果是从小到大，返回前反转一下即可。K 一般取 10 到 100，取决于前端一页展示多少条。
5. 避坑与排查：倒排索引实现里最容易翻车的五个地方
5.1 分词后没去重，倒排表里同一文档出现多次
现象：查询结果里同一篇文档出现好几遍，或者打分异常偏高。
原因：建索引时对每个 token 直接 push 文档 ID，没有先按文档聚合词频。同一篇文档里「data」出现 5 次，倒排表里就有 5 条相同 docId 的记录。
解决：先用局部哈希表统计词频，再一次性写入。如果已经写坏了，查询时对倒排表按 docId 去重，但更彻底的做法是重建索引。
5.2 文档 ID 用 size_t 导致二进制文件跨平台不兼容
现象：在 64 位机器上存的索引，拿到 32 位环境加载后数据错乱。
原因：size_t的宽度随平台变化，直接按字节块读写会导致字段宽度不一致。
解决：持久化时统一用固定宽度类型，比如uint32_t存文档 ID 和词频，uint64_t存数量字段。跨平台场景下不要用size_t做序列化。
5.3 倒排表未排序就做交集，结果漏文档
现象：多词查询返回的结果比预期少，但单词查询正常。
原因：文档不是按 ID 递增顺序加入的，或者中途删过文档，导致倒排表里 docId 乱序。双指针归并要求两边都有序，乱序时比较逻辑失效。
解决：建索引时保证 docId 单调递增；如果有删除操作，用标记删除而不是物理删除，查询时跳过标记位。或者在求交集前对每个倒排表做一次排序。
5.4 IDF 计算用了实时文档总数，导致打分不稳定
现象：同样的查询，加了几篇文档后排序结果大变。
原因：totalDocs每次查询都取当前文档总数，索引一变 IDF 就变。如果docFreq没同步更新，打分就失真。
解决：把totalDocs和每个词的docFreq在索引构建完成后固化下来，查询时直接读快照。增量更新时同步维护这两个值。
5.5 内存索引全量加载导致启动慢
现象：索引文件几百 MB，程序启动要等十几秒。
原因：加载时逐个词项解析并插入unordered_map，每个词项都触发一次内存分配。
解决：加载前用reserve预留哈希桶数量，减少 rehash。更大的索引可以改造成内存映射文件，查询时按需读取，但实现复杂度会上升一个量级。
6. 进阶技巧：用内存映射和跳表把查询再压一档
索引大到几百 MB 后，全量加载进内存越来越不划算。一个实用的进阶做法是把倒排表按词项分块存盘，查询时用内存映射按需读取。下面是一个最小示例，展示如何用mmap把索引文件映射进地址空间。
#include <sys/mman.h> #include <fcntl.h> #include <unistd.h> // 将索引文件映射到内存，返回起始指针 const char* mapIndex(const std::string& path, size_t& fileSize) { int fd = open(path.c_str(), O_RDONLY); if (fd < 0) return nullptr; fileSize = lseek(fd, 0, SEEK_END); const char* data = static_cast<const char*>( mmap(nullptr, fileSize, PROT_READ, MAP_PRIVATE, fd, 0)); close(fd); return data; }映射后不需要把整个文件读进堆内存，操作系统按页调度。查询某个词时，先读词典区拿到偏移量，再跳到对应位置解析倒排表。词典区可以常驻内存，倒排区按需换入。
另一个值得做的优化是给倒排表加跳表指针。在倒排表里每隔 128 个文档插一个跳转点，求交集时先按跳转点跳跃，再在小区间内线性比较。文档量上万后，这个优化能把交集耗时降一半左右。
参数上，跳表间隔取 64 到 256 之间比较合适。太小则跳转点本身占内存，太大则跳跃收益不明显。我一般先用 128 跑基准测试，再根据实际倒排表长度微调。
验证优化效果的方法很直接：构造 10 万篇模拟文档，分别测优化前后的查询 P99 延迟和常驻内存。如果延迟降了但内存涨了 30% 以上，就要重新权衡。我自己的习惯是每次只改一个变量，测完记录数据再动下一个，不然出了问题根本不知道是哪个改动引起的。
希望帮到你。
本文还有配套的精品资源，点击获取
