📚 课程目录第3章倒排索引与检索原理

3. 倒排索引与检索原理：倒排表构建、跳表合并、短语查询、实时更新机制

  核心提示：倒排索引是搜索引擎的基石，面试高频覆盖构建、合并、短语匹配与更新。重点考察对跳表合并效率、位置偏移处理、实时索引增量/全量切换的理解。

考察点	对跳表结构理解、空间换时间策略、Merge 时间复杂度分析
回答框架	1. 每 k 个 docId 抽取一个哨兵节点形成上层链表 2. 合并时从上层快速跳跃，跳过大量不需要比较的 docId 3. 平衡层数与额外存储开销（通常 k=8~16）
示例回答	倒排链按 docId 排序，每隔 8 个文档抽取一个节点构建跳表上层。合并两个倒排链时，先在高层跳跃比较，找到重叠区间再下钻。平均比较次数从 O(n) 降到 O(log n)，同时每层只增加约 12.5% 存储。
可能追问	跳表与 B+Tree 在倒排合并中选型差异？跳表写放大如何处理？
避坑提醒	勿把跳表当作平衡树；强调工程中常用固定步长而非随机层数，便于批量构建。

考察点	位置索引设计、多次与操作后的位置过滤、性能优化意识
回答框架	1. 每个 term 存储 (docId, positions) 列表 2. 先通过跳表合并命中所有 term 的 docId 3. 对每个 doc 交叉比对 position 是否连续
示例回答	短语“搜索引擎原理”需同时匹配两个 term，先找出同时包含的文档，再遍历 position 数组检查位置差=1。如果 term 频次高，可预先计算位置哈希或使用位图加速。
可能追问	如果短语长度超过 10 个词如何优化？如何处理 stop word 在短语中？
避坑提醒	不能只做 doc 级交集而忽略位置；短语查询必须考虑分词器是否保留停用词。

考察点	增量/全量策略、LSM 思想在倒排中的应用、内存 Flush
回答框架	1. 内存维护增量倒排表（RTSegment） 2. 定时冻结为不可变段并合并到磁盘 3. 查询时合并内存段与磁盘段，删除标记采用墓碑
示例回答	新文档先写入内存跳表，每秒冻结一个 Seg。查询时对内存 Seg 和磁盘 Seg 做多路合并。删除时写入墓碑，合并时清理。每个 Seg 上限 64MB，避免合并延迟。
可能追问	如何保证实时性在 1 秒内？合并过程中查询延迟如何优化？
避坑提醒	切勿设计全局锁；实时更新要区分“可见性”与“持久化”，读多写少场景优先保证查询低延迟。

项目名称	电商搜索引擎倒排索引重构（LSM+跳表）
业务背景	商品数 2亿，日均搜索 3000 万次，原有 B+Tree 倒排引擎写入吞吐低、短语查询慢
规模指标	索引大小 1.2TB，单文档平均 term 数 23，查询 QPS 5000+，P99 延迟 < 30ms
技术栈	C++/Java, RAFT+TokuMX, 自定义跳表合并器, 内存双 Buffer 段
核心难点	1. 跳表层数自适应（根据 doc 频次动态调整步长） 2. 短语查询时 position 链的并行过滤 3. 实时更新磁盘 IO 与查询延迟的 tradeoff
面试高频追问	跳表合并时如何处理重复 doc？增量段过多导致查询退化如何解决？
可迁移回答话术	“我们在内存中维护多层跳表，用固定大小冻结段控制合并粒度；查询时多路归并+布隆过滤器快速跳过不存在的 term 段，最终 P99 低于 30ms。该方案也适用于日志检索、实时推荐等场景。”

💡 复习建议：重点掌握跳表 vs 普通链表的合并复杂度差异；短语查询需手写伪代码说明位置遍历逻辑；实时更新要讲清楚可见性与持久化分离。

⚠️ 常见扣分点：混淆“跳表”与“B+Tree”的节点存储结构；忽略短语查询中 position 的排序特性；实时更新只提概念不讲段合并机制。