Elasticsearch中的倒排索引结构是什么
发布时间：2021-06-26 14:23:46
来源：亿速云
阅读：681
作者：chen
栏目： 大数据
本篇内容主要讲解“Elasticsearch中的倒排索引结构是什么”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“Elasticsearch中的倒排索引结构是什么”吧!
倒排索引（Inverted Index）也叫反向索引，有反向索引必有正向索引。通俗地来讲，正向索引是通过key找value，反向索引则是通过value找key。
先来回忆一下我们是怎么插入一条索引记录的：
curl -X PUT "localhost:9200/user/_doc/1" -H 'Content-Type: application/json' -d'
{
"name" : "Jack",
"gender" : 1,
"age" : 20
}
'其实就是直接PUT一个JSON的对象，这个对象有多个字段，在插入这些数据到索引的同时，Elasticsearch还为这些字段建立索引——倒排索引，因为Elasticsearch最核心功能是搜索。
那么，倒排索引是个什么样子呢？
倒排索引由两部分构成：
它的结构如下：
单词词典有两种数据结构实现：B+树和Hash表
B+树和 Mysql索引结构中主键索引数据结构一样，这里就不再介绍了
哈希表的key是单词的hash值，值是单词的链表，因为hash算法会有冲突的情况发生，所以这里的值是一个集合，里面保存着相同hash值得单词以及改词指向倒排列表的指针
倒排列表
倒排列表特性：
记录出现过某个单词的文档列表
同时还记录单词在所有文档中的出现次数和偏移位置
倒排列表元素数据结构：
(DocID;TF;<POS>)
其中：
举例
有下面单个文档
| - | 内容 |
|---|
| 文档1 | 百度的年度目标 |
| 文档2 | AI技术生态部的年度目标 |
| 文档3 | AI市场的年度目标 |
则他们生成的倒排索引
| 单词ID | 单词 | 逆向文档频率 | 倒排列表(DocID;TF;<POS>) |
|---|
| 1 | 目标 | 3 | (1;1;<3>),(2;1;<5>),(3;1;<4>) |
| 2 | 年度 | 3 | (1;1;<2>),(2;1;<4>),(3;1;<3>) |
| 3 | AI | 2 | (2;1;<1>),(3;1;<1>) |
| 4 | 技术 | 1 | (2;1;<2>) |
| 5 | 生态 | 1 | (2;1;<3>) |
| 6 | 市场 | 1 | (3;1;<2>) |
比如单词“年度”，单词ID为2，在三个文档中出现过，所以逆向文档频率为3，同时倒排索引中的元素也有三个：(1;1;<2>),(2;1;<4>),(3;1;<3>)。拿第一个元素(1;1;<2>)进行说明，他表示“年度”再文档ID为1的文档中出现过1次，出现的位置是第二个单词
首先，来搞清楚几个概念，为此，举个例子：
假设有个user索引，它有四个字段：分别是name，gender，age，address。画出来的话，大概是下面这个样子，跟 关系型数据库一样
Term（单词）：一段文本经过分析器分析以后就会输出一串单词，这一个一个的就叫做Term（直译为：单词）
Term Dictionary（单词字典）：顾名思义，它里面维护的是Term，可以理解为Term的集合
Term Index（单词索引）：为了更快的找到某个单词，我们为单词建立索引
Posting List（倒排列表）：倒排列表记录了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息，每条记录称为一个倒排项(Posting)。根据倒排列表，即可获知哪些文档包含某个单词。（PS：实际的倒排列表中并不只是存了文档ID这么简单，还有一些其它的信息，比如：词频（Term出现的次数）、偏移量（offset）等，可以想象成是Java中的对象）
（PS：如果类比现代汉语词典的话，那么Term就相当于词语，Term Dictionary相当于汉语词典本身，Term Index相当于词典的目录索引）
我们知道，每个文档都有一个ID，如果插入的时候没有指定的话，Elasticsearch会自动生成一个，因此ID字段就不多说了
上面的例子，Elasticsearch建立的索引大致如下：
name字段：
gender字段：
Elasticsearch分别为每个字段都建立了一个倒排索引。比如，在上面“张三”、“北京市”、22 这些都是Term，而[1，3]就是Posting List。Posting list就是一个数组，存储了所有符合某个Term的文档ID。
只要知道文档ID，就能快速找到文档。可是，要怎样通过我们给定的关键词快速找到这个Term呢？
当然是建索引了，为Terms建立索引，最好的就是B-Tree索引（PS：MySQL就是B树索引最好的例子）。
首先，让我们来回忆一下MyISAM存储引擎中的索引是什么样的：
我们查找Term的过程跟在MyISAM中记录ID的过程大致是一样的
MyISAM中，索引和数据是分开，通过索引可以找到记录的地址，进而可以找到这条记录
在倒排索引中，通过Term索引可以找到Term在Term Dictionary中的位置，进而找到Posting List，有了倒排列表就可以根据ID找到文档了
（PS：可以这样理解，类比MyISAM的话，Term Index相当于索引文件，Term Dictionary相当于数据文件）
（PS：其实，前面我们分了三步，我们可以把Term Index和Term Dictionary看成一步，就是找Term。因此，可以这样理解倒排索引：通过单词找到对应的倒排列表，根据倒排列表中的倒排项进而可以找到文档记录）
实际的 term index 是一棵 trie 树：
例子是一个包含 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的 trie 树。这棵树不会包含所有的 term，它包含的是 term 的一些前缀。通过 term index 可以快速地定位到 term dictionary 的某个 offset，然后从这个位置再往后顺序查找。再加上一些压缩技术（搜索 Lucene Finite State Transducers） term index 的尺寸可以只有所有 term 的尺寸的几十分之一，使得用内存缓存整个 term index 变成可能。整体上来说就是这样的效果。
以上是三个 posting list。我们现在需要把它们用 AND 的关系合并，得出 posting list 的交集。首先选择最短的 posting list，然后从小到大遍历。遍历的过程可以跳过一些元素，比如我们遍历到绿色的 13 的时候，就可以跳过蓝色的 3 了，因为 3 比 13 要小。
整个过程如下
Next -> 2
Advance(2) -> 13
Advance(13) -> 13
Already on 13
Advance(13) -> 13 MATCH!!!
Next -> 17
Advance(17) -> 22
Advance(22) -> 98
Advance(98) -> 98
Advance(98) -> 98 MATCH!!!
最后得出的交集是 [13,98]，所需的时间比完整遍历三个 posting list 要快得多。但是前提是每个 list 需要指出 Advance 这个操作，快速移动指向的位置。什么样的 list 可以这样 Advance 往前做蛙跳？skip list：
考虑到频繁出现的 term（所谓 low cardinality 的值），比如 gender 里的男或者女。如果有 1 百万个文档，那么性别为男的 posting list 里就会有 50 万个 int 值。用 Frame of Reference 编码进行压缩可以极大减少磁盘占用。这个优化对于减少索引尺寸有非常重要的意义。当然 mysql b-tree 里也有一个类似的 posting list 的东西，是未经过这样压缩的。
因为这个 Frame of Reference 的编码是有解压缩成本的。利用 skip list，除了跳过了遍历的成本，也跳过了解压缩这些压缩过的 block 的过程，从而节省了 cpu。
利用 bitset 合并
Bitset 是一种很直观的数据结构，对应 posting list 如：
[1,3,4,7,10]
对应的 bitset 就是：
[1,0,1,1,0,0,1,0,0,1]
每个文档按照文档 id 排序对应其中的一个 bit。Bitset 自身就有压缩的特点，其用一个 byte 就可以代表 8 个文档。所以 100 万个文档只需要 12.5 万个 byte。但是考虑到文档可能有数十亿之多，在内存里保存 bitset 仍然是很奢侈的事情。而且对于个每一个 filter 都要消耗一个 bitset，比如 age=18 缓存起来的话是一个 bitset，18<=age<25 是另外一个 filter 缓存起来也要一个 bitset。
所以秘诀就在于需要有一个数据结构：
Lucene 使用的这个数据结构叫做 Roaring Bitmap。
到此，相信大家对“Elasticsearch中的倒排索引结构是什么”有了更深的了解，不妨来实际操作一番吧！这里是亿速云网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
