【ElasticSearch从入门到架构师】第8章：倒排索引深度剖析

本章导读倒排索引是ElasticSearch的心脏理解它的存储结构、匹配机制和算法原理是成为ES架构师的必经之路。本章将深入剖析倒排索引的底层实现带你看透ES为什么这么快。一、正排索引 vs 倒排索引核心差异1.1 什么是正排索引Forward Index正排索引是我们最熟悉的索引方式也是关系型数据库如MySQL的默认索引模式。核心思想以文档ID为Key以文档内容为Value。结构示例文档ID: 1 文档内容: ElasticSearch是一个分布式搜索引擎 文档ID: 2 文档内容: ElasticSearch使用倒排索引实现快速检索 文档ID: 3 文档内容: 搜索引擎的核心技术是倒排索引查询过程如果要搜索ElasticSearch数据库必须逐行扫描所有文档时间复杂度O(N)N为文档总数这就是传统的LIKE %ElasticSearch%为什么慢适用场景✅ 精确匹配ID查询、等值查询✅ 范围查询WHERE id 100❌ 全文检索性能灾难1.2 什么是倒排索引Inverted Index倒排索引颠覆了正排索引的映射关系。核心思想以词项Term为Key以包含该词项的文档列表为Value。结构示例接上面的文档词项: ElasticSearch 倒排列表: [文档1, 文档2] 词项: 倒排索引 倒排列表: [文档2, 文档3] 词项: 搜索引擎 倒排列表: [文档3]查询过程搜索ElasticSearch → 直接查词典找到该词项 → 获取倒排列表[1, 2]时间复杂度O(1)或O(logN)取决于词典实现这就是ES快如闪电的秘密核心差异对比表维度正排索引倒排索引映射方向文档ID → 内容词项 → 文档列表查询方式全表扫描词典查找时间复杂度O(N)O(1) ~ O(logN)适用场景精确查询、范围查询全文检索、模糊匹配典型应用MySQL B树索引ElasticSearch、Lucene存储开销较小较大需存储词典倒排表1.3 为什么叫倒排这是一个历史命名问题正排Forward文档 → 词项文档包含哪些词倒排Inverted词项 → 文档词项在哪些文档中出现倒排的含义是颠倒了映射方向而不是反向索引的意思。1.4 实际应用对比假设有100万篇文档要搜索包含架构师的文档MySQL正排SELECT*FROMarticlesWHEREcontentLIKE%架构师%;需要扫描100万行无法使用索引响应时间秒级甚至分钟级ElasticSearch倒排GET /articles/_search { query: { match: { content: 架构师 } } }词典查找架构师 → O(1)获取倒排列表 → O(1)响应时间毫秒级二、倒排索引存储结构词典、倒排表、词频、位置、偏移量一个完整的倒排索引由多个核心组件构成每个组件都承载着关键信息。2.1 词典Term Dictionary作用存储所有不重复的词项Term并提供快速查找能力。实现结构Lucene 4.0之前使用跳跃表Skip ListLucene 4.0之后使用FSTFinite State Transducer有限状态转换器FST的优势内存占用极小共享前缀压缩查询速度极快O(len(term))支持前缀查询、模糊查询FST结构示意图输入词项列表: [cat, deep, do, dog, dogs] FST结构共享前缀: (start) | c | a | t (end, cat) (start) | d -- o -- g (end, do/dog) | | e s (end, dogs) | e | p (end, deep)关键特性词项是经过分析的经过分词、归一化、去停用词等处理词典是有序存储的支持范围查询和前缀查询2.2 倒排表Posting List作用存储每个词项对应的文档列表是倒排索引的核心数据。基础结构Term: ElasticSearch Posting List: [1, 3, 5, 8, 13, 21, ...]表示词项ElasticSearch出现在文档ID为1、3、5、8…的文档中。倒排表的三种存储模式模式描述适用场景有序数组文档ID按升序排列小规模数据跳跃表Skip List增加跳跃指针加速合并中等规模位图Bitset/Roaring Bitmap用bit位表示文档是否存在大规模、稀疏数据Roaring Bitmap原理ES 5.0默认将32位整数划分为2^16个块chunk每个块根据数据密度选择不同的存储方式数组、位图、混合极大压缩存储空间加速集合运算AND、OR、NOT2.3 词频Term Frequency, TF作用记录词项在每个文档中出现的次数用于后续的相关性打分。存储结构Term: ElasticSearch Posting List with TF: [ { docId: 1, tf: 3 }, // ElasticSearch在文档1中出现3次 { docId: 3, tf: 1 }, // 在文档3中出现1次 { docId: 5, tf: 7 }, // 在文档5中出现7次 ... ]为什么需要TF词频越高说明该词项对文档的主题越重要是TF-IDF和BM25算法的核心输入之一TF的归一化原始TF可能受文档长度影响长文档词频天然更高通常使用log(1 tf)或tf / maxTF进行归一化2.4 位置Position作用记录词项在文档中的精确位置支持短语查询Phrase Query和邻近查询Proximity Query。存储结构Term: ElasticSearch Posting List with Positions: [ { docId: 1, tf: 3, positions: [5, 18, 42] // ElasticSearch在文档1中分别出现在第5、18、42个词项位置 }, { docId: 3, tf: 1, positions: [12] }, ... ]为什么需要位置信息短语查询查询: ElasticSearch 架构师 要求: ElasticSearch和架构师必须相邻且顺序一致 实现: 检查两个词项的position是否连续 [pos, pos1]邻近查询查询: ElasticSearch 架构师~5 要求: 两个词项出现位置相距不超过5个词项 实现: 检查 |pos1 - pos2| 5高亮显示知道词项位置才能准确标记高亮片段2.5 偏移量Offset作用记录词项在原始文本中的字符偏移用于精确高亮和片段提取。存储结构Term: ElasticSearch Posting List with Offsets: [ { docId: 1, tf: 2, positions: [5, 18], offsets: [ { start: 23, end: 37 }, // 第1次出现第23~37个字符 { start: 156, end: 170 } // 第2次出现第156~170个字符 ] }, ... ]为什么需要偏移量高亮显示需要知道词项在原始字符串中的精确起止位置位置 vs 偏移量Position词项在分词后的位置第几个tokenOffset词项在原始文本中的字符位置两者不同因为分词可能将HelloWorld分为Hello和World2.6 完整倒排索引结构图┌─────────────────────────────────────────────────────┐ │ 倒排索引Inverted Index │ ├─────────────────────────────────────────────────────┤ │ │ │ ┌─────────────┐ │ │ │ 词 典 │ ← FST结构内存存储 │ │ │ (Term Dict) │ │ │ └──────┬──────┘ │ │ │ 每个词项指向对应的倒排表 │ │ ▼ │ │ ┌─────────────────────────────────────────┐ │ │ │ 倒排表Posting List │ │ │ ├─────────────────────────────────────────┤ │ │ │ Term: ElasticSearch │ │ │ │ ┌─────────────────────────────────────┐ │ │ │ │ │ DocID │ TF │ Positions │ Offsets │ │ │ │ │ ├─────────────────────────────────────┤ │ │ │ │ │ 1 │ 3 │ [5,18,42] │ [...] │ │ │ │ │ │ 3 │ 1 │ [12] │ [...] │ │ │ │ │ │ 5 │ 7 │ [...] │ [...] │ │ │ │ │ └─────────────────────────────────────┘ │ │ │ └─────────────────────────────────────────┘ │ │ │ └─────────────────────────────────────────────────────┘2.7 实战查看ES中的倒排索引使用_termvectorsAPI可以查看文档的词项向量信息GET/articles/_termvectors/1{fields:[content],term_statistics:true,field_statistics:true,positions:true,offsets:true}返回示例{_id:1,term_vectors:{content:{terms:{elasticsearch:{term_freq:3,tokens:[{position:5,start_offset:23,end_offset:37},{position:18,start_offset:156,end_offset:170},{position:42,start_offset:380,end_offset:394}]}}}}}三、全文检索匹配、打分机制底层逻辑当用户发起一个搜索请求时ES内部究竟发生了什么这一节带你深入ES的查询执行全流程。3.1 查询执行全流程用户发起搜索: ElasticSearch 架构师 │ ▼ ┌───────────────────────────────────────┐ │ 第1步查询解析Query Parsing │ │ - 解析查询DSL │ │ - 生成查询语法树 │ └───────────────────────────────────────┘ │ ▼ ┌───────────────────────────────────────┐ │ 第2步分词Analysis │ │ - 对查询文本进行分词 │ │ - ElasticSearch 架构师 │ │ → [elasticsearch, 架构师] │ └───────────────────────────────────────┘ │ ▼ ┌───────────────────────────────────────┐ │ 第3步词典查找Dictionary Lookup │ │ - 在FST词典中查找词项 │ │ - elasticsearch → 找到 │ │ - 架构师 → 找到 │ └───────────────────────────────────────┘ │ ▼ ┌───────────────────────────────────────┐ │ 第4步获取倒排表Fetch Postings │ │ - 读取每个词项的倒排列表 │ │ - elasticsearch → [1,3,5,8,...] │ │ - 架构师 → [2,3,7,15,...] │ └───────────────────────────────────────┘ │ ▼ ┌───────────────────────────────────────┐ │ 第5步倒排表合并Posting Merge │ │ - 根据查询类型进行集合运算 │ │ - AND: 交集 [3] │ │ - OR: 并集 [1,2,3,5,7,8,...] │ │ - 使用跳跃表/Roaring Bitmap加速 │ └───────────────────────────────────────┘ │ ▼ ┌───────────────────────────────────────┐ │ 第6步打分Scoring │ │ - 对每个匹配文档计算相关性分数 │ │ - 使用TF-IDF或BM25算法 │ │ - 默认使用BM25ES 5.0 │ └───────────────────────────────────────┘ │ ▼ ┌───────────────────────────────────────┐ │ 第7步排序与返回Sort Return │ │ - 按分数降序排列 │ │ - 返回Top N结果 │ │ - 支持from/size分页 │ └───────────────────────────────────────┘3.2 倒排表合并算法当查询包含多个词项时需要合并多个倒排表。这是ES查询性能的关键瓶颈之一。场景查询elasticsearch AND 架构师倒排表1 (elasticsearch): [1, 3, 5, 8, 13, 21, 34, ...] 倒排表2 (架构师): [2, 3, 7, 8, 13, 55, ...] 合并结果 (交集): [3, 8, 13]合并策略1跳跃表合并Skip List Merge倒排表1: [1, 3, 5, 8, 13, 21, 34, 55, 89, ...] ↑ 倒排表2: [2, 3, 7, 8, 13, 55, ...] ↑ 比较 5 vs 7: 5 7前进倒排表1的指针 比较 8 vs 7: 8 7前进倒排表2的指针 比较 8 vs 8: 相等记录到结果集两个指针都前进时间复杂度O(m n)m和n为两个倒排表的长度合并策略2位图合并Bitset Merge倒排表1 → Bitset1: 1010100101001010... 倒排表2 → Bitset2: 0101001010100101... AND操作: 0010000000000000... (按位AND)优势位运算极快CPU原生支持适合倒排表较大的场景ES使用Roaring Bitmap实现3.3 打分机制底层逻辑ES使用**向量空间模型Vector Space Model**来计算文档相关性。核心思想将每个文档表示为一个高维向量将查询也表示成一个向量计算两个向量的余弦相似度作为相关性分数向量表示文档向量: D [tf(t1,d), tf(t2,d), ..., tf(tn,d)] 查询向量: Q [tf(t1,q), tf(t2,q), ..., tf(tn,q)] 余弦相似度: score(D, Q) cosθ (D·Q) / (|D| × |Q|)Lucene的实际实现score(D, Q) coord(D, Q) × queryNorm(Q) × ∑(tf(t, D) × idf(t) × boost(t)) ↑ ↑ ↑ 协调因子 查询归一化 词项权重各因子详解coord(D, Q) - 协调因子奖励包含更多查询词项的文档包含3个查询词项比包含2个的分数更高queryNorm(Q) - 查询归一化使不同查询之间的分数具有可比性不影响文档间的相对排序tf(t, D) - 词频词项在文档中的出现次数idf(t) - 逆文档频率词项在多少文档中出现过boost(t) - 词项权重可以手动提升某些词项的重要性3.4 实战解读ES的打分解释使用explain参数可以查看每个文档的打分细节GET/articles/_search{explain:true,query:{match:{content:ElasticSearch 架构师}}}返回示例简化{_explanation:{value:12.5,description:sum of,details:[{value:8.2,description:weight(content:elasticsearch in 3) [BM25Similarity], result of:,details:[{description:idf, computed as log(1 (N - n 0.5) / (n 0.5)),value:2.1},{description:tfNorm, computed as (freq * (k1 1)) / (freq k1 * (1 - b b * dl / avgdl)),value:3.9}]},{value:4.3,description:weight(content:架构师 in 3) [BM25Similarity], result of:,...}]}}四、TF-IDF、BM25 算法原理与打分权重优化这是ES相关性打分的核心算法理解它们能帮你精确控制搜索结果的质量。4.1 TF-IDF 算法4.1.1 算法思想TF-IDF Term Frequency × Inverse Document FrequencyTF词频词项在文档中出现的频率假设一个词在文档中出现次数越多它对该文档越重要IDF逆文档频率词项在多少文档中出现假设一个词出现的文档越多它的区分度越低如的、是等停用词4.1.2 TF-IDF公式TF(t, D) 词项t在文档D中出现的次数 IDF(t) log( N / (n 1) ) N: 文档总数 n: 包含词项t的文档数 TF-IDF(t, D) TF(t, D) × IDF(t)直观理解如果ElasticSearch在文档中出现5次 → TF 5如果ElasticSearch只在10篇文档中出现总共1000篇→ IDF log(1000/10) 2TF-IDF 5 × 2 104.1.3 TF-IDF的问题词频无上限一个词出现100次比出现1次的文档分数高100倍这不合理文档长度偏差长文档天然有更高的词频无法区分常见词和关键词需要手动设置停用词4.2 BM25 算法ES默认BM25Best Matching 25是TF-IDF的改进版也是ES 5.0之后的默认打分算法。4.2.1 BM25的核心改进TF饱和函数词频增长对分数的贡献逐渐递减对数函数文档长度归一化长文档的分数会被适度惩罚可调参数提供k1和b两个参数供调优4.2.2 BM25公式BM25(t, D) IDF(t) × (TF(t, D) × (k1 1)) / (TF(t, D) k1 × (1 - b b × (|D| / avgdl))) ↑ ↑ ↑ 逆文档频率 词频饱和度 文档长度归一化参数说明参数默认值含义调优建议k11.2控制TF饱和度值越大TF的影响越大0~3之间调节b0.75控制文档长度归一化强度0完全不归一化1完全归一化公式直观图解TF饱和度曲线k11.2: 分数 ↑ │ ╱╲ │ ╱ ╲ │ ╱ ╲ │ ╱ ╲ │ ╱ ╲ │ ╱ ╲___________ │ ╱ │ ╱ │ ╱ │╱ └────────────────────────────→ TF 0 ∞ 说明TF10时的分数远低于TF1时的10倍解决了TF无上限问题4.2.3 IDF的BM25版本BM25使用了一个改进的IDF公式IDF(t) log(1 (N - n 0.5) / (n 0.5)) 其中 N: 文档总数 n: 包含词项t的文档数与经典IDF的区别避免了IDF为负的情况当n N/2时对稀有词项的IDF值更平滑4.3 BM25打分完整示例场景搜索ElasticSearch 架构师计算文档3的分数已知信息文档总数 N 1000 包含elasticsearch的文档数 n1 50 包含架构师的文档数 n2 200 文档3的长度 |D| 500词 平均文档长度 avgdl 300词 词项elasticsearch在文档3中出现 3次 词项架构师在文档3中出现 1次 k1 1.2, b 0.75计算过程Step 1: 计算IDF IDF(elasticsearch) log(1 (1000 - 50 0.5) / (50 0.5)) log(1 950.5/50.5) ≈ 3.0 IDF(架构师) log(1 (1000 - 200 0.5) / (200 0.5)) log(1 800.5/200.5) ≈ 1.6 Step 2: 计算TF归一化因子 文档长度因子 1 - b b × (|D| / avgdl) 1 - 0.75 0.75 × (500/300) ≈ 1.5 Step 3: 计算BM25分数 BM25(elasticsearch, D3) 3.0 × (3 × (1.2 1)) / (3 1.2 × 1.5) 3.0 × 6.6 / 4.8 ≈ 4.1 BM25(架构师, D3) 1.6 × (1 × (1.2 1)) / (1 1.2 × 1.5) 1.6 × 2.2 / 2.8 ≈ 1.3 总分 4.1 1.3 5.44.4 打分权重优化实战4.4.1 调整字段权重Field BoostGET/articles/_search{query:{multi_match:{query:ElasticSearch,fields:[title^3,content]// title字段权重是content的3倍}}}4.4.2 调整BM25参数PUT/articles{settings:{similarity:{my_bm25:{type:BM25,k1:1.5,// 提高k1让TF影响更大b:0.5// 降低b减少文档长度影响}}},mappings:{properties:{content:{type:text,similarity:my_bm25}}}}参数调优建议场景k1建议b建议原因短文本标题、标签1.5~2.00.3~0.5文档长度差异小不需要强归一化长文本文章内容1.0~1.20.75~0.9需要强归一化避免长文档优势精确匹配场景0.5~1.00.0减少TF影响更依赖IDF4.4.3 使用Function Score自定义打分GET/articles/_search{query:{function_score:{query:{match:{content:ElasticSearch}},functions:[{field_value_factor:{field:likes,factor:1.2,modifier:log1p// 点赞数取log避免数值过大}},{gauss:{publish_date:{origin:now,scale:30d,// 30天内的文章分数更高offset:7d,decay:0.5}}}],score_mode:multiply,// 分数相乘boost_mode:sum// 最终分数 原始分数 函数分数}}}五、索引压缩技术提升存储利用率与查询速度ES存储着海量数据索引压缩是降低存储成本、提升查询性能的关键技术。5.1 为什么需要索引压缩问题100万篇文档每篇平均500词 → 假设有50万不重复词项每个词项的倒排表可能包含数十万个文档ID如果不压缩倒排索引的存储开销可能是原始文本的3~5倍目标减少磁盘占用降低存储成本减少内存占用更多数据可以缓存在内存减少I/O提升查询速度5.2 倒排表的压缩编码倒排表本质上是递增的整数序列文档ID是有序的适合使用差分编码 变长整数编码。5.2.1 差分编码Delta Encoding原理不存储绝对的文档ID而是存储相邻ID的差值。原始倒排表: [1, 5, 8, 13, 21, 34] 差分编码后: [1, 4, 3, 5, 8, 13] (后一个减去前一个) 优势 - 原始值范围1~34需要6 bits - 差值范围1~13需要4 bits - 压缩率约33%5.2.2 变长整数编码Variable Byte Encoding原理使用1~N个字节表示整数小整数用少字节大整数用多字节。编码规则每个字节的**最高位MSB**作为延续位MSB 0这是最后一个字节MSB 1还有后续字节剩余7位存储数据示例编码整数 300300的二进制: 00000001 00101100 按7位分组: 0000010 0101100 加上MSB: 10000010 00101100 ↑ ↑ 延续位 最后字节 存储: 0x82 0x2C (只需要2个字节)压缩效果原始定长4字节: [300, 5, 42, 1000] 压缩后变长: [2字节, 1字节, 1字节, 2字节] 6字节 vs 16字节 压缩率: 62.5%5.2.3 Elias-Fano编码Lucene默认原理将整数分为低位部分和高位部分分别编码。示例编码序列 [5, 9, 12, 15, 20]Step 1: 确定分区位数 最大值20的二进制: 10100 (5 bits) 选择低位数 u floor(log2(N)) floor(log2(5)) 2 高位数 5 - 2 3 Step 2: 编码低位直接存储 5 → 01 9 → 01 12 → 00 15 → 11 20 → 00 Step 3: 编码高位使用一元编码 高位: [1, 2, 3, 3, 5] 一元编码: 0 10 110 110 11110 最终编码: [低位...] [高位...]Elias-Fano的优势编码和解码都很快O(1)随机访问压缩率高接近信息熵下界支持高效的succ(v)操作找到大于等于v的最小编码值5.3 词典压缩FSTFST本身就是一种压缩结构它通过共享前缀来大幅减少存储空间。示例原始词项列表未压缩: cat → 3字节 catch → 5字节 category → 8字节 总计: 16字节 FST压缩后: 共享前缀 cat只存储一次 cat → 指向cat节点 终止标记 catch → 指向cat节点 ch category → 指向cat节点 egory 总计: ≈8字节压缩率50%FST的额外优势支持模糊查询可以快速找到与给定词项编辑距离≤k的所有词项支持前缀查询可以高效遍历所有以某前缀开头的词项支持自动补全配合单词查找树Trie实现搜索建议5.4 帧压缩Frame Of Reference, FOR原理将倒排表分成多个块block每个块使用适合的编码方式。示例倒排表: [1, 100, 101, 102, 500, 501, 502] 分块: Block1: [1, 100] → 范围大使用位图 Block2: [101, 102] → 范围小使用差分变长编码 Block3: [500, 501, 502] → 范围小使用差分变长编码 每个块存储: - 块类型标记1字节 - 块数据压缩后Lucene的实现默认块大小128个文档ID根据块内数据的分布自动选择编码方式查询时只解压需要的块不需要解压整个倒排表5.5 实战查看索引压缩效果查看索引大小# 查看某个索引的存储大小GET /_cat/indices/articles?vhindex,store.size# 返回示例index store.size articles2.3gb查看段的信息GET /articles/_segments优化索引存储PUT/articles/_settings{index.codec:best_compression// 使用最高压缩比LZ4 → DEFLATE}压缩效果对比压缩模式压缩算法压缩率查询性能defaultLZ4中等最快best_compressionDEFLATE最高约30%额外压缩稍慢5.6 存储优化最佳实践合理设置分片数每个分片的大小建议在10GB~50GB之间分片过多 → 元数据开销大分片过大 → 恢复慢、迁移慢启用索引压缩PUT/articles/_settings{index.codec:best_compression}定期Force MergePOST /articles/_forcemerge?max_num_segments1将多个段合并为少量段减少文件句柄占用提升查询性能使用合适的数据类型能用keyword就不用text减少分词开销能用integer就不用long减少存储启用冷温热架构热数据SSD 不压缩温数据SSD 压缩冷数据HDD 最高压缩本章小结本章深入剖析了ElasticSearch倒排索引的底层实现重点内容包括正排 vs 倒排理解了两种索引的核心差异和应用场景倒排索引结构掌握了词典FST、倒排表、词频、位置、偏移量的作用和存储方式查询执行流程从查询解析到结果返回的完整链路打分算法深入理解TF-IDF和BM25的原理及参数调优索引压缩掌握了差分编码、变长整数、Elias-Fano、FST等压缩技术下章预告第9章将深入讲解ES的分布式架构包括数据分片、副本机制、路由策略、分布式查询流程等核心内容。如有疑问欢迎在评论区留言讨论