Elasticsearch倒排索引原理：词典树与Posting List的压缩存储
大约 9 分钟
Elasticsearch倒排索引原理：词典树与Posting List的压缩存储
适读人群：Java后端开发、搜索工程师、对全文搜索底层感兴趣的工程师 | 阅读时长：约25分钟
开篇故事
2022年，我们把商品搜索从MySQL的LIKE查询迁移到了Elasticsearch。
迁移前：WHERE name LIKE '%连衣裙%'，1000万商品表，全表扫描，耗时8秒。
迁移后：ES搜索「连衣裙」，1000万文档，耗时30ms。
性能差距270倍。
为什么ES这么快？很多人的答案是「因为ES用了倒排索引」，但这只说对了一半。更深入的问题是：倒排索引是怎么存储的？为什么能在毫秒内完成搜索？
带着这个问题，我翻了ES底层Lucene的源码，今天把倒排索引的完整实现讲清楚。
一、正排索引 vs 倒排索引
正排索引（MySQL B+树）：
文档ID → 文档内容
1 → "红色连衣裙，女款，M码"
2 → "蓝色连衣裙，修身款"
3 → "牛仔裤，直筒款"
搜索「连衣裙」：必须扫描所有文档，判断是否包含关键词 → O(N)倒排索引：
词语 → 包含该词语的文档列表（Posting List）
「连衣裙」→ [1, 2]
「红色」 → [1]
「蓝色」 → [2]
「牛仔裤」→ [3]
搜索「连衣裙」：直接查词典 → 获取Posting List[1,2] → O(1)二、底层原理：Lucene的完整存储结构
2.1 分段存储（Segment）
Lucene将索引数据存储在多个不可变的Segment（段）中：
Lucene索引结构：
Segment_1 (不可变):
├── .tim (Term Index) 词典文件
├── .tip (Term Dictionary) 词典索引（FST）
├── .doc (Posting List) 文档ID列表
├── .pos (Positions) 词语在文档中的位置
└── .nvd (Norms) 文档评分相关
Segment_2: ...
Segment_N: ...
写入流程：
新文档 → 内存Buffer（IndexWriter缓冲）
→ 定期flush → 新Segment（不可变）
→ 后台merge → 大Segment（合并小Segment）2.2 词典结构：FST（有限状态转换机）
这是ES搜索快的关键之一。Lucene不用普通的HashMap存词典，而是用FST（Finite State Transducer）。
FST是一种压缩的字典树，同时具备：
- 精确查找：O(term_length)，比HashMap的O(1)慢一点，但节省大量内存
- 前缀查询：天然支持
- 范围查询：按字典序遍历
FST存储示例（存储 "car", "cat", "dog" 三个词）：
传统Trie树（不压缩）：
root → 'c' → 'a' → 'r' (end)
→ 't' (end)
→ 'd' → 'o' → 'g' (end)
FST（共享前缀和后缀）：
共享前缀 "ca"：car 和 cat 共用 'c','a' 两个节点
内存占用：
100万词的FST：约20-50MB
100万词的HashMap：约500MB（压缩了10-25倍）ASCII图展示FST结构：
[root]
/ \
'c' 'd'
| |
'a' 'o'
/ \ \
'r' 't' 'g'
END END END
→ 1 → 2 → 3 (词的序号)2.3 Posting List的压缩：Frame of Reference (FOR)
找到词语后，需要读取它的Posting List（包含该词的所有文档ID）。
对于热门词「连衣裙」，可能有100万个文档ID： [1, 3, 7, 15, 100, 101, 102, 200, ...]
如果每个ID用8字节存储，100万个ID需要8MB。Lucene使用FOR（Frame of Reference）压缩：
原始ID列表（升序排列）：
[1, 3, 7, 15, 100, 101, 102, 200, ...]
步骤1：差分编码（存相邻ID的差值）
[1, 2, 4, 8, 85, 1, 1, 98, ...]
差值通常很小！
步骤2：分块（每块128个差值）
Block1: [1, 2, 4, 8, 85, 1, 1, 98, ...]
Block2: [...]
步骤3：找到每块中最大值，确定每个值需要的bit数
Block1最大值=98，需要7 bits
用7 bits存储Block1中的128个差值 = 128 * 7 = 896 bits = 112 bytes
压缩比：原始128个ID × 8 bytes = 1024 bytes
压缩后：112 bytes
压缩率：89% !!!2.4 高频词的跳表（Skip List）
对于超大的Posting List，直接线性扫描合并效率低。Lucene在Posting List上建了跳表加速交集运算：
Posting List: [1, 3, 7, 15, 100, 101, 102, 200, 500, 1000, ...]
跳表（每隔128个元素加一个跳跃点）：
跳跃点1: (id=1, offset=0) ← 从位置0开始有128个ID
跳跃点2: (id=200, offset=128) ← 从位置128开始有128个ID
跳跃点3: (id=500, offset=256) ← ...
计算 "连衣裙" AND "红色" 的交集：
连衣裙的Posting: [1, 2, 3, 100, 200, ...]
红色的Posting: [1, 150, 200, 350, ...]
利用跳表：当连衣裙扫到100时，红色下一个>100的元素在跳跃点处找到
大幅减少了比较次数三、完整解决方案与代码
3.1 ES索引设计：控制映射以优化存储
// ES 7.x Java High Level REST Client示例
@Component
public class ProductIndexManager {
@Autowired
private RestHighLevelClient esClient;
/**
* 创建商品索引（优化映射设计）
*/
public void createProductIndex() throws IOException {
CreateIndexRequest request = new CreateIndexRequest("products");
// 索引设置
request.settings(Settings.builder()
.put("number_of_shards", 5) // 5个主分片
.put("number_of_replicas", 1) // 1个副本
.put("index.max_result_window", 10000) // 限制分页深度
// 分词器配置
.put("analysis.analyzer.ik_smart.type", "custom")
.put("analysis.analyzer.ik_smart.tokenizer", "ik_smart")
);
// 字段映射
Map<String, Object> properties = new HashMap<>();
// 商品名称：需要全文搜索 + 精确匹配（双字段）
properties.put("name", Map.of(
"type", "text",
"analyzer", "ik_smart", // 索引时分词
"search_analyzer", "ik_smart", // 搜索时分词
"fields", Map.of(
"keyword", Map.of(
"type", "keyword", // 精确匹配的keyword子字段
"ignore_above", 256 // 超过256字符不索引
)
)
));
// 价格：数值，用于范围过滤和排序
properties.put("price", Map.of("type", "scaled_float", "scaling_factor", 100));
// 状态：低基数，用keyword
properties.put("status", Map.of("type", "keyword"));
// 商品描述：只需全文搜索，不需要返回原文（设置store=false节省存储）
properties.put("description", Map.of(
"type", "text",
"analyzer", "ik_max_word",
"store", false
));
// 商品标签：keyword数组
properties.put("tags", Map.of("type", "keyword"));
// 创建时间：用于排序和时间范围过滤
properties.put("created_at", Map.of(
"type", "date",
"format", "yyyy-MM-dd HH:mm:ss||epoch_millis"
));
request.mapping(Map.of("properties", properties));
esClient.indices().create(request, RequestOptions.DEFAULT);
}
}3.2 复杂搜索查询
@Service
public class ProductSearchService {
@Autowired
private RestHighLevelClient esClient;
/**
* 多条件商品搜索
* 演示各种ES查询的使用场景
*/
public SearchResult<Product> search(ProductSearchRequest req) throws IOException {
SearchRequest searchRequest = new SearchRequest("products");
SearchSourceBuilder source = new SearchSourceBuilder();
BoolQueryBuilder boolQuery = QueryBuilders.boolQuery();
// 全文搜索：match查询（分词后搜索）
if (StringUtils.hasText(req.getKeyword())) {
boolQuery.must(QueryBuilders.multiMatchQuery(req.getKeyword())
.field("name", 3.0f) // name字段权重3倍
.field("description", 1.0f) // description字段权重1
.type(MultiMatchQueryBuilder.Type.BEST_FIELDS)
);
}
// 精确过滤：term查询（不分词）
if (req.getStatus() != null) {
boolQuery.filter(QueryBuilders.termQuery("status", req.getStatus()));
}
// 范围过滤：range查询
if (req.getMinPrice() != null || req.getMaxPrice() != null) {
RangeQueryBuilder priceRange = QueryBuilders.rangeQuery("price");
if (req.getMinPrice() != null) priceRange.gte(req.getMinPrice());
if (req.getMaxPrice() != null) priceRange.lte(req.getMaxPrice());
boolQuery.filter(priceRange);
}
// 标签过滤：terms查询（OR关系）
if (!CollectionUtils.isEmpty(req.getTags())) {
boolQuery.filter(QueryBuilders.termsQuery("tags", req.getTags()));
}
source.query(boolQuery);
// 排序
if ("price_asc".equals(req.getSort())) {
source.sort("price", SortOrder.ASC);
} else if ("price_desc".equals(req.getSort())) {
source.sort("price", SortOrder.DESC);
} else {
source.sort("_score", SortOrder.DESC); // 默认按相关性评分排序
}
// 分页（避免深分页，推荐使用search_after）
source.from((req.getPage() - 1) * req.getSize());
source.size(req.getSize());
// 高亮
HighlightBuilder highlight = new HighlightBuilder();
highlight.field("name").preTags("<em>").postTags("</em>");
source.highlighter(highlight);
// 聚合：各价格区间的商品数量
source.aggregation(
AggregationBuilders.range("price_ranges")
.field("price")
.addRange(0, 100)
.addRange(100, 300)
.addRange(300, 1000)
.addUnboundedTo(1000)
);
searchRequest.source(source);
SearchResponse response = esClient.search(searchRequest, RequestOptions.DEFAULT);
return buildResult(response, req.getPage(), req.getSize());
}
private SearchResult<Product> buildResult(SearchResponse response, int page, int size) {
long total = response.getHits().getTotalHits().value;
List<Product> products = Arrays.stream(response.getHits().getHits())
.map(hit -> {
Product product = JSON.parseObject(hit.getSourceAsString(), Product.class);
// 设置高亮内容
if (hit.getHighlightFields().containsKey("name")) {
product.setHighlightName(
hit.getHighlightFields().get("name").fragments()[0].string()
);
}
return product;
})
.collect(Collectors.toList());
// 解析聚合结果
Range priceAgg = response.getAggregations().get("price_ranges");
Map<String, Long> priceDistribution = priceAgg.getBuckets().stream()
.collect(Collectors.toMap(
Range.Bucket::getKeyAsString,
Range.Bucket::getDocCount
));
return new SearchResult<>(products, total, page, size, priceDistribution);
}
}3.3 性能对比测试
/**
* MySQL LIKE vs ES 性能对比测试
* 数据量：1000万商品
*/
@SpringBootTest
public class SearchPerformanceTest {
@Autowired
private JdbcTemplate jdbcTemplate;
@Autowired
private ProductSearchService esService;
@Test
public void compareSearchPerformance() throws Exception {
String keyword = "连衣裙";
// MySQL LIKE查询（无索引，全表扫描）
long mysqlStart = System.currentTimeMillis();
jdbcTemplate.query(
"SELECT * FROM products WHERE name LIKE ? LIMIT 20",
ps -> ps.setString(1, "%" + keyword + "%")
);
long mysqlCost = System.currentTimeMillis() - mysqlStart;
System.out.println("MySQL LIKE: " + mysqlCost + "ms"); // 约8000ms
// ES全文搜索
long esStart = System.currentTimeMillis();
ProductSearchRequest req = new ProductSearchRequest();
req.setKeyword(keyword);
req.setPage(1);
req.setSize(20);
esService.search(req);
long esCost = System.currentTimeMillis() - esStart;
System.out.println("ES search: " + esCost + "ms"); // 约30ms
System.out.println("ES是MySQL的" + (mysqlCost / esCost) + "倍快");
}
}四、踩坑实录
坑1：mapping不合理，全文字段做精确匹配
问题：搜索 status="active" 但status字段类型是text
text字段会被分词，"active"被分词为["active"]
用term查询text字段：有时无法命中（分词后的存储可能不同）
报错/现象：
GET products/_search
{"query": {"term": {"status": "ACTIVE"}}}
→ 返回0条结果（"ACTIVE"被分析器转为小写"active"存储）解决方案：
// 低基数枚举值必须用keyword类型，不要用text
properties.put("status", Map.of("type", "keyword")); // 正确
// 如果字段既要全文搜索又要精确匹配：
properties.put("name", Map.of(
"type", "text",
"fields", Map.of(
"keyword", Map.of("type", "keyword") // 子字段用于精确匹配
)
));
// 搜索用 name（分词），过滤用 name.keyword（不分词）坑2：refresh间隔导致写入后立即查询不到
// 写入文档
esClient.index(new IndexRequest("products").id("123").source(doc), RequestOptions.DEFAULT);
// 立即查询
SearchResponse response = esClient.search(new SearchRequest("products")
.source(new SearchSourceBuilder().query(QueryBuilders.termQuery("id", "123"))),
RequestOptions.DEFAULT);
// 可能返回0条！原因：ES默认每1秒刷新一次（refresh），新写入的文档在refresh之前对搜索不可见（但对GET by id可见）。
解决方案：
// 方案1：写入时强制refresh（不推荐生产，影响性能）
IndexRequest req = new IndexRequest("products").id("123").source(doc);
req.setRefreshPolicy(WriteRequest.RefreshPolicy.IMMEDIATE); // 立即刷新
// 方案2：等待refresh（推荐）
req.setRefreshPolicy(WriteRequest.RefreshPolicy.WAIT_UNTIL); // 等待刷新完成再返回
// 方案3：调短refresh间隔（权衡）
// PUT products/_settings
// {"index": {"refresh_interval": "500ms"}}
// 方案4：业务层接受1秒延迟（最佳实践）
// 搜索引擎的定位是近实时搜索，不是强一致存储
// 写入后告诉用户"数据将在1秒内可搜索"坑3：深分页导致OOM
问题：使用 from/size 分页到第1000页
GET products/_search
{"from": 10000, "size": 20}
ES的处理：
每个分片获取前 from+size = 10020 条
5个分片 × 10020 = 50100 条在协调节点内存中排序
随着from增大，内存消耗呈线性增长
报错：
Result window is too large, from + size must be less than or equal to: [10000]解决方案：
// 方案1：search_after（游标分页）
SearchSourceBuilder source = new SearchSourceBuilder();
source.query(QueryBuilders.matchAllQuery());
source.sort("created_at", SortOrder.DESC);
source.sort("_id", SortOrder.ASC); // 保证唯一性
source.size(20);
// 第一页：不传search_after
// 第N+1页：传入第N页最后一条的sort values
if (lastSortValues != null) {
source.searchAfter(lastSortValues);
}
// 从响应中提取sort values用于下次分页
SearchHit lastHit = response.getHits().getHits()[response.getHits().getHits().length - 1];
Object[] nextSearchAfter = lastHit.getSortValues();五、总结与延伸
ES快的核心秘密：
- FST词典：比HashMap节省10-25倍内存，支持前缀查询
- FOR压缩：Posting List压缩率达70-90%，减少磁盘IO
- 跳表：多词AND/OR查询时，快速跳过不需要检查的文档
- 分片并行：查询分发到多个分片并行执行，最终归并结果
ES不是MySQL的替代品：
- ES：全文搜索、复杂聚合、近实时（1秒延迟）
- MySQL：事务、精确查询、强一致（立即可见）
两者配合：数据写入MySQL（主存储），同步到ES（搜索引擎），各司其职。