MySQL索引 VS ElasticSearch索引
使用索引的一些倡议
其实通过上图对 B+树
的懂得,也能优化日常工作的一些小细节;比方为什么需要最好是有序递增的?
假设我们写入的主键数据是无序的,那么有大概后写入数据的 id 小于此前写入的,这样在保护 B+树
索引时便有大概需要移动已经写好数据。
假如是依照递增写入数据时则不会有这个思考,每次只需要顺次写入即可。
所以我们才会要求数据库主键尽量是趋势递增的,不思考分表的状况时最合理的就是自增主键。
团体来看思绪和跳表相似,只是针对使用处景做了相关的调整(比方数据全部储备于叶子节点)。
ES 索引
MySQL
聊完了,此刻来看看 Elasticsearch
是怎样来使用索引的。
正排索引
在 ES 中采纳的是一种名叫倒排索引
的数据构造;在正式讲倒排索引此前先来聊聊和他相反的正排索引
。
以上图为例,我们可以通过 doc_id
查询到详细对象的方式称为使用正排索引
,其实也能懂得为一种散列表。
本质是通过 key 来查寻 value。
比方通过 doc_id=4
便能很快查询到 name=jetty wang,age=20
这条数据。
倒排索引
那假如反过来我想查询 name
中包括了 li
的数据是什么?这样怎样高效查询呢?
仅仅通过上文提到的正排索引明显起不到什么作用,只能顺次将所有数据遍历后推断名称中可否包括 li
;这样效力十分低下。
但假如我们从新构建一个索引构造:
当要查询 name
中包括 li
的数据时,只需要通过这个索引构造查询到 Posting List
中所包括的数据,再通过映射的方式查询到终究的数据。
这个索引构造其实就是倒排索引
。
Term Dictionary
但怎样高效的在这个索引构造中查询到 li
呢,结合我们此前的经历,只要我们将 Term
有序摆列,便可以使用二叉树搜索树的数据构造在o(logn)
下查询到数据。
将一个文本拆分成一个一个独立Term
的历程其实就是我们常说的分词。
而将所有 Term
合并在一起就是一个 Term Dictionary
,也可以叫做单词词典。
- 英文的分词相对简便,只需要通过空格、标点符号将文本分隔便能拆词,中文则相对复杂,但也有很多开源工具做支撑(由于不是本文重点,对分词感乐趣的可以自行搜索)。
当我们的文本量宏大时,分词后的 Term
也会许多,这样一个倒排索引的数据构造假如存置于内存那必定是不足存的,但假如像 MySQL
那样存置于磁盘,效力也没那么高。
Term Index
所以我们可以选中一个折中的办法,既然没法将整个 Term Dictionary
放入内存中,那我们可认为Term Dictionary
创立一个索引然后放入内存中。
这样便可以高效的查询Term Dictionary
,最后再通过Term Dictionary
查询到 Posting List
。
相关于 MySQL
中的 B+树
来说也会减少了几次磁盘IO
。
这个 Term Index
我们可以使用这样的 Trie树
也就是我们常说的字典树
来存置。
更多关于字典树的内容请查看这里。
假如我们是以 j
开头的 Term
停止搜索,第一第一步就是通过在内存中的 Term Index
查询出以 j
打头的 Term
在 Term Dictionary
字典文件中的哪个位置(这个位置可以是一个文件指针,大概是一个区间范畴)。
紧接着在将这个位置区间中的所有 Term
取出,由于已经排好序,便可通过二分查寻快速定位到详细位置;这样便可查询出 Posting List
。
终究通过 Posting List
中的位置信息便可在原始文件中将目标数据检索出来。
更多优化
当然 ElasticSearch
还做了很多针对性的优化,当我们对两个字段停止检索时,就可以利用 bitmap
停止优化。
比方此刻需要查询 name=li and age=18
的数据,这时我们需要通过这两个字段将各自的结果 Posting List
取出。
最简便的办法是离别遍历两个汇合,取出反复的数据,但这个明显效力低下。
这时我们便可使用 bitmap
的方式停止储备(还节约储备空间),同时利用先天的位与
**运算便可得出结果。**
[1, 3, 5]
? 10101
[1, 2, 4, 5]
? 11011
这样两个二进制数组求与便可得出结果:
10001
? [1, 5]
终究反解出 Posting List
为[1, 5]
,这样的效力天然是要高上很多。
一样的查询需求在 MySQL
中并没有非凡优化,只是先将数据量小的数据挑选出来之后再挑选第二个字段,效力天然也就没有 ES
高。
当然在最新版的 ES
中也会对 Posting List
停止紧缩,详细紧缩规则可以查看官方文档,这里就不详细介绍了。
总结
最后我们来总结一下:
通过以上内容可以看出再复杂的产品终究都是根基数据构造组成,只是会对不一样利用场景针对性的优化,所以打好数据构造与算法的根基后再看某个新的技术或中心件时才能快速上手,乃至本人就能知道优化标的目的。
最后画个饼,后续我会尝试依照 ES
倒排索引的思绪做一个单机版的搜索引擎,只要本人写一遍才能加深懂得。
相关免费学习引荐:mysql数据库(视频)
以上就是MySQL索引 VS ElasticSearch索引的具体内容,更多请关注百分百源码网其它相关文章!