网站建设人文类,杭州公司网站制作维护,云南建设厅网站公示,十堰专业网站建设倒排索引
idproductdesc1新版 小米 至尊-纪念版手机1小米 NFC 手机3NFC手机4小米 耳机5华为 耳机6扫地机器人7华为 Mata………………term_indexterm dictionaryposting list------------------------------------小米1……100W华为6,7,9NFC76,90耳机5352红米643,98机器人645,9…倒排索引
idproductdesc1新版 小米 至尊-纪念版手机1小米 NFC 手机3NFC手机4小米 耳机5华为 耳机6扫地机器人7华为 Mata………………term_indexterm dictionaryposting list------------------------------------小米1……100W华为6,7,9NFC76,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
