Elasticsearch基本原理

蔚落 2022-05-10 08:08 256阅读 0赞

ES作为高度可伸缩的全文搜索与分析引擎，经常被用作大量数据的复杂搜索与分析业务。本博文以问题方式展示ES的基础特性，并简单介绍底层算法实现。

**1. ES搜索速度为什么会特别快？**

简单来说就是使用了使用了Lucene的倒排索引技术，首先以分词的形式将文档分解成单词+文章号【频率】+位置的形式，借用网上例子：

文章1的内容为：Tom lives in Guangzhou,I live in Guangzhou too.

文章2的内容为：He once lived in Shanghai.

生成倒排索引为：

关键词            文章号[出现频率]              出现位置 　　
    guangzhou           1[2]                      3，6 　　
    he                  2[1]                      1 　　
    i                   1[1]                      4 　　
    live                1[2]                      2，5, 
                        2[1]                      2 　　
    shanghai            2[1]                      3 　　
    tom                 1[1]                      1

可以看到倒排索引的关键在于将文章分解后，单词按照字母顺序排列，查找时可使用二分法查找关键字。实现时，lucene将上面三列分别作为词典文件（Term Dictionary）、频率文件(frequencies)、位置文件 (positions)保存。其中词典文件不仅保存有每个关键词，还保留了指向频率文件和位置文件的指针，通过指针可以找到该关键字的频率信息和位置信息。

term dictionary按照二分法查找，时间复杂度为logN，但是如果文档内容过大，打比方， 包含了所有英文字典的单词，这样，term dictionary存储到内存中是不可能的。因此，提出了term index的概念，它是一个trie树：

![70][]

百度百科解释：字典树，又叫单词查找树，是一种[树形结构][Link 1]，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的[字符][Link 2]串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

![70 1][]

这样我们可以看到，先通过Term Index前缀匹配，然后定位到Term Dictionary的开始位置，再通过顺序查找的方式定位具体关键词，这样拜托了很多无谓的词语查找。

** 2. 如何提升组合查询的查询效率？**

上面步骤我们可以很快定位单个词语出现的文档号及频率信息。如果按照两个单词（定义为term）查找，则会得到两个包含文档号的列表，官方称为Posting list，查询两个term出现则需要将两个Posting list做合并，为快速得到合并结果提供了两个数据结构：skip list和bitset。

首先看下skip list的查找原理：

**![70 2][]**

首先将排好序的posting list按照由短到长的顺序排好，合并顺序是从下到上，首先找到文章号2，因为第2列的第一个数是1小于2，则跳过1，比较13，发现不相等，则开始比较13；依次类推，这样合并比较次数会大大减少。

bitset的基本原理：

bitset就是将每一位代表一个数进行表示，存在该数则用1表示，不存在则用0表示，例如：【1,4,7,10】可以表示为：

1 0 0 1 0 0 1 0 0 1 （最左侧1 表示10存在）

单纯用位来表示是存在问题的，一个上千亿甚至更大的数表示可能需要G级别内存来表示，这样在内存中计算合并也不是很现实的，因此lucene提出了压缩算法，压缩后的数据结构称为：Roaring Bitmap。（有兴趣的同学可以研究下）

**3. ES的评分算法是什么样的？**

**   **  ES5.0版本之前采用的默认算法是TF/IDF算法，5.0版本之后评分算法改为BM25。首先看下TF/IDF算法：

![70 3][]

score(q,d)是针对document进行的一次评分查询，q--query，d--document；

Term frequency：匹配词个数/文档中总词个数，文档中匹配的单词个数越多，评分越高；

Inverse document frequency：文档总个数/匹配文档个数

Coord：协调因素，根据文档中包含term数量而定

Field boost：升压值

Length norm：查询term越长，协调因子越小

Query norm：一种基于查询的规范化因子，计算为每个查询项的平方权重之和

我们不必搞清楚真正的评分算法公式，只要大致知道一个文档中包含的匹配次数越多，则分数越高；同样，包含查询term文档总个数越少，数值越精确。

BM25算法：

![70 4][]

各参数含义：

N—document总数

Dft——包含term的document总数

K ——也表示为k1，它是饱和参数，控制项频率的增加在项频率饱和中产生的速度。k1的默认值是1.2。较低的值导致饱和度更快，较低的值导致饱和度更高

Avgdl——语料库中的平均文档长度(完整数据集)

两个算法的区别：

1.饱和度。有一个场景，一个文档中出现了1000个x和0个y，那TF/IDF算法会给出一个较高的分数，但是，BM25算法受饱和参数的影响，5个x和1个y的文档评分要远远高于1000个x和0个y的情况。

2.文档长度。举个例子，如果“旅行”一词在一篇包含1000个术语的文章中出现了一两次，那么这篇文章在多大程度上是关于旅行的，这篇文章几乎没有说明，但是在一条短推文中出现了两次，这意味着这篇文章在很大程度上是关于旅行的。TF-IDF执行一个有偏见的测量基于文档的得分计算长度,但是BM25使用文档的长度来弥补这一事实更长的文档通常有更多的单词,因此更有可能有更高的词频率却并不相关的术语。

参考文章：

[https://blog.csdn.net/u011635492/article/details/81023158][https_blog.csdn.net_u011635492_article_details_81023158]

[https://blog.csdn.net/u011239443/article/details/60604017][https_blog.csdn.net_u011239443_article_details_60604017]

参考书籍：《Mastring Elasticsearch 5.x third Edition》

[70]: /images/20220510/006f57d168764d20aebc47c32cb41cf3.png
[Link 1]: https://baike.baidu.com/item/%E6%A0%91%E5%BD%A2%E7%BB%93%E6%9E%84/9663807
[Link 2]: https://baike.baidu.com/item/%E5%AD%97%E7%AC%A6
[70 1]: /images/20220510/a16d8900f2914683a5619ba57c59b3a3.png
[70 2]: /images/20220510/75835971034445559f5cb0172028b547.png
[70 3]: /images/20220510/3505fd6443154611ad67e025b6df3e42.png
[70 4]: /images/20220510/6d5954b7c017498f88b50c34d3a05eef.png
[https_blog.csdn.net_u011635492_article_details_81023158]: https://blog.csdn.net/u011635492/article/details/81023158
[https_blog.csdn.net_u011239443_article_details_60604017]: https://blog.csdn.net/u011239443/article/details/60604017