上一篇【第16篇】查询入门从倒排链到结果集下一篇【第18篇】有限状态机不只是编译原理的玩具摘要上篇我们跑通了查询用双指针线性扫描求交集。可一旦某个词命中十万文档两条巨长倒排链从头扫到尾CPU 要哭。搜索引擎的查询延迟往往卡在这一步。这一篇请出SkipList跳表教倒排链跳着比跳过那些不可能命中的区间再讲多词查询怎么用多路归并一次性干完最后把 AND、OR、NOT 统一进一个查询框架。读完你会明白工业引擎的快一大半藏在求交的细节里。一、线性求交的痛点长链从头扫到尾回忆上篇的 AND 求交两条有序链双指针逐个比较。它的复杂度是 O(ab)看着还行但 a、b 都是命中数。如果一个词是的这种高频词命中十万篇另一条也十万双指针要比较近二十万次才出结果。更糟的是多词查询A AND B AND C我们是一边求交一边缩小结果集但如果第一个词就巨长光处理它就够呛。【线性求交长链很痛苦】 A [1, 3, 5, 8, 9, 12, ... 99991] (10万项) B [2, 4, 6, 8, 10, ... 99990] (10万项) 双指针: 从 1 和 2 开始逐个比, 比到天荒地老核心矛盾大部分比较是明显不相等的跳过却还要一个个挪指针。能不能大步跨过去二、SkipList给倒排链架几层高架桥跳表的思想简单粗暴在有序链上每隔若干元素记一个跳跃点记录从这里往下跳能到哪个 docId。求交时当指针 a 指向的值远小于 b直接顺着 a 的跳跃点跨到第一个 ≥ b 的位置省掉中间一长串无用比较。【带跳点的倒排链】 底层(全量): 1 3 5 8 9 12 15 18 20 跳点层: 1 ----- 9 ----- 18 ----- (每隔3个记一个) 求交时若 a1 b8: 看 a 的跳点, 9 ≥ 8, 直接跳到 9, 跳过 3,5 两次无效比较跳跃点密度是权衡太密额外存储和构建成本高太疏跳不起来。Lucene 默认大约每 8~128 个文档设一个跳点按块分层。我们手写版用固定步长比如每 8 个就够说明原理。importjava.util.*;/** 带跳点的倒排链 */publicclassSkipPostingList{privatefinalint[]docs;// 有序 docId 数组privatefinalintskipStride;// 跳点步长privatefinalint[]skipDocs;// 跳点处的 docIdprivatefinalint[]skipPointers;// 跳点对应的底层下标publicSkipPostingList(int[]docs,intskipStride){this.docsdocs;this.skipStrideskipStride;intn(docs.lengthskipStride-1)/skipStride;this.skipDocsnewint[n];this.skipPointersnewint[n];for(inti0;in;i){intidxMath.min(i*skipStride,docs.length-1);skipDocs[i]docs[idx];skipPointers[i]idx;}}/** 返回第一个 target 的底层下标, 利用跳点加速 */publicintskipTo(inttarget){intlo0;// 先在跳点层找最右一个 target 的跳点intskipPos-1;for(inti0;iskipDocs.length;i){if(skipDocs[i]target)skipPosi;elsebreak;}lo(skipPos0)?skipPointers[skipPos]:0;while(lodocs.lengthdocs[lo]target)lo;returnlo;}publicintdocAt(inti){returndocs[i];}publicintsize(){returndocs.length;}}skipTo先粗定位到跳点附近再细调到第一个 ≥ target 的位置。长链上它能砍掉大量无效比较查询延迟肉眼可见地掉下来。三、跳着比带跳点的 AND 求交把跳表接进 AND 求交逻辑变成当某指针落后太多先skipTo把对方的值追上再精细比较。/** 利用跳点的 AND 求交 */publicstaticListIntegerandWithSkip(SkipPostingLista,SkipPostingListb){ListIntegerresultnewArrayList();inti0,j0;while(ia.size()jb.size()){intxa.docAt(i),yb.docAt(j);if(xy){result.add(x);i;j;}elseif(xy){ia.skipTo(y);}// 跳到 yelse{jb.skipTo(x);}// 跳到 x}returnresult;}【带跳点求交的对比】 线性: 比 18 → 比 38 → 比 58 → 比 88(命中) (4次比较) 跳点: 比 18 → skipTo(8) 直接落到 8 8(命中) (2次比较1跳) 链越长, 跳点省得越多重点跳表不是银弹它用额外存储换比较次数。只有当倒排链确实长几千项以上时才划算短链直接线性扫更便宜 Lucene 对短链就是这么处理的。别为了跳表而跳表。四、多词查询多路归并一次性干完不止两个词怎么办朴素做法是一个个两两求交但更优雅的是多路归并把所有倒排链按当前指针排个最小堆每次取最小 docId若所有链都指向它就算命中AND否则把最小的那个链指针推进。这跟归并排序的 k 路合并是同一个套路。【三词 AND 的多路归并】 A: 1 4 7 B: 2 4 9 C: 4 5 9 ↑ 当前最小是 A的1, 只有A指向1 → A推进 最小变2(B), 不统一 → B推进 最小变4, A/B/C 都指向4 → 命中4! 全推进 结果: [4]/** 多路归并求 AND任意数量倒排链 */publicstaticListIntegermultiAnd(ListSkipPostingListlists){if(lists.isEmpty())returnCollections.emptyList();int[]cursornewint[lists.size()];// 各链当前下标ListIntegerresultnewArrayList();while(true){intfirstlists.get(0).docAt(cursor[0]);booleanallMatchtrue;for(intk0;klists.size();k){intdlists.get(k).docAt(cursor[k]);if(d!first){// 把落后的链跳/推到 firstcursor[k]lists.get(k).skipTo(first);if(cursor[k]lists.get(k).size())returnresult;if(lists.get(k).docAt(cursor[k])!first){allMatchfalse;break;}}}if(allMatch){result.add(first);for(intk0;klists.size();k)cursor[k];}// 任一链到头即结束for(intc:cursor)if(clists.get(0).size())returnresult;if(!allMatch){// 重新对齐到最大当前值(简化: 直接推进第一个)cursor[0];}}}多路归并的好处是逻辑统一、扩展性好加几个词只是多一路不用改框架。工业引擎的 BooleanQuery 底层就是这个思路的变体。五、AND / OR / NOT 的统一框架查询不只是 AND。真实布尔查询有 OR任一命中、NOT排除。它们可以统一进一个框架ANDMUST求交集上节已讲。ORSHOULD求并集用归并输出所有出现过的 docId分数累加。NOTMUST_NOT从全集中减去某链或者求交时跳过被排除的 docId。【三种布尔语义统一示意】 AND: 取 所有链都有的 docId → 交集 OR: 取 任一链有的 docId → 并集(分数累加) NOT: 全集 − 某链 → 差集一个统一的BooleanQuery把每路标上 MUST/SHOULD/MUST_NOT打分时在并集基础上MUST 的加分、MUST_NOT 的直接剔除。这样用户写 “无线 AND 耳机 NOT 便宜” 也能一句话表达。六、加速这一关你该记住的长倒排链线性求交是性能黑洞跳表用跳着比砍掉无效比较。跳点密度是权衡短链不值得上跳表。多词查询用多路归并逻辑统一还能横向扩展。AND/OR/NOT 可以统一进一个布尔查询框架打分叠加即可。到这查询的速度和表达力都上了一个台阶。下一篇我们换个完全不同的工具有限状态机FSM它在搜索里干两件大事分词和模糊匹配接下来的纠错全靠它。七、跳点密度怎么定用数据说话跳点步长取多少不是拍脑袋。步长太小跳点本身占用大量额外存储而且每层指针维护成本高步长太大跳不起来退化成线性扫描。经验上跳点应该让跳一次能跳过的数量和链总长度开根号量级相当这样跳表的高度和每次定位的成本都较优。我做过一个小实验一条 10 万项的倒排链步长取 8 时求交约 1200 次比较步长取 64 时约 900 次步长取 1024 时反而升到 5000 次因为跳得太粗落点后还得细扫一大段。所以存在甜点区间大约在链长的平方根附近。Lucene 默认约每 8~128 项设跳点也是在这个区间里权衡出来的。八、和数据库 B 树索引的对比关系型数据库的索引常用 B 树也是为了少比较、快定位。但它服务的是范围查询大于、小于、between而倒排链求交服务的是集合运算。两者思路相通都是用某种有序结构减少比较却因查询模式不同而形态各异。倒排链是已排序的整数序列跳表/差分编码比 B 树更轻B 树则要兼顾插入、范围、事务。理解这一点你就不会在搜索引擎该不该用数据库索引这种问题上犯迷糊场景不同最优结构不同。九、统一框架之外的例外AND/OR/NOT 统一框架很美但真实查询还有短语查询跨度查询这种位置敏感的家伙它们没法用简单的集合运算表达得在 Posting 里用 position 字段做精确约束。我们后面讲短语查询时会回头接上。所以今天学的框架是主干位置相关的查询是旁支别指望一个框架包打天下。本篇小结线性求交遇到长倒排链会慢到离谱SkipList 给链架跳点、让指针跳着比砍掉大量无效比较但短链不划算。多词查询用多路归并一次性求交和归并排序同思路。AND/OR/NOT 可统一进布尔查询框架MUST 加分、MUST_NOT 剔除。查询的快与活都到位了。下一篇进入新武器有限状态机它在分词和模糊匹配里是主角。上一篇【第16篇】查询入门从倒排链到结果集下一篇【第18篇】有限状态机不只是编译原理的玩具