ElasticSearch倒排索引-构建千亿级日志分析系统
1.什么是倒排索引
Elasticsearch 使用一种称为 倒排索引 的结构，它适用于快速的全文搜索。一个倒排索引由文档中所有不重复词的列表构成，对于其中每个词，有一个包含它的文档列表。
正排索引：通过文档查找KEY，优点：易维护，每新增一个doc只需要把每个key在该doc中出现的次数和位置进行维护即可；缺点：搜索耗时太长
倒排索引：通过KEY来查找doc，用户在搜索引擎搜索框输入查询词进行搜索时，搜索引擎会对查询词进行切词以及近义词匹配等操作，根据原始查询词得到一系列的单词列表。然后根据搜索引擎内部的字典来查询每个单词对应的倒排列表，从而定位到包含这个单词的网页或者说是文档。最后搜索引擎根据特定的网页排序算法将查询到的网页进行排序，通过前端将搜索结果展示给用户
优点：搜索效率高；
缺点：维护成本高，每新增一个doc，需要维护整key——doc矩阵
搜索引擎要面临海量的数据搜索，尽量将大运算量的工作在创建索引时完成，使检索时间尽量的少，将搜索做到极致，而传统关系型数据的功能大而全，针对的业务场景不一样。
倒排列表用来记录有哪些文档包含了某个单词。一般在文档集合里会有很多文档包含某个单词，每个文档会记录文档编号（DocID），单词在这个文档中出现的次数（TF）及单词在文档中哪些位置出现过等信息，这样与一个文档相关的信息被称做倒排索引项（Posting），包含这个单词的一系列倒排索引项形成了列表结构，这就是某个单词对应的倒排列表。下图是倒排列表的示意图，在文档集合中出现过的所有单词及其对应的倒排列表组成了倒排索引。
在实际的搜索引擎系统中，并不存储倒排索引项中的实际文档编号，而是代之以文档编号差值（D-Gap）。
文档编号差值是倒排列表中相邻的两个倒排索引项文档编号的差值，一般在索引构建过程中，可以保证倒排列表中后面出现的文档编号大于之前出现的文档编号，所以文档编号差值总是大于0的整数。如图2所示的例子中，原始的 3个文档编号分别是187、196和199，通过编号差值计算，在实际存储的时候就转化成了：187、9、3。
之所以要对文档编号进行差值计算，主要原因是为了更好地对数据进行压缩，原始文档编号一般都是大数值，通过差值计算，就有效地将大数值转换为了小数值，而这有助于增加数据的压缩率。
假设我们有两个文档，每个文档的 content 域包含如下内容：
The quick brown fox jumped over the lazy dog
Quick brown foxes leap over lazy dogs in summer
为了创建倒排索引，我们首先将每个文档的 content 域拆分成单独的 词（我们称它为 词条 或 tokens ），创建一个包含所有不重复词条的排序列表，然后列出每个词条出现在哪个文档。结果如下所示：
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
两个文档都匹配，但是第一个文档比第二个匹配度更高。如果我们使用仅计算匹配词条数量的简单 相似性算法 ，那么，我们可以说，对于我们查询的相关性来讲，第一个文档比第二个文档更佳。
参考链接：https://www.elastic.co/guide/cn/elasticsearch/guide/current/inverted-index.html
讲到这里我们需要介绍分词器
2.倒排索引和传统数据库的索引
B+树是在平衡二叉树上的一种改进，尽量减少重平衡，叶子节点存储了所有数据满足了遍历查询。
传统数据的索引一般使用B+树，例如MySQL。
关系型数据库之所以使用B+树有以下几个方面的原因：
1) 关系型数据库一般有关联查询，多表的关联查询，和搜索引擎的全集查询场景不一样，关联查询需要对查询关键字进行比较；
2) 对插入比较多的场景使用B+树比平衡二叉树代价更小；
3) 关系型数据库经常进行排序、分页，B+数的链表结构使得分页和排序的代价较小，搜索引擎的分页则不然，下文会单独讲原因；
4) 关系型数据的数据结构通常比较规范，例如长度、类型有约束，而搜索引擎的内容长度不固定；
3、注意不要深度分页
在分布式系统中深度分页
理解为什么深度分页是有问题的，我们可以假设在一个有 5 个主分片的索引中搜索。 当我们请求结果的第一页（结果从 1 到 10 ），每一个分片产生前 10 的结果，并且返回给 协调节点 ，协调节点对 50 个结果排序得到全部结果的前 10 个。
现在假设我们请求第 1000 页—结果从 10001 到 10010 。所有都以相同的方式工作除了每个分片不得不产生前10010个结果以外。 然后协调节点对全部 50050 个结果排序最后丢弃掉这些结果中的 50040 个结果。
可以看到，在分布式系统中，对结果排序的成本随分页的深度成指数上升。这就是 web 搜索引擎对任何查询都不要返回超过 1000 个结果的原因。
实际应用中我们也对Nosql数据库进行过分表，例如对MongoDB进行分表存储和查询，为解决搜索深度带来的问题我们一般设定查询条件必须带时间，而分表的规则基于时间。
由于ElasticSearch的分布式存储是基于Hash的，因此，无法在有序的范围内进行分页。
https://www.elastic.co/guide/cn/elasticsearch/guide/current/pagination.html