企业官网建设流程全解析

上一篇【第16篇】查询入门：从倒排链到结果集
下一篇【第18篇】有限状态机：不只是编译原理的玩具

摘要

上篇我们跑通了查询，用双指针线性扫描求交集。可一旦某个词命中十万文档，两条巨长倒排链从头扫到尾，CPU 要哭。搜索引擎的查询延迟往往卡在这一步。这一篇请出SkipList跳表，教倒排链"跳着比"，跳过那些不可能命中的区间；再讲多词查询怎么用多路归并一次性干完；最后把 AND、OR、NOT 统一进一个查询框架。读完你会明白，工业引擎的快，一大半藏在求交的细节里。

一、线性求交的痛点：长链从头扫到尾

回忆上篇的 AND 求交：两条有序链，双指针逐个比较。它的复杂度是 O(a+b)，看着还行，但 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个记一个) 求交时若 a=1 < b=8: 看 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.docs=docs;this.skipStride=skipStride;intn=(docs.length+skipStride-1)/skipStride;this.skipDocs=newint[n];this.skipPointers=newint[n];for(inti=0;i<n;i++){intidx=Math.min(i*skipStride,docs.length-1);skipDocs[i]=docs[idx];skipPointers[i]=idx;}}/** 返回第一个 >= target 的底层下标, 利用跳点加速 */publicintskipTo(inttarget){intlo=0;// 先在跳点层找最右一个 < target 的跳点intskipPos=-1;for(inti=0;i<skipDocs.length;i++){if(skipDocs[i]<target)skipPos=i;elsebreak;}lo=(skipPos>=0)?skipPointers[skipPos]:0;while(lo<docs.length&&docs[lo]<target)lo++;returnlo;}publicintdocAt(inti){returndocs[i];}publicintsize(){returndocs.length;}}

skipTo先粗定位到跳点附近，再细调到第一个 ≥ target 的位置。长链上它能砍掉大量无效比较，查询延迟肉眼可见地掉下来。

三、跳着比：带跳点的 AND 求交

把跳表接进 AND 求交，逻辑变成：当某指针落后太多，先skipTo把对方的值追上，再精细比较。

/** 利用跳点的 AND 求交 */publicstaticList<Integer>andWithSkip(SkipPostingLista,SkipPostingListb){List<Integer>result=newArrayList<>();inti=0,j=0;while(i<a.size()&&j<b.size()){intx=a.docAt(i),y=b.docAt(j);if(x==y){result.add(x);i++;j++;}elseif(x<y){i=a.skipTo(y);}// 跳到 >= yelse{j=b.skipTo(x);}// 跳到 >= x}returnresult;}

【带跳点求交的对比】 线性: 比 1<8 → 比 3<8 → 比 5<8 → 比 8==8(命中) (4次比较) 跳点: 比 1<8 → 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（任意数量倒排链） */publicstaticList<Integer>multiAnd(List<SkipPostingList>lists){if(lists.isEmpty())returnCollections.emptyList();int[]cursor=newint[lists.size()];// 各链当前下标List<Integer>result=newArrayList<>();while(true){intfirst=lists.get(0).docAt(cursor[0]);booleanallMatch=true;for(intk=0;k<lists.size();k++){intd=lists.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){allMatch=false;break;}}}if(allMatch){result.add(first);for(intk=0;k<lists.size();k++)cursor[k]++;}// 任一链到头即结束for(intc:cursor)if(c>=lists.get(0).size())returnresult;if(!allMatch){// 重新对齐到最大当前值(简化: 直接推进第一个)cursor[0]++;}}}

多路归并的好处是逻辑统一、扩展性好，加几个词只是多一路，不用改框架。工业引擎的 BooleanQuery 底层就是这个思路的变体。

五、AND / OR / NOT 的统一框架

查询不只是 AND。真实布尔查询有 OR（任一命中）、NOT（排除）。它们可以统一进一个框架：

• AND（MUST）：求交集，上节已讲。
• OR（SHOULD）：求并集，用归并输出所有出现过的 docId，分数累加。
• NOT（MUST_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篇】有限状态机：不只是编译原理的玩具