3、广告检索模块设计：倒排索引原理、广告定向条件的索引构建、布尔表达式检索优化、我在项目中遇到的索引膨胀问题及解决方案
广告检索，说白了就是「从海量广告里，快速找到符合当前用户的那几条」。
我刚开始做广告系统时，觉得这不就是个倒排索引嘛，跟搜索引擎差不多。后来踩了坑才发现——广告检索的难点不在「查得快」，而在「条件多」。地域、人群、设备、时段……每个广告都挂着一堆定向条件，怎么把这些条件组织起来，让检索既快又准？
嗯，今天咱们就聊聊这个。
3.1 倒排索引原理：广告检索的基石
先说说倒排索引。传统索引是「文档→词」的映射，倒排索引反过来，是「词→文档列表」。
举个例子：
- 广告A：关键词「运动鞋」「男款」
- 广告B：关键词「运动鞋」「女款」
- 广告C：关键词「跑鞋」「男款」
倒排索引长这样：
运动鞋 → [A, B]
男款 → [A, C]
女款 → [B]
跑鞋 → [C]用户搜「运动鞋 男款」，取交集，得到[A]。就这么简单。
核心要点：倒排索引的本质是用空间换时间。把「查文档」变成「查词表」，检索复杂度从O(n)降到O(1)。
但广告检索跟搜索引擎有个关键区别——搜索引擎的查询词是用户输入的，而广告的「查询词」是系统根据用户画像、上下文自动生成的。比如用户在北京、用iPhone、晚上8点打开App，那查询条件就是「地域=北京 & 设备=iPhone & 时段=20:00」。
这就引出了下一个问题：定向条件怎么建索引？
3.2 广告定向条件的索引构建
广告定向条件五花八门，但归纳起来就四大类：地域、人群、设备、时段。每种条件的索引构建方式都不一样。
3.2.1 地域索引
地域是个典型的层级结构：国家→省→市→区。一个广告可能定向「北京」，也可能定向「朝阳区」。
我建议用位图索引（Bitmap Index）。每个地域ID对应一个bit位，广告覆盖的地域用bitmask表示。检索时，用户的地域ID直接查bitmask，O(1)搞定。
// 示例：地域bitmask
广告A：北京(0x01) | 上海(0x02) = 0x03
广告B：朝阳区(0x04) = 0x04
// 用户在北京，地域ID=0x01
// 检查广告A：0x03 & 0x01 != 0 → 命中
// 检查广告B：0x04 & 0x01 == 0 → 不命中小技巧：地域层级可以用前缀编码。比如北京朝阳区编码为「110105」，检索时用前缀匹配，效率很高。
3.2.2 人群索引
人群标签通常是多值属性，比如「性别=男」「年龄=25-35」「兴趣=运动」。每个标签都是一个倒排链。
我习惯用「标签ID→广告ID列表」的倒排结构。检索时，把用户的所有标签对应的广告ID列表取出来，做交集或并集。
标签：性别=男 → [A, B, C]
标签：年龄=25-35 → [A, C, D]
标签：兴趣=运动 → [A, D, E]
// 用户：男、25-35、运动
// 取交集：[A]注意：人群标签的倒排链可能很长。一个热门标签可能关联几十万条广告，取交集时性能会急剧下降。后面会讲怎么优化。
3.2.3 设备索引
设备属性相对固定：操作系统、机型、网络类型等。我建议用枚举值+位图的方式。
比如操作系统：iOS=1，Android=2，HarmonyOS=3。每个广告用一个int表示支持的设备类型，检索时直接比较。
广告A：支持iOS和Android → 设备mask = 0x03
用户设备：iOS → 设备ID = 1
if (广告A.mask & (1 << 用户设备ID)) != 0 → 命中3.2.4 时段索引
时段定向比较特殊，它是个时间范围。比如广告只在「9:00-12:00」和「14:00-18:00」投放。
我见过两种做法：
- 时间片轮询：把一天切成1440个分钟片，每个广告维护一个bitmap，共1440bit。检索时直接查对应分钟位的值。
- 区间树：用区间树存储广告的投放时段，检索时查用户当前时间落在哪些区间里。
我个人推荐时间片轮询。虽然内存占用大一点（每个广告180字节），但检索速度极快，适合高并发场景。
3.3 布尔表达式检索优化
广告定向条件本质上是个布尔表达式：
(地域=北京 AND 设备=iPhone) OR (地域=上海 AND 时段=20:00)检索时，需要判断这个表达式是否为真。最直接的做法是把表达式转成析取范式（DNF），然后逐项判断。但DNF有个问题——项数可能爆炸。
我记得有个项目，广告的定向条件有20多个标签，转成DNF后产生了上万个子句。检索一次要几秒钟，完全不可用。
优化思路：用「布尔表达式求值树」代替DNF。把表达式解析成树形结构，每个节点是一个操作符（AND/OR/NOT），叶子节点是条件判断。检索时深度遍历，遇到不满足的条件就剪枝。
举个例子：
表达式：(A AND B) OR (C AND D)
求值树：
OR
/ \
AND AND
/ \ / \
A B C D
检索过程：
1. 先判断左子树：A AND B
2. 如果A不满足，直接跳过左子树，不用判断B
3. 再判断右子树：C AND D
4. 同理，C不满足就跳过D这种做法的好处是「短路求值」，能省掉大量不必要的条件判断。我在项目中实测，检索耗时从2秒降到了50毫秒。
另一个优化：把高频条件前置。比如「地域」通常能过滤掉大部分广告，那就把它放在AND表达式的第一个位置。这样能尽早剪枝。
3.4 我在项目中遇到的索引膨胀问题及解决方案
好，终于说到这个让我头疼了很久的问题了。
那是在一个DSP（需求方平台）项目里，广告主可以设置非常精细的定向条件。比如「北京朝阳区、25-35岁、男性、iPhone用户、晚上8-10点、喜欢运动」。每个条件都要建索引。
一开始，索引文件只有几百MB，跑得挺欢。但随着广告量增长到千万级，索引文件膨胀到了几十GB。内存装不下，磁盘IO成了瓶颈，检索延迟从10ms飙升到500ms。
问题出在哪？
- 倒排链冗余：同一个广告出现在多个倒排链里，每个链都存一份广告ID。比如一个广告有10个标签，那它的ID就被存了10次。
- 位图稀疏：地域位图里，大部分bit是0，但每个广告都占了一个完整的bitmask。
- 元数据膨胀：每个倒排链的元数据（长度、偏移量等）本身也占空间。
我的解决方案：
- 压缩倒排链：用差值编码（Delta Encoding）代替直接存广告ID。比如广告ID是[1, 3, 7, 12]，存成[1, 2, 4, 5]（差值）。再用Varint编码压缩，平均每个ID只占1-2字节。
- 分层索引：把高频标签和低频标签分开。高频标签用位图索引，低频标签用倒排链。这样既保证了高频查询的速度，又节省了低频标签的内存。
- 索引分片：按广告ID范围把索引分成多个分片。检索时只查相关分片，减少IO量。
- 冷热分离：最近7天的广告放内存（热索引），历史广告放SSD（冷索引）。检索时先查热索引，没命中再查冷索引。
效果：索引大小从32GB降到了4.2GB，压缩比约7.6:1。检索P99延迟从500ms降到了30ms。
嗯，这里有个坑要提醒你——压缩和解压是有CPU开销的。我刚开始用Varint编码时，压缩率是上去了，但CPU飙升到了80%。后来改用SIMD加速的解码库，才把CPU压下来。
避坑指南：索引膨胀不是一蹴而就的。我建议在系统设计初期就预留好压缩和分片的能力，别等到线上出问题了再改。我曾经就因为没预留扩展点，重构索引花了两周时间，那两周天天被业务方催……
好了，广告检索模块的核心内容就这些。总结一下：倒排索引是基础，定向条件要因地制宜，布尔表达式用求值树优化，索引膨胀靠压缩和分层解决。下一章咱们聊聊广告排序——怎么从候选广告里挑出最赚钱的那条。