希望长大对我而言,是可以做更多想做的事,而不是被迫做更多不想做的事...... 首页 Elasticsearch倒排索引比mysql快 丁D 学无止境 2019-12-13 10:30 60677已阅读 Elasticsearch 倒排索引 摘要本文将介绍倒排索引为什么比mysql的索引快的原理。 ### 正排索引 一个文档中,有什么单词。是以文档作为维度。 ![](/upload/855959-20170706154309815-1724421988.png) ### 倒排索引 这个单词在哪些文档中。以单词作为维度。 ![](/upload/855959-20170706154505378-610589524.png) es使用的是倒排索引 ### 倒排索引是怎么构成的 如下图所示倒排索引由 term index 、term dictionary、posting list组成 ![](/upload/20180715124329682.png) 我们下面来看一个例子 数据如图所示 有3个文档 ![](/upload/20180715121642442.png) 倒排索引的矩阵 ![](/upload/20180715121729443.png) 18,20,男,女这种分词后的单词就做term。 【1,3】,【2】,【1,2】,【3】,这个是文档的id叫做posting list 那什么是term index,或者是term dictionary呢? 假设我们有这么一句话:`This guy is great. `分词后可能变成(不考虑去掉停用词等) ``` this、 guy 、is 、great ``` 如果我们就这个去查询可能要扫描所有的term,如果我们排序一下变成 ``` guy、 great、 is、 this ``` 这样的话我们就能使用二分法去查询快速找到单词了,这个就是 **term dictionary** 有了term dictionary,可以用logN次磁盘查找得到目标。但是磁盘的随机读操作仍然是非常昂贵的(一次random access大概需要10ms的时间)。所以尽量少的读磁盘,有必要把一些数据缓存到内存里。但是整个term dictionary本身又太大了,无法完整地放到内存里。于是就有了**term index**。term index有点像一本字典的大的章节表。比如:A开头的term ……… Xxx页;C开头的term ……… Xxx页;E开头的term ………Xxx页。 term index不会包含所有的term,它包含的是term的一些前缀。通过term index可以快速地定位到term dictionary的某个offset,然后从这个位置再往后顺序查找。是以树的形式存在内存中的。 ![](/upload/20180715122024111.png) 到这里我们就可以解释为什么es比mysql块了。因为mysql只有term dictionary这一层,以树的形式存储在磁盘中,检索一个term需要若干次的random access的磁盘操作。而Lucene在term dictionary的基础上添加了term index来加速检索,term index以树的形式缓存在内存中。从term index查到对应的term dictionary的block位置之后,再去磁盘上找term,大大减少了磁盘的random access次数。 >PS: term index在内存中是以FST(finite state transducers)的形式保存的,其特点是非常节省内存。Term dictionary在磁盘上是以分block的方式保存的,一个block内部利用公共前缀压缩,比如都是Ab开头的单词就可以把Ab省去。这样term dictionary可以比b-tree更节约磁盘空间。 很赞哦! (2) 上一篇:k8s滚动升级和扩缩容 下一篇:MySQL优化看这篇就对了 目录 点击排行 Elasticsearch6.3.2之x-pack redis哨兵 2019-07-09 22:05 Redis+Twemproxy+HAProxy+Keepalived 2019-07-12 17:20 GC优化策略和相关实践案例 2019-10-10 10:54 JVM垃圾回收器 2019-10-10 10:23 标签云 Java Spring MVC Mybatis Ansible Elasticsearch Redis Hive Docker Kubernetes RocketMQ Jenkins Nginx 友情链接 郑晓博客 佛布朗斯基 凉风有信 南实博客 Rui | 丁D Java研发工程师 生活可以用「没办法」三个字概括。但别人的没办法是「腿长,没办法」、「长得好看,没办法」、「有才华,没办法」。而你的没办法,是真的没办法。 请作者喝咖啡