ElasticSearch搜索引擎原理，都给你整理好了
“
最近接触的⼏个项⽬都使⽤到了 Elasticsearch (以下简称 ES ) 来存储数据和对数据进⾏搜索分析，就对 ES 进⾏了⼀些学习。本⽂整理⾃我⾃⼰的⼀次技术分享。
本⽂不会关注 ES ⾥⾯的分布式技术、相关 API 的使⽤，⽽是专注分享下“ES 如何快速检索”这个主题上⾯。这个也是我在学习之前对ES 最感兴趣的部分。
mysql操作官方文档
本⽂⼤致包括以下内容：
关于搜索：
传统关系型数据库和 ES 的差别
搜索引擎原理
细究倒排索引：
倒排索引具体是个什么样⼦的（posting list→term dic→term index）
关于 postings list 的⼀些巧技（FOR、Roaring Bitmaps）
如何快速做联合查询？
关于搜索
先设想⼀个关于搜索的场景，假设我们要搜索⼀⾸诗句内容中带“前”字的古诗。
⽤传统关系型数据库和 ES 实现会有什么差别？如果⽤像 MySQL 这样的 RDBMS 来存储古诗的话，我们应该会去使⽤这样的 SQL 去查询：
select name from poems where content like "%前%";
这种我们称为顺序扫描法，需要遍历所有的记录进⾏匹配。不但效率低，⽽且不符合我们搜索时的期望。
⽐如我们在搜索“ABCD"这样的关键词时，通常还希望看到"A"，"AB"，"CD"，“ABC”的搜索结果。于是乎就有了专业的搜索引擎，⽐如我们今天的主⾓ ES。
搜索引擎原理
搜索引擎的搜索原理简单概括的话可以分为这么⼏步：
内容爬取，停顿词过滤，⽐如⼀些⽆⽤的像"的"，“了”之类的语⽓词/连接词
内容分词，提取关键词
根据关键词建⽴倒排索引
⽤户输⼊关键词进⾏搜索
这⾥我们就引出了⼀个概念，也是我们今天的要剖析的重点倒排索引。也是 ES 的核⼼知识点。
如果你了解 ES 应该知道，ES 可以说是对 Lucene 的⼀个封装，⾥⾯关于倒排索引的实现就是通过 lucene 这个 jar 包提供的 API 实现的，所以下⾯讲的关于倒排索引的内容实际上都是 lucene ⾥⾯的内容。
倒排索引
⾸先我们还不能忘了我们之前提的搜索需求，先看下建⽴倒排索引之后，我们上述的查询需求会变成什么样⼦。
这样我们⼀输⼊“前”，借助倒排索引就可以直接定位到符合查询条件的古诗。
当然这只是⼀个很⼤⽩话的形式来描述倒排索引的简要⼯作原理。在 ES  中，这个倒排索引是具体是个什么样的，怎么存储的等等，这些才是倒排索引的精华内容。
①⼏个概念
在进⼊下⽂之前，先描述⼏个前置概念。
term：关键词这个东西是我⾃⼰的讲法，在 ES 中，关键词被称为 term。
postings list：还是⽤上⾯的例⼦，{静夜思，望庐⼭瀑布}是 "前" 这个 term 所对应列表。在 ES 中，这些被描述为所有包含特定 term ⽂档的 id 的集合。
由于整型数字 integer 可以被⾼效压缩的特质，integer 是最适合放在 postings list 作为⽂档的唯⼀标识的，ES 会对这些存⼊的⽂档进⾏处理，转化成⼀个唯⼀的整型 id。
再说下这个 id 的范围，在存储数据的时候，在每⼀个 shard ⾥⾯，ES 会将数据存⼊不同的 segment，这是⼀个⽐ shard 更⼩的分⽚单位，这些 segment 会定期合并。
在每⼀个 segment ⾥⾯都会保存最多 2^31 个⽂档，每个⽂档被分配⼀个唯⼀的 id，从 0 到 (2^31)-1。
相关的名词都是 ES 官⽅⽂档给的描述，后⾯参考材料中都可以到出处。
②索引内部结构
上⾯所描述的倒排索引，仅仅是⼀个很粗糙的模型。真的要在实际⽣产中使⽤，当然还差的很远。
在实际⽣产场景中，⽐如 ES 最常⽤的⽇志分析，⽇志内容进⾏分词之后，可以得到多少的 term？
那么如何快速的在海量 term 中查询到对应的 term 呢？遍历⼀遍显然是不现实的。
term dictionary：于是乎就有了 term dictionary，ES 为了能快速查到 term，将所有的 term 排了⼀个序，⼆分法查。
是不是感觉有点眼熟，这不就是 MySQL 的索引⽅式的，直接⽤ B+树建⽴索引词典指向被索引的数据。
term index：但是问题⼜来了，你觉得 Term Dictionary 应该放在哪⾥？肯定是放在内存⾥⾯吧？磁盘io 那么慢。就像 MySQL 索引就是存在内存⾥⾯了。
但是如果把整个 term dictionary 放在内存⾥⾯会有什么后果呢？内存爆了...
别忘了，ES 默认可是会对全部 text 字段进⾏索引，必然会消耗巨⼤的内存，为此 ES 针对索引进⾏了深度的优化。
在保证执⾏效率的同时，尽量缩减内存空间的占⽤。于是乎就有了 term index。
Term index：从数据结构上分类算是⼀个“Trie 树”，也就是我们常说的字典树。
这是⼀种专门处理字符串匹配的数据结构，⽤来解决在⼀组字符串集合中快速查某个字符串的问题。
这棵树不会包含所有的 term，它包含的是 term 的⼀些前缀（这也是字典树的使⽤场景，公共前缀）。
通过 term index 可以快速地定位到 term dictionary 的某个 offset，然后从这个位置再往后顺序查。就想右边这个图所表⽰的。
怎么样，像不像我们查英⽂字典，我们定位 S 开头的第⼀个单词，或者定位到 Sh 开头的第⼀个单词，然后再往后顺序查询？
lucene 在这⾥还做了两点优化，⼀是 term dictionary 在磁盘上⾯是分 block 保存的，⼀个 block 内部利⽤公共前缀压缩，⽐如都是 Ab 开头的单词就可以把 Ab 省去。
⼆是 term index 在内存中是以 FST（finite state transducers）的数据结构保存的。
FST 有两个优点：
空间占⽤⼩：通过对词典中单词前缀和后缀的重复利⽤，压缩了存储空间。
查询速度快：O(len(str)) 的查询时间复杂度。
FST 的理论⽐较复杂，本⽂不细讲，延伸阅读：
www.shenyanchao/blog/2018/12/04/lucene-fst/
OK，现在我们能得到 lucene 倒排索引⼤致是个什么样⼦的了。
关于 postings list 的⼀些巧技
在实际使⽤中，postings list 还需要解决⼏个痛点：
postings list 如果不进⾏压缩，会⾮常占⽤磁盘空间。
联合查询下，如何快速求交并集（intersections and unions）。
对于如何压缩，可能会有⼈觉得没有必要，”posting list 不是已经只存储⽂档 id 了吗？还需要压缩？”，但是如果在 posting list 有百万个 doc id 的情况，压缩就显得很有必要了。
⽐如按照朝代查询古诗，⾄于为啥需要求交并集，ES 是专门⽤来搜索的，肯定会有很多联合查询的需求吧 （AND、OR）。按照上⾯的思路，我们先将如何压缩。
①压缩
Frame of Reference：在 lucene 中，要求 postings lists 都要是有序的整形数组。
这样就带来了⼀个很好的好处，可以通过增量编码（delta-encode）这种⽅式进⾏压缩。
⽐如现在有 id 列表 [73, 300, 302, 332, 343, 372]，转化成每⼀个 id 相对于前⼀个 id 的增量值（第⼀
个 id 的前⼀个 id 默认是 0，增量就是它⾃⼰）列表是 [73, 227, 2, 30, 11, 29]。
在这个新的列表⾥⾯，所有的 id 都是⼩于 255 的，所以每个 id 只需要⼀个字节存储。
实际上 ES 会做的更加精细：
它会把所有的⽂档分成很多个 block，每个 block 正好包含 256 个⽂档，然后单独对每个⽂档进⾏增量编码。
计算出存储这个 block ⾥⾯所有⽂档最多需要多少位来保存每个 id，并且把这个位数作为头信息（header）放在每个 block 的前⾯。这个技术叫 Frame of Reference。
上图也是来⾃于 ES 官⽅博客中的⼀个⽰例（假设每个 block 只有 3 个⽂件⽽不是 256）。
FOR 的步骤可以总结为：
进过最后的位压缩之后，整型数组的类型从固定⼤⼩（8，16，32，64 位）4 种类型，扩展到了 [1-64] 位共 64 种类型。
通过以上的⽅式可以极⼤的节省 posting list 的空间消耗，提⾼查询性能。不过 ES 为了提⾼ filter 过滤器查询的性能，还做了更多的⼯作，那就是缓存。
Roaring Bitmaps (for filter cache)：在 ES 中，可以使⽤ filters 来优化查询，filter 查询只处理⽂档是

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。