首页 技术PHP正文

Elasticsearch为什么搜索那么快?

薄洪涛 PHP 2019-05-21 617 0 Elasticsearch
介绍
Elasticsearch 是一个分布式可扩展的实时搜索和分析引擎,一个建立在全文搜索引擎 Apache Lucene(TM) 基础上的搜索引擎.当然 Elasticsearch 并不仅仅是 Lucene 那么简单,它不仅包括了全文搜索功能,还可以进行以下工作:
  • 分布式实时文件存储,并将每一个字段都编入索引,使其可以被搜索。

  • 实时分析的分布式搜索引擎。

  • 可以扩展到上百台服务器,处理PB级别的结构化或非结构化数据。

上次说过和传统数据库的比较
关系数据库     ⇒ 数据库 ⇒ 表    ⇒ 行    ⇒ 列(Columns) Elasticsearch  ⇒ 索引(Index)   ⇒ 类型(type)  ⇒ 文档(Docments)  ⇒ 字段(Fields)
一个 Elasticsearch 集群可以包含多个索引(数据库),也就是说其中包含了很多类型(表)。这些类型中包含了很多的文档(行),然后每个文档中又包含了很多的字段(列)。Elasticsearch的交互,可以使用Java API,也可以直接使用HTTP的Restful API方式

索引
一切设计都是为了提高搜索的性能
为了提高搜索的性能,难免会牺牲某些其他方面,插入,更新;没有哪一种数据库写入和读取都快的;只是在时间和空间的平衡点的挪动;search最核心功能是搜索
那es是如何做到快速搜索的呢?
我们先看下普通数据库mysql是如何处理索引的,mysql使用的是btree索引;
因为二叉树的查找效率是logN,同时增加新的索引的时候不必移动所有的节点,所以mysql采用b-tree 索引,能同时兼顾插入和查询的性能。因此在这个基础上,再结合磁盘的读取特性(顺序读/随机读),传统关系型数据库采用了B-Tree/B+Tree这样的数据结构:同时,树上的每个节点,都存储了多个值,缩短了磁盘寻道的时间(补充:每次寻到读取数据花费10ms以上)
ES库在设计上采用了倒排索引,如下图

e4632ac1392b01f7a39d963fddb1a1e0.png

我详细说一下何为倒序索引,举个例子:
docid
年龄
性别
1
18
2
20
3
18
我们有这么一张表(type),然后每一行(document)都有一个docid;那么给这张表建立的倒序索引如下,注意:每个字段都会建立索引
年龄
term(年龄)
Posting list(docid)
18
1,3
20
2
性别
term(性别)
Posting list(docid)
3
1,2
我们的索引字段叫term,对应的docid称为Posting list,Posting list其实是一个int类型的数组;
那搜索的时候,我们要查询年龄为18的,直接从年龄的索引表查就好了,直接得出1,3;我们把对字段的索引的term都放一起,叫term dictionary

clipboard.png


term_index
如果把term dictionary都放内存中,岂不美滋滋?
问题是,我们如果要应对的是亿万级别的数据,term dictionary放内存内存肯定是不够用的,所以我们再次引出一个概念;term_index;说到这里不太好理解,我打个比方,如果说亿万级别的数据相当于一本很厚的书,是不是要先有目录,咱们根据目录就可以查找到对应的章节,这个目录就相当于term dictionary,也就是索引,但是啊,书太厚,目录是不是也很厚(内存放不下term-posting list),目录厚了查找也不方便,所以我们有个目录的目录,就是term_index,比如我们要查第一部第二章第一节第一段在第几页,直接先看目录的目录(term_index),发现目录的目录说,你要查的第一部第二章第一节第一段在在目录的第3页(term dictionary的某个确定位置)可以找到对应的页数信息;然后我们就去翻目录,找到第一部第二章第一节第一段在128267页;
其实term_index也一样,就是对索引的索引,通过查到索引得出数据的信息;为了提升性能,term_index做了排序(如果不排序就扫描增高term_index),我们有很多个term,比如age,name,sex,hobby....,那么存在term_index中就是age,hobby,name,sex,按前缀排序的顺序,这样我们就可以使用二分查找,而不是全遍历!!
如果所有的 term 都是英文字符的话,可能这个 term index 就真的是 26 个英文字符表构成的了。但是实际的情况是,term 未必都是英文字符,term 可以是任意的 byte 数组。而且 26 个英文字符也未必是每一个字符都有均等的 term,比如 x 字符开头的 term 可能一个都没有,而 s 开头的 term 又特别多。实际的 term index 是一棵 trie 树:

e4632ac1392b01f7a39d963fddb1a1e0.png

比如我们要查询name在18-20岁的,我们要先去term_index查询n开头的,然后所有n开头的查找a开头的...依次类推,这里时间复杂度为logN,查询到name对应的term dictionary的位置,然后从这个位置去顺序查找,是不是快很多?看下图你就明白了

clipboard.png


说到这里我们就知道为什么es比mysql快了,因为mysql索引只有一层(term dictionary只有一层),而且是放磁盘上的,每次查询数据要多次读磁盘的索引文件确定出数据的位置;
es直接读内存,从term_index树中检索出,确定出要查数据的在索引文件的位置,不需要多次读磁盘上的索引文件!!

本文参考InfoQ大佬的文章,向大佬致敬!!

版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。

评论