上一篇【第04篇】网络爬虫：给搜索引擎当采风人
下一篇【第06篇】分布式计算与搜索用户界面：不止是检索
摘要
如果说搜索引擎有心脏，那一定是全文索引。没有它，搜索就是慢吞吞的全文扫描；有了它，毫秒级返回才成为可能。本文从"为什么全表 LIKE 注定失败"讲起，把倒排索引这个核心结构掰开：它到底记了什么、词典和倒排链怎么分工、正排索引为何是好搭档，以及倒排不是银弹，它也有自己的代价。
一、为什么"全表 LIKE"注定失败
设想一个最朴素的办法：用户搜"耳机"，你就对数据库里每一行执行WHERE content LIKE '%耳机%'。在几千条数据时，这能凑合。一旦数据上千万、上亿，灾难就来了。
LIKE 前缀带通配符，数据库基本用不上索引，只能逐行扫描、逐字符匹配。数据量线性增长，查询时间也线性增长，CPU 被吃得死死的。更糟的是，多词查询、排序、高亮这些需求，纯 SQL 拼起来既慢又丑。
【两种查询方式的时间代价】 全表扫描: 查一次 ≈ 扫 N 篇文档 N 越大越慢，线性增长 倒排索引: 查一次 ≈ 取"词"对应的少量文档 和 N 无关，只和命中数有关倒排索引的思路，就是把"按文档找词"反过来，变成"按词找文档"。这个词典式的思维，是人类用了几百年的老办法，搜索引擎只是把它做到了极致。
二、倒排索引：把目录思维用到底
还记得书末尾的关键词索引吗？查"倒排"，它告诉你：第 12、45、78 页。搜索引擎的倒排索引是一模一样的逻辑，只不过规模从几百页变成几十亿文档。
具体到存储，倒排索引由两部分组成：词典（所有出现过的词）和倒排表（每个词对应的文档列表）。查询"耳机"时，去词典里找到"耳机"这个词，顺手拿出它的倒排表，里面就是所有包含"耳机"的文档编号。一步到位，不用扫全库。
【倒排索引的模样】 词典(Dictionary) 倒排表(Postings) ┌──────────┐ ┌──────────────────────────┐ │ 无线 │ ──────────────▶ │ [d1, d3, d7, d9, ...] │ │ 耳机 │ ──────────────▶ │ [d1, d2, d7, d10, ...] │ │ 便宜 │ ──────────────▶ │ [d2, d5] │ └──────────┘ └──────────────────────────┘ 词 ──指向──▶ 包含该词的文档ID列表这里有个关键认知：词典和倒排表是分开存的。词典常驻内存（或者高度压缩后放内存），倒排表可能很大，放磁盘，按需读取。这也是为什么倒排查询快：先内存里查词，再按指针读少量磁盘数据。
三、倒排里到底记了什么
很多人以为倒排表里只存文档编号。那是简化版。真实的倒排项，通常会记三类信息：
文档 ID，说明这条结果来自哪个文档，这是最基本的。
词频（TF），这个词在该文档里出现了几次。出现次数多，通常更相关，打分要用。
位置（Position），这个词在文档里的第几个位置。位置信息支撑短语查询，比如你要搜"无线耳机"作为一个连续短语，而不是"无线"和"耳机"各出现一次就行，就得靠位置来判断它们挨没挨着。
【一个倒排项长这样】 词 "耳机" 的倒排: ┌────────┬──────┬─────────────────────────┐ │ 文档ID │ 词频 │ 位置序列 │ ├────────┼──────┼─────────────────────────┤ │ d1 │ 3 │ [5, 23, 88] │ │ d7 │ 1 │ [12] │ └────────┴──────┴─────────────────────────┘位置序列看着不起眼，却是后面"短语查询""邻近查询"的命根子。我们手写检索引擎时，也会把位置记下来，到时候你就知道它有多值钱。
四、词典与倒排链：两兄弟的分工
词典和倒排链这对兄弟，职责划分很清楚。
词典负责"快速定位词"。它本质是个字典结构，给你一个词，要能在极短时间内返回它在倒排表里的位置。词典怎么存，后面我们会专门讲（提示：Lucene 用的是 FST，一种又省内存又快的有限状态结构）。
倒排链负责"列出所有文档"。它可能很长，比如"的"这个字，几乎每篇文档都有，倒排链能拉到几亿项。正因为有的词倒排链极长，查询时的合并才需要技巧，这部分我们写查询篇会细聊。
【查询时两兄弟的配合】 查询 "无线 耳机" │ ▼ 词典: 定位 "无线" → 倒排1 定位 "耳机" → 倒排2 │ ▼ 取两条倒排链，按文档ID求交集 → [d1, d7]五、正排索引：倒排的好搭档
只有倒排还不够。倒排告诉你"哪些文档命中了"，但用户要的是完整结果：标题、摘要、URL、价格。这些"文档长什么样"的信息，存在正排索引里，也就是按文档 ID 直接取出整条记录。
所以一个成熟的索引，通常是倒排 + 正排双线并存。倒排负责"找"，正排负责"取详情"。
【倒排 + 正排 配合】 倒排: 词 → 文档ID列表 （用于检索） 正排: 文档ID → 标题/正文/URL （用于展示）后来 Lucene 还搞出个 DocValues，专门给排序和聚合用，本质是"按列存"的正排。这块放到 Lucene 原理篇再展开，这里你只要记住：检索靠倒排，取详情靠正排，两者缺一不可。
六、倒排不是银弹：它的代价
倒排这么好，为什么不全用倒排？因为它有代价。
建索引慢且重。每来一篇新文档，都要分词、更新词典、追加倒排链。文档量巨大时，建索引本身就是个大工程，这也是为什么前面要异步、要分布式。
占用空间大。倒排表、词频、位置，这些都要存。好在有各种压缩算法（后面会专门讲变长编码、PForDelta），能把整数序列压得很小，但终究要多花存储。
更新不灵活。倒排结构天生适合"批量建、批量读"，单条增删改相对笨重。所以工业引擎多用"段"来管理：新文档进新段，旧段定期合并。这也是 Lucene 段合并的由来，后面会拆。
没有免费的午餐。倒排用"建索引时的重"，换了"查询时的快"。这笔买卖，在搜索场景下怎么算都值。
七、动手算一笔账：倒排到底快多少
光说概念不够，算笔账。假设有三篇文档：
文档1: "无线 耳机 降噪 无线" （"无线"出现2次，位置0、3） 文档2: "有线 耳机 便宜" 文档3: "耳机 降噪 好玩"建完倒排，词典和倒排表长这样：
词典: 无线, 耳机, 降噪, 有线, 便宜, 好玩 倒排: 无线 → [(1, 词频2, 位置0,3)] 耳机 → [(1,..),(2,..),(3,..)] 降噪 → [(1,..),(3,..)] ...现在查"无线 耳机"，取两条倒排链求交集，得到文档1。全程只读了和这两个词相关的少量数据。
换成 LIKE 会怎样？数据库得把三篇文档逐字扫一遍，判断"无线"和"耳机"是不是子串。文档少看不出差别，可一旦文档涨到 1 亿篇，LIKE 要扫完 1 亿篇再逐字匹配，耗时随文档数线性增长，几分钟都算快的。倒排查询耗时只和"命中词的倒排链长度"有关，和总文档数基本脱钩。
【数量级对比（示意）】 文档量 LIKE扫描耗时 倒排查询耗时 1 万篇 ~0.1 秒 ~1 毫秒 1 亿篇 ~几百秒 ~几毫秒这账一算，倒排为什么是心脏，就毫无悬念了。也正是因为这笔账，后面 Lucene 才会花大力气压缩倒排链（变长编码、PForDelta 那些），毕竟链长可能上亿，压缩省下的不只是空间，还有 IO 时间。
再补一句：倒排链之所以能"求交集"这么快，除了有序，还靠跳表（SkipList）这种结构跳过不可能命中的区间。这个我们写查询篇会亲手实现，现在你只要记住"有序 + 跳着比"这六个字。
八、倒排的近亲：正排的进化与列式存储
第七节的账算完，再回头看正排。前面说正排负责"取详情"，按文档 ID 返回整条记录，这是最朴素的行式存储。可当你要排序、要聚合（比如"按价格从低到高"“统计每个品牌的商品数”），行式正排就吃力了：为了排个序，得把每篇文档的"价格"字段都读一遍，IO 浪费严重。
于是有了列式存储的思路：把同一字段的所有值竖着存在一起。要排价格，只读价格这一列；要聚品牌，只读品牌这一列。Lucene 里的 DocValues 就是这么回事，它把正排从"按行"翻成"按列"，专门伺候排序和聚合。
【行式 vs 列式 正排】 行式(逐文档): Doc1[标题,价格,品牌] Doc2[标题,价格,品牌] ... 列式(逐字段): 价格列[10,20,15,...] 品牌列[...] ← 排序/聚合只读一列这点对后面理解 Lucene 和 ES 很关键。很多人分不清倒排和 DocValues：记住，倒排管"找得到"（检索），DocValues 管"排得动、聚得快"（分析）。一个负责查，一个负责算。等我们钻进 Lucene 原理篇，会专门拆 DocValues 的几种类型和压缩方式。现在你只要建立"正排也能按列存、而且很有用"这个认知。
本篇小结
全文索引是搜索引擎的心脏，核心就是倒排结构：词典负责快速定位词，倒排链列出包含该词的文档，倒排项里还记着词频和位置（位置支撑短语查询）。倒排负责"找"，正排负责"取详情"，两者配合才完整。倒排的代价是建索引重、占空间、更新不灵活，于是引出段管理和压缩这些后续话题。
下一篇，我们把视野拉宽一点，聊聊为什么单机早晚不够用（分布式计算），以及用户真正面对的搜索界面长什么样。
上一篇【第04篇】网络爬虫：给搜索引擎当采风人
下一篇【第06篇】分布式计算与搜索用户界面：不止是检索
