从零实现倒排索引召回：一个轻量级推荐系统的核心引擎

背景介绍

在推荐系统中，召回环节承担着从海量商品池中快速筛选候选集的重任。面对千万甚至亿级的商品库，如何做到毫秒级响应，同时保证召回质量？倒排索引（Inverted Index）是最经典、最高效的解决方案之一。

虽然工业界有 Elasticsearch、Faiss 等成熟的召回组件，但理解倒排索引的底层原理，并亲手实现一个精简版，对于掌握召回核心思想、定制特殊召回逻辑（如多样性控制）非常有价值。本文将分享我手写的一个 C++ 倒排索引召回模块，并讨论其优化思路。

核心设计思想

倒排索引的本质是“标签 → 商品列表”的映射。在推荐场景中：

• 正向索引：商品 → 它拥有的标签（兴趣点、关键词、品类等）

• 倒排索引：标签 → 包含该标签的商品列表（按相关性得分排序）

用户画像通常是一组带权重的标签(gsid, score)，召回任务就是：根据用户的多兴趣标签，快速从倒排索引中拉取候选商品，融合多路得分后输出 Top K。

数据结构设计

数据结构设计

class invertedIndex { // 倒排链中的节点 class ItemNode { int itemId; // 商品ID double score; // 商品与该标签的相关性得分 }; // 用户兴趣节点（外部输入） class GsidNode { int gsid; // 兴趣标签ID double score; // 用户对该兴趣的权重 }; private: // 核心索引：gsid → 按得分降序排列的 ItemNode 列表 map<int, vector<ItemNode>> index; };

选择map而非unordered_map是为了支持范围查询和有序遍历，在合并多个倒排链时更可控。倒排链内部使用vector并始终保持按得分降序，这样取出 Top K 时无需再排序。

核心功能实现

1. 建立索引

void insert(int itemId, vector<GsidNode> gsids) { for (GsidNode g : gsids) { ItemNode item(itemId, g.score); vector<ItemNode>& itemList = index[g.gsid]; // 二分查找插入位置，维持降序 auto pos = lower_bound(itemList.begin(), itemList.end(), item, greater<ItemNode>()); itemList.insert(pos, item); } }

要点：每个商品入库时，将其挂载到对应的标签倒排链尾部，并通过二分插入维持排序。时间复杂度 O(L * log N)，L 为商品关联的标签数。

2. 单兴趣召回

vector<int> topK(int gsid, int k) { if (index.find(gsid) == index.end()) return {}; int n = min(k, (int)index[gsid].size()); vector<int> res; for (int i = 0; i < n; i++) { res.push_back(index[gsid][i].itemId); } return res; }

单兴趣召回直接截取倒排链前 K 个商品，适用于兴趣明确、不需要融合的场景。

3. 多兴趣融合召回

vector<ItemNode> topK(vector<GsidNode> gsidList, int k) { vector<ItemNode> candidate; for (GsidNode g : gsidList) { for (ItemNode item : index[g.gsid]) { // 得分相乘：用户兴趣权重 × 商品与标签的相关性 candidate.push_back({item.itemId, item.score * g.score}); } } sort(candidate.begin(), candidate.end(), greater<ItemNode>()); // 取前 k 个，可能存在同一商品被不同标签重复召回，去重逻辑未展示 return {candidate.begin(), candidate.begin() + min(k, (int)candidate.size())}; }

注意：该实现存在性能隐患——会将多个倒排链全量拉取后再全局排序。当倒排链很长（如热门标签对应数万商品）时，候选集膨胀严重。优化思路见后文。

进阶难题与优化方案

问题1：单个兴趣下商品过多，查询效率低

现象：热门标签（如“女装”）下的商品可达数十万，即使只取 Top 100，仍需遍历全部节点？

解决方案：

• 分桶存储：按itemId % N将大倒排链拆分成多个子表，查询时并发从各子表取 Top K，再归并。

• 跳表 / 跳跃指针：在倒排链中建立索引块，支持跳跃式定位。

• 提前截断：插入时限制每条倒排链的最大长度（例如只保留得分最高的前 2000 个商品），牺牲极长尾召回换效率。

问题2：多兴趣融合时，热门兴趣淹没长尾兴趣

现象：用户 80% 权重在“游戏”，20% 在“古典音乐”，结果候选集几乎被游戏商品占满。

解决：在topK中引入兴趣配额制，每个兴趣最多取j个商品（即多样性控制函数topKDiversity）。

问题3：多样性要求：同兴趣商品不能相邻，且每个兴趣最多 j 个

这是我预留的topKDiversity接口要解决的核心问题，典型场景是信息流推荐防止内容同质化。

实现思路（伪代码层）：

vector<ItemNode> topKDiversity(vector<GsidNode> gsidList, int k, int j) { // 1. 为每个兴趣独立取 Top j 个商品 vector<vector<ItemNode>> perInterestTop; for (auto& g : gsidList) { perInterestTop.push_back(getTopJ(g.gsid, j)); } // 2. 按轮盘方式贪心选择：每次从剩余兴趣中选得分最高的商品， // 但不能与上一个商品同兴趣，直至凑满 k 个 vector<ItemNode> result; int lastGsid = -1; while (result.size() < k) { ItemNode best; int bestInterest = -1; for (int i = 0; i < perInterestTop.size(); i++) { if (perInterestTop[i].empty()) continue; if (gsidList[i].gsid == lastGsid) continue; // 同兴趣跳过 if (perInterestTop[i][0].score > best.score) { best = perInterestTop[i][0]; bestInterest = gsidList[i].gsid; } } if (bestInterest == -1) break; // 无候选 result.push_back(best); lastGsid = bestInterest; // 从对应兴趣列表中弹出已选商品 perInterestTop[getIndexByGsid(bestInterest)].erase(perInterestTop[getIndexByGsid(bestInterest)].begin()); } return result; }

该算法保证：

• 每个兴趣最多贡献 j 个商品

• 相邻商品不来自同一兴趣

• 全局尽可能按得分从高到低排列（贪心）

性能思考与工程落地

工程建议：

• 使用vector+ 手写二分维护有序性，cache 友好

• 对于实时性要求高的场景，索引全量加载到内存，定期 reload

• 线上可结合 Redis + 本地缓存，倒排链压缩存储（Varint + 差分编码）

与 Elasticsearch / Faiss 对比

如果你的系统规模在百万商品以内，且需要精细控制召回策略（多样性、兴趣配额、去重逻辑），手写倒排索引是完全可行的。

结语

倒排索引是推荐系统召回环节最朴实、最可靠的武器之一。亲手实现一遍，你不仅能深入理解其原理，还能根据业务需求自由扩展（比如支持时间衰减、实时权重更新）。本实现虽简单，但已经包含了工业倒排索引的核心骨架。后续我会继续完善topKDiversity的高效实现，并尝试加入BM25 相关性计算和增量索引更新机制，敬请期待。