ES-深入理解倒排索引

倒排索引

id	product	desc
1	新版 小米 至尊-纪念版手机
1	小米 NFC 手机
3	NFC手机
4	小米 耳机
5	华为 耳机
6	扫地机器人
7	华为 Mata
……	……	……
term_index	term dictionary	posting list
----------	--------------	------------
	小米	1……100W
	华为	6,7,9
	NFC	76,90
	耳机	5352
	红米	643,98
	机器人	645,9806
……	……	……

我们引入这两个表格来理解倒排索引，第一个表是真实的数据，我们根据product这个字段进行分词，然后拆分的词为term dictionary,然后将id,存在posting list。

对于倒排表有两种压缩算法进行存储：
1 Frame OF Reference 索引帧（FOR）

真正的ES存储是类似于第二个例子，采用分组的形式。这大概就是FOR的压缩逻辑，但是缺陷就是如果数据特别离散压缩效果不会很好,采用RBM来进行存储。
2 Roaring BitMap 咆哮位图（RBM）

对于词项字典我们对应的也有方式来存储
1 先来了解一下前缀树
前缀树有一定的复用，每一个终端节点就是一个单词，我们发现如果不是终端节点比如我们查找AB在这里面是找不到的，同时最后DF也是没有复用的存储了多次，因此需要进一步优化。

2 基于前缀树的优化
2.1 有限状态机
有限个状态 同一时间只能处于同一个状态 不同状态之间可以相互转换 状态是无序的
就像下面这张图，我只话了部分边，就是哥哥状态可以相互转换。

2.2 有限状态接收机
在前缀树的基础上我们插入jksj jksjtech jkb estech
4 和 8 为终止节点 数据在边上 节点是数字 如果插入一个单词当前比如之前没有jkb当插入到b的时候发现没有这个字母，则会选择一个红色的节点作为结束，为什么不选4因为选四就会多一个单单词jksjb但实际我们没有不符合我们的期望。

这个里面是否存在ES呢？
其实是不存在的，我们没有插入ES，但是es恰好在终止节点，所以多存储了一些不存在的数据。所以这样优化还是不够需要进一步看下面的结构。
2.3 有限状态转换机（FST）
FST最重要的功能是可以实现Key到Value的映射，相当于HashMap。FST的查
询速度⽐HashMap要慢⼀点但FST的内存消耗要⽐HashMap少很多。FST在
Lucene中被⼤量使⽤，例如：倒排索引的存储，同义词词典的存储，搜索关键
字建议等
比如我们有下面这几个数据：
后面这个数字一般是由机器算出来的，这个值是来解决上面的问题，也就是来校准是否真的存在例如es这种例子。
jksj/10
jksjtech/5
jkb/2

当我们插入jksj的时候 j:10 后面的字母都为0就可以 也可以k:10其它数字都为0
但是我们插入jksjtech 这个时候j前面的权重和必须要小于等于5，不然jksjtech 不可能为5 所以这个时候可以j:5 然后把另外的5放到output也里面去,也就是在终止节点开外挂。当然前面值可以任意分配只要不超过5 比如j:3 k:2 s: 0 :j + 外挂值 如果为终止节点则会加外挂这样就满足了我们的需要。
jkb/2 后面插入jkb的时候同样的原理会从新分配路径上的值。

2.4 ES的存储逻辑
frontier[]
⽤来存放UnCompiledNode，即待处理的节点(未持久化的节点)
current[]
存放CompiledNode，即最终的节点，存储(持久化以后的节点）

ARC {label 值,output 节点字面信息, target(包含一个flag 下一个节点的头补信息 && 下一个节点的label) 指向的节点}。

abd
abe
abfi
abfj
abfk
abgl
abgm
abgn
abgo
abgp
abgq
abgr
abh
ac
这个是字典序排好以后进行插入，来理解FST的过程：
首先插入abd， 然后插入abe代表d结尾的Node结束了可以进行落盘，按照这个逻辑只要后面与这个节点无关了就可以进行落盘，然后如果达到了每个block的最大数量最后就会进行分裂，整个过程就是不停的落盘生成子文件，子文件进行分裂，形成了上面这张图的文件结构。其中有一些术语，pending block是等待落盘的，floor block是已经落盘的。pending trem是一个单独的也就是没有其它字符共享block。
term index的存储

图片来源：图片来源地址

参考资料 极客时间ES