上一篇【第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篇】分布式计算与搜索用户界面不止是检索