查询太慢？看看 ES 是如何把索引的性能压榨到极致的！，java 基础程序设计

**Term Dictionary：**把 Term 按字典序排列，然后用二分法查找 Term （存在磁盘）**Term Index：**是 Term Dictionary 的索引，存 Term 的前缀，和与该前缀对应的 Term Dictionary 中的第一个 Term 的 block 的位置，找到这个第一个 Term 后会再往后顺序查找，直到找到目标 Term。（存在内存）

Term Index 的压缩所以，理论上 Term Index 的数据结构就是：Map<Term 的前缀, 对应的 block 的位置>但是 Term 量大的情况下同样会把内存撑爆。所以有了基于 FST 的压缩技术。Finite State Transducers（FST）：有穷状态转换器，Term Index 采用的压缩技术。举个例子：

【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开：qq.cn.hn/FTf 免费领取

Map[“cat”??- > 5, “deep” - > 10, “do” - > 15, “dog” - > 2, “dogs” - > 8?]

• 每条边有两条属性，一个表示 label（key 的元素,上图有点问题，应该是指向 a 的），另一个表示 Value(out)。

• 每个节点有两个属性，Final=true/false（有 key 再这个节点结束则为 true）；final 为 true 时，还有个 FinalOut，FinalOut=entry 的 value 值-该路径 out 值之和。

• 举个例子：8 号节点，对应的 entry 的 key 是 do，value 是 15，而该路径 out 值之和是 2，所以 FinalOut=15-2=13

• out 值怎么来的？

• 当只有一条数据写入时如 cat，则第一个字节即“c”的 out 值就等于该 entry 的 value 值即“5”；

• 当 deep 写入时因为后面 d 开头的数据还没写，所以“d”的 out 值就是“10”；

• 当 do 写入时，因为“d”=“10”，所以“o”=“15”-“10”=“5”

• 当 dog 写入时，因为“d”=“10”，“o”=“5”，已经超过了 dog 的值“2”，此时，会把“d”设为“2”，“o”设为“0”，这样才能满足 dog=“2”的情况。

• 但是，这样 deep 和 do 的 out 值就要重新分配了

• deep 的整条路径和为“10”，已知“d”=“2”，所以“e”承包剩下的“8”。

• do 的整条路径和为“15”，已经“d”=“2”，“o”=“0”，没有 label 了，所以 FinalOut=15-2-0=13。

由上所述，不难得出，FST 查询的复杂度时 O(1)，能快速定位到目的 Term 前缀的 Block 位置。

Posting List 的压缩关键在于：增量编码压缩，将大数变小数，按字节存储。原理就是通过增量，将原来的大数变成小数仅存储增量值，再精打细算按 bit 排好队，最后通过字节存储。

假设有某个 posting list：?[1,3,4,7,10]对应的 bitmap 就是：?[1,0,1,1,0,0,1,0,0,1]

用 0/1 表示某个值是否存在，比如 10 这个值就对应第 10 位，对应的 bit 值是 1，这样用一个字节就可以代表 8 个文档 id，旧版本(5.0 之前)的 Lucene 就是用这样的方式来压缩的，但这样的压缩方式仍然不够高效，如果有 1 亿个文档，那么需要 12.5MB 的存储空间，这仅仅是对应一个索引字段(我们往往会有很多个索引字段)。Bitmap 的缺点是存储空间随着文档个数线性增长。

将 posting list 按照 65535 为界限分块，比如第一块所包含的文档 id 范围在 0~65535 之间，第二块的 id 范围是 65536~131071，以此类推。再用<商，余数>的组合表示每一组 id，这样每组里的 id 范围都在 0~65535 内了，剩下的就好办了，既然每组 id 不会变得无限大，那么我们就可以通过最有效的方式对这里的 id 存储。short[] 占的空间：2bytes（65535 = 2^16-1 ?是 2bytes 能表示的最大数）bitmap 占的空间: 65536/8 = 8192bytes 当 block 块里元素个数不超过 4096，用 short[]，因为 4096 个 short[]才等于 8192bytes；而一个 bitmap 就等于 8192bytes 了，虽然它能存 65536 个元素。

联合索引联合索引通俗地说就是找到满足多个搜索条件的文档 ID。那么这种场景下，倒排索引如何满足快速查询的要求呢？

• 利用跳表(Skip list)的数据结构快速做“与”运算，或者

• 利用上面提到的 bitset 按位“与”

先看看跳表的数据结构：

将一个有序链表 level0，挑出其中几个元素到 level1 及 level2，每个 level 越往上，选出来的指针元素越少，查找时依次从高 level 往低查找，比如 55，先找到 level2 的 31，再找到 level1 的 47，最后找到 55，一共 3 次查找，查找效率和 2 叉树的效率相当，但也是用了一定的空间冗余来换取的。假设有下面三个 posting list 需要联合索引：