1. Elasticsearch 倒排索引的结构(term dictionary、posting list、doc values)是怎样的?FST(有限状态转换器)如何压缩前缀查找、加速 term 定位?
请描述 Elasticsearch 倒排索引的组成部分(term dictionary、posting list、doc values),并说明 FST(有限状态转换器)如何压缩前缀查找并加速 term 定位?
- 倒排索引的三个核心组件及其职责
- FST 的字典压缩与共享前缀原理
- doc values 与正向索引的关系
倒排索引由三部分组成:term dictionary(词项字典)保存所有不重复的 term 及其元数据,posting list(倒排表)保存每个 term 对应的 doc id 列表、词频和位置信息,doc values 则是列式存储的正向索引,用于排序、聚合和脚本计算。term dictionary 的常规查找是二分查找,但 ES 使用 FST(有限状态转换器)将 term 字典压缩为一张共享前缀的确定型无环图,通过在构建时合并所有 term 的公共前缀,大幅减少存储空间,同时把 O(log n) 的分块二分查找降为接近 O(term 长度) 的单次遍历,从而加速 term 定位。doc values 本质上是按文档倒排的列式存储,与倒排索引互补,避免了排序聚合时遍历多余文档。
倒排索引解决的是"单词到文档"的映射,而 doc values 解决"文档到字段值"的逆向需求,两者配合覆盖检索与聚合两类场景。FST 的巧妙之处在于把前缀共享变成图的共享节点,既压缩又加速,是 ES 大规模分片下保持字典常驻内存的关键。
{
"settings": { "index": { "sort.field": "timestamp", "sort.order": "desc" } },
"mappings": {
"properties": {
"category": { "type": "keyword", "doc_values": true },
"content": { "type": "text", "doc_values": false, "index": true }
}
}
}