1. 引言
elasticsearch 是一个分布式可扩展实时搜索和分析引擎，他在 Apache Lucence 搜索引擎的基础上增加了分布式实时文件存储，并且实现了非常强大的可扩展性，成为了企业级搜索引擎构建的首选。
作为一个优秀的分布式存储、搜索组件，了解 elasticsearch 的工作原理对于我们日常使用和技术提升都是非常有必要的。 本文，我们就抽丝剥茧，详细看看这个强大的分布式搜索引擎是如何工作的。
2. 文档
对于一个存储引擎，用来定位磁盘上实际数据的索引是十分重要的一部分，索引的数据结构直接决定了存储引擎的数据读写效率。 例如，mysql 通过多分支的 B 树索引，成功减少了磁盘 IO 次数，同时兼顾了范围查询等功能与写入性能，但因为 B 树作为多分支树，在其分支数量与高度的限制下，当数据库容量增长到一定程度，随之造成的磁盘 IO 次数增加仍然会造成性能的明显下降。 那么，作为海量数据搜索引擎的 elasticsearch 是通过什么样的索引数据结构来解决这个问题的呢？ elasticsearch 是面向文档型数据库，一条数据在 elasticsearch 中就是一个文档，通过 json 的格式来进行序列化存储，例如：
代码语言：javascript复制{
"name" : "John",
"sex" : "Male",
"age" : 25,
}每个文档都属于一个 type，由 type 定义了文档包含哪些字段，每个文档都有自己唯一的 docid。
3. 索引
elasticsearch 对于 type 中定义的每一个可能被检索的字段都各自建立了一套索引。
如图所示，elasticsearch 的索引共有三层：
- Term Index — 通过 FST 结构保存，类似于字典树结构，索引了文档中该字段的若干个公共前缀
- Term Dictionary — 存储了关键词的字典结构
- Posting List — 存储了关键词对应的 docid 列表
Term Index 通过树结构快速找到关键词前缀所在的下一级索引（Term Dictionary）中的偏移，再在第二级索引中定位到完整的关键词，最终在第三级索引中找到对应的 docid，大大降低了随机磁盘操作。 同时，FST 是一种十分节省内存的树结构，后面有时间博主再单独发文章来介绍这个数据结构。 而在 Term Dictionary 中，关键词通过公共前缀进行聚合和压缩，节省了公共的前缀重复存储的开销，也十分节省空间。
4. 多索引联合查询
如果进行多索引联合查询，mysql 会在优化环节找到最具选择性的索引，然后在遍历索引 B 树的同时在内存中进行计算和过滤。 而 Elasticsearch 的实现就相对复杂。
4.1. 跳跃表
事实上，Posting List 是一个跳跃表结构，关于跳跃表，之前我们在介绍 redis 相关的源码时已经有过介绍： redis zset 的实现，基于链表的二分查找 — 跳跃表源码解析
跳跃表是一个多层级链表的复合结构，在有序的基础上，通过跳过一定数目的节点实现数据检索过程中降低时间复杂度的目的。 在多索引联合查询中，第一步，对每个索引单独进行查询，找到对应的存储 docid 列表构成的跳跃表结构。 这样，经过第一步，若干个索引联合查询我们就获得了若干个跳跃表。 接下来，找到这些结果中，docid 最少的 posting list 开始从小到大遍历每一个 docid，并用这个 docid 在其他所有跳跃表中检索，最终，就可以获取多索引联合查询结果交集的 docid 列表了。
4.2. 利用 bitset 进行合并
上述通过跳跃表的查询每次仍然需要遍历最短结果的每一个 docid，是否有进一步提升性能的空间呢？ 答案是有的，Elasticsearch 通过 bitset 结构缓存实现了 O(1) 时间复杂度的合并。 假设一个关键词对应的 posting list 为 [1, 3, 4, 7, 10]，那么可以按二进制位建立一个 bitset：[1, 0, 1, 1, 0, 0, 1, 0, 0, 1] 多个 bitset 只需要进行按位与操作就可以得到最终的交集 bitset 了。 在 Elasticsearch 中，对于 4096 个 doc 以上的 posting list 才会通过 bitset 结构来实现，因为 4096 个 docid 以上 bitset 结构存储空间的优势会随着 docid 数量的增长而显著提升，可以参考官网的对比：https://www.elastic.co/cn/blog/frame-of-reference-and-roaring-bitmaps。
5. 性能提升 — 定时文档合并
elasticsearch 还会定期进行多文档合并，来实现查询性能的提升。 例如下面有三个 doc：
代码语言：javascript复制{timestamp:12:05:01, idc:sz, value:10}
{timestamp:12:05:01, idc:sz, value:12}
{timestamp:12:05:02, idc:sz, value:13}合并后就可以变成：
代码语言：javascript复制{
max_timestamp: 12:05:02, min_timestamp: 12:05:01, idc:sz,
records: [
{timestamp:12:05:01, idc:sz, value:10}
{timestamp:12:05:01, idc:sz, value:12}
{timestamp:12:05:02, idc:sz, value:13}
]
}这样，多个 doc 被放到了一个父 doc 中，既能够大幅压缩 posting list 的空间，也可以提升多索引联合查询时的效率。
6. 后记
本文详细介绍了 Elasticsearch 借以实现极高的查询性能的底层文档存储结构与索引结构。 那么，集群上多个 node。 之间是如何相互协同工作的呢？他们是如何实现数据的写入和读取的呢？敬请关注下一篇文章为您详细介绍。
7. 参考资料
https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps。 https://mp.weixin.qq.com/s?__biz=MjM5NzMyMjUwMg==&mid=2247486712&idx=1&sn=bec9e4d4812dbd6ad8a88a85957a6583&chksm=a6da869191ad0f878d5ce451566986c18251904776352f5de67d049b450be19859cc3de2ccba&scene=0&xtrack=1&key=abb696fd3dfcc4ba0e4048c987e2eeaa0502417a079a9d7cd6222361f91a08ad932ea3c48d2c0c0abc382ea601f58f33b922f4fdfd254afaca9033731e2e5faf5a8f82c8b42fcf76297618e3e7661082&ascene=1&uin=MTgzMTA0NjczNg==&devicetype=Windows 10&version=62060841&lang=zh_CN&pass_ticket=d2Riq5Y6OiNbqlOLu51WFB7hT5pgcW4vmDAHCasHnCBrbO9P392p77v1Draph8h+。 https://mp.weixin.qq.com/s?__biz=MjM5NzMyMjUwMg==&mid=2247485953&idx=1&sn=d41b001f99f11b7c774e597360301a17&chksm=a6da806891ad097e7b8449383c17601d7fccaaca75eda29b47ec1f230f3cfea32afa2693fd4f&mpshare=1&scene=24&srcid=&key=e4aa0eedbdf3808bc0bfacf1c68ad512e4f78c798de08497ee423214c6049239b1348b6e9e0b58ac680d68ff16a54030f3d1f097ca2c7ef097d4c4bd27dcd1118800b70cd80c9c729fc596cd6065efe2&ascene=14&uin=MTgzMTA0NjczNg==&devicetype=Windows 10&version=62060841&lang=zh_CN&pass_ticket=wLBntJ51sHw21rvBnkjr+puSr9M8WxePS16Njy7CoHajAEds4KnABh8kRweY+hq1。 https://www.cnblogs.com/dreamroute/p/8484457.html。 https://www.infoq.cn/article/database-timestamp-02/?utm_source=infoq&utm_medium=related_content_link&utm_campaign=relatedContent_articles_clk。
