背景介绍

在推荐系统中，召回 环节承担着从海量商品池中快速筛选候选集的重任。面对千万甚至亿级的商品库，如何做到毫秒级响应，同时保证召回质量？倒排索引（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 个商品

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

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

性能思考与工程落地

模块	时间复杂度	优化方向
插入	O(L·log N)	批量插入 + 定期重建索引
单兴趣召回	O(k)	已是最好
多兴趣融合（朴素）	O(∑链长 + M log M)	堆合并替代全排序
多样性召回	O(k·兴趣数)	用优先队列优化每轮选最大

工程建议：

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

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

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

与 Elasticsearch / Faiss 对比

特性	手写倒排索引	ES	Faiss
适用场景	轻量、定制化召回	全文检索 + 简单向量	稠密向量近似最近邻
多样性控制	灵活可控	较复杂	不支持
性能	百万级商品可支撑	千万级	亿级向量
开发成本	较高	低	中

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

结语

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