赞
踩
例如,假设我们有两个文档,每个文档的 content
域包含如下内容:
为了创建倒排索引,首先我们需要借助分词器,将每个文档的 content
域拆分成单独的词(我们称它为 词条
或 tokens、term
),创建一个包含所有不重复词条的排序列表,然后列出每个词条出现在哪个文档。
Term Doc_1 Doc_2
-------------------------
Quick | | X
The | X |
brown | X | X
dog | X |
dogs | | X
fox | X |
foxes | | X
in | | X
jumped | X |
lazy | X | X
leap | | X
over | X | X
quick | X |
summer | | X
the | X |
------------------------
如果我们想搜索 quick brown
,我们只需要查找包含每个词条的文档:
Term Doc_1 Doc_2
-------------------------
brown | X | X
quick | X |
------------------------
Total | 2 | 1
这里我们匹配到了两个文档(为了节省空间,这里返回的只是文档ID,最后再通过文档id去查询到具体文档。)。对于搜索引擎来说,用户总希望能够先看到相关度更高的结果,因此实际使用时我们通过一些算法来进行权重计算,将查询的结果按照权重降序返回。
Elasticsearch为了能够快速的在倒排索引中找到某个term,他会按照字典序对所有的term进行排序,再通过二分查找来找到term,这就是Term Dictionary,但即使有了Term Dictionary,O(logN)的磁盘读写仍然是影响性能的一大问题。
B-Tree通过减少磁盘寻道次数来提高查询性能,Elasticsearch也是采用同样的思路,直接通过内存查找term,不读磁盘,但是如果term太多,term dictionary也会很大,放内存不现实,于是有了Term Index,从下图可以看出,Term Index其实就是一个Trie树(前缀树)
这棵树不会包含所有的term,它包含的是term的一些前缀。通过term index可以快速地定位到term dictionary的某个offset,然后从这个位置再往后顺序查找。
为什么Elasticsearch/Lucene检索比mysql快呢?
Mysql只有term dictionary这一层,是以b-tree排序的方式存储在磁盘上的。检索一个term需要若干次的random access的磁盘操作。而Lucene在term dictionary的基础上添加了term index来加速检索,term index以树的形式缓存在内存中。从term index查到对应的term dictionary的block位置之后,再去磁盘上找term,大大减少了磁盘的random access次数。
Doc values的存在是因为倒排索引只对某些操作是高效的。 倒排索引的优势在于查找包含某个项的文档,而对于从另外一个方向的相反操作并不高效,即:确定哪些项是否存在单个文档里,聚合需要这种次级的访问模式。
以排序来举例——虽然倒排索引的检索性能非常快,但是在字段值排序时却不是理想的结构。
转置
倒排索引。转置
结构经常被称作 列式存储
。它将所有单字段的值存储在单数据列中,这使得对其进行操作是十分高效的,例如排序、聚合等操作。
在Elasticsearch中,Doc Values就是一种列式存储结构,在索引时与倒排索引同时生成。也就是说Doc Values和倒排索引一样,基于 Segement生成并且是不可变的。同时Doc Values和倒排索引一样序列化到磁盘。
Doc Values常被应用到以下场景:
下面举一个例子,来讲讲它是如何运作的
假设存在以下倒排索引
Term Doc_1 Doc_2 Doc_3 ------------------------------------ brown | X | X | dog | X | | X dogs | | X | X ------------------------------------
- 1
- 2
- 3
- 4
- 5
- 6
那么其生成的DocValues如下(实际存储时不会存储doc_id,值所在的顺位即为doc_id)
Doc_id Values ------------------ Doc_1 | brown | Doc_1 | dog | Doc_2 | brown | Doc_2 | dogs | Doc_3 | dog | Doc_3 | dogs | ------------------
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
假设我们需要计算出brown出现的次数
GET /my_index/_search
{
"query":{
"match":{
"body":"brown"
}
},
"aggs":{
"popular_terms":{
"terms":{
"field":"body"
}
}
},
"size" : 0
}
下面来分析上述请求在ES中是如何来进行查询的:
但是doc_values仍存在一些问题,其不支持analyzed类型的字段,因为这些字段在进行文本分析时可能会被分词处理,从而导致doc_values将其存储为多行记录。但是在我们实际使用时,为什么仍然能对analyzed的字段进行聚合操作呢?这时就需要介绍一下Fielddata
doc values不生成分析的字符串,那为什么这些字段仍然可以使用聚合呢?是因为使用了fielddata的数据结构。与doc values不同,fielddata构建和管理100%在内存中,常驻于JVM内存堆。
从历史上看,fielddata 是所有字段的默认设置。但是Elasticsearch已迁移到doc values以减少 OOM 的几率。分析的字符串是仍然使用fielddata的最后一块阵地。 最终目标是建立一个序列化的数据结构类似于doc values ,可以处理高维度的分析字符串,逐步淘汰 fielddata。
它的一些特性如下
因此,在聚合字符串字段之前,请评估情况:
not_analyzed
字段吗?如果是,可以通过doc values节省内存 。analyzed
字段,它将使用fielddata并加载到内存中。这个字段因为N-grams有一个非常大的基数?如果是,这对于内存来说极度不友好。在Elasticsearch中,为了能够更方便的计算交集和并集,它要求倒排索引是有序的,而这个特点同时也带来了一个额外的好处,我们可以使用增量编码来压缩倒排索引,也就是FOR(Frame of Reference)编码
增量编码压缩,将大数变小数,按字节存储
FOR编码分为三个步骤
如下图所示,如果我们的倒排索引中存储的文档id为[73, 300, 302, 332, 343, 372]
,那么经过增量编码后的结果则为[73, 227, 2, 30, 11, 29]
。这种压缩的好处在哪里呢?我们通过增量将原本的大数变成了小数,使得所有的增量都在0~255之间,因此每一个值就只需要使用一个字节就可以存储,而不会使用int
或者bigint
,大大的节约了空间。
接着,第二步我们将这些增量分到不同的区块中(Lucene底层用了256个区块,下面为了方便展示之用了两个)。
第三步,我们计算出每组数据中最大的那个数所占用的bit位数,例如下图中区块1最大的为227,所以只占用8个bit位,所以三个数总共占用3 * 8bits
即3字节。而区块2最大为29,只占用5个bit位,因此这三个数总共占用3 * 5bits
即差不多2字节。通过这种方法,将原本6个整数从24字节压缩到了5字节,效果十分出色。
FOR编码对于倒排索引来说效果很好,但对于需要存储在内存中的过滤器缓存等不太合适,两者之间有很多不同之处:
基于以上的不同,对于缓存来说FOR编码并不适用,因此我们还需要考虑其他的一些选择。
为什么要使用4096作为数组和位图选取的阈值呢?
下面是官方给出的数据报告,在一个块中只有文档数量超过4096,位图的内存优势才会凸显出来
这就是Roaring Bitmaps高效率的原因,它基于两种完全不同的方案来进行编码,并根据内存效率来动态决定使用哪一种方案。
官方也给出了几种方案的性能测试
从上述对比可以看出,没有一种方法是完美的,但是以下两种方法的巨大劣势使得它们不会被选择
因此在综合考量下,Elasticsearch还是选择使用Roaring Bitmaps,并且在很多大家了解的开源大数据框架中,也都使用了这一结构,如Hive、Spark、Kylin、Druid等。
如果多个字段索引的联合查询,倒排索引如何满足快速查询的要求呢?
AND
操作。Elasticsearch支持以上两种的联合索引方式,如果查询的过滤器缓存到了内存中(以位图的形式),那么合并就是两个位图的AND
。如果查询的过滤器没有缓存,那么就用跳表的方式去遍历两个硬盘中的倒排索引。
假设有下面三个倒排索引需要联合索引:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。