我的编程空间,编程开发者的网络收藏夹
学习永远不晚

ElasticSearch索引 VS MySQL索引

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

ElasticSearch索引 VS MySQL索引

这段时间在维护产品的搜索功能,每次在管理台看到 elasticsearch 这么高效的查询效率我都很好奇他是如何做到的。

这甚至比在我本地使用 MySQL 通过主键的查询速度还快。

为此我搜索了相关资料:

这类问题网上很多答案,大概意思呢如下:

  •  ES 是基于 Lucene 的全文检索引擎,它会对数据进行分词后保存索引,擅长管理大量的索引数据,相对于 MySQL 来说不擅长经常更新数据及关联查询。

说的不是很透彻,没有解析相关的原理;不过既然反复提到了索引,那我们就从索引的角度来对比下两者的差异。

MySQL 索引

先从 MySQL 说起,索引这个词想必大家也是烂熟于心,通常存在于一些查询的场景,是典型的空间换时间的案例。

以下内容以 Innodb 引擎为例。

常见的数据结构

假设由我们自己来设计 MySQL 的索引,大概会有哪些选择呢?

散列表

首先我们应当想到的是散列表,这是一个非常常见且高效的查询、写入的数据结构,对应到 Java 中就是 HashMap

这个数据结构应该不需要过多介绍了,它的写入效率很高O(1),比如我们要查询 id=3 的数据时,需要将 3 进行哈希运算,然后再这个数组中找到对应的位置即可。

但如果我们想查询 1≤id≤6 这样的区间数据时,散列表就不能很好的满足了,由于它是无序的,所以得将所有数据遍历一遍才能知道哪些数据属于这个区间。

有序数组

有序数组的查询效率也很高,当我们要查询 id=4 的数据时,只需要通过二分查找也能高效定位到数据O(logn)。

同时由于数据也是有序的,所以自然也能支持区间查询;这么看来有序数组适合用做索引咯?

自然是不行,它有另一个重大问题;假设我们插入了 id=2.5 的数据,就得同时将后续的所有数据都移动一位,这个写入效率就会变得非常低。

平衡二叉树

既然有序数组的写入效率不高,那我们就来看看写入效率高的,很容易就能想到二叉树;这里我们以平衡二叉树为例:

由于平衡二叉树的特性:

左节点小于父节点、右节点大于父节点。

所以假设我们要查询 id=11 的数据,只需要查询 10—>12—>11 便能最终找到数据,时间复杂度为O(logn),同理写入数据时也为O(logn)。

但依然不能很好的支持区间范围查找,假设我们要查询5≤id≤20 的数据时,需要先查询10节点的左子树再查询10节点的右子树最终才能查询到所有数据。

导致这样的查询效率并不高。

跳表

跳表可能不像上边提到的散列表、有序数组、二叉树那样日常见的比较多,但其实 Redis 中的 sort set 就采用了跳表实现。

这里我们简单介绍下跳表实现的数据结构有何优势。

我们都知道即便是对一个有序链表进行查询效率也不高,由于它不能使用数组下标进行二分查找,所以时间复杂度是o(n)

但我们也可以巧妙的优化链表来变相的实现二分查找,如下图:

我们可以为最底层的数据提取出一级索引、二级索引,根据数据量的不同,我们可以提取出 N 级索引。

当我们查询时便可以利用这里的索引变相的实现了二分查找。

假设现在要查询 id=13 的数据,只需要遍历 1—>7—>10—>13 四个节点便可以查询到数据,当数越多时,效率提升会更明显。

同时区间查询也是支持,和刚才的查询单个节点类似,只需要查询到起始节点,然后依次往后遍历(链表有序)到目标节点便能将整个范围的数据查询出来。

同时由于我们在索引上不会存储真正的数据,只是存放一个指针,相对于最底层存放数据的链表来说占用的空间便可以忽略不计了。

平衡二叉树的优化

但其实 MySQL 中的 Innodb 并没有采用跳表,而是使用的一个叫做 B+ 树的数据结构。

这个数据结构不像是二叉树那样大学老师当做基础数据结构经常讲到,由于这类数据结构都是在实际工程中根据需求场景在基础数据结构中演化而来。

比如这里的 B+ 树就可以认为是由平衡二叉树演化而来。

刚才我们提到二叉树的区间查询效率不高,针对这一点便可进行优化:

在原有二叉树的基础上优化后:所有的非叶子都不存放数据,只是作为叶子节点的索引,数据全部都存放在叶子节点。

这样所有叶子节点的数据都是有序存放的,便能很好的支持区间查询。

只需要先通过查询到起始节点的位置,然后在叶子节点中依次往后遍历即可。

当数据量巨大时,很明显索引文件是不能存放于内存中,虽然速度很快但消耗的资源也不小;所以 MySQL 会将索引文件直接存放于磁盘中。

这点和后文提到 elasticsearch 的索引略有不同。

由于索引存放于磁盘中,所以我们要尽可能的减少与磁盘的 IO(磁盘 IO 的效率与内存不在一个数量级)

通过上图可以看出,我们要查询一条数据至少得进行 4 次IO,很明显这个 IO 次数是与树的高度密切相关的,树的高度越低 IO 次数就会越少,同时性能也会越好。

那怎样才能降低树的高度呢?

我们可以尝试把二叉树变为三叉树,这样树的高度就会下降很多,这样查询数据时的 IO 次数自然也会降低,同时查询效率也会提高许多。

这其实就是 B+ 树的由来。

使用索引的一些建议

其实通过上图对 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 倒排索引的思路做一个单机版的搜索引擎,只有自己写一遍才能加深理解。 

 

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

ElasticSearch索引 VS MySQL索引

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

ElasticSearch索引 VS MySQL索引

这段时间在维护产品的搜索功能,每次在管理台看到 elasticsearch 这么高效的查询效率我都很好奇他是如何做到的。

MySQL索引:B+树索引

MySQL索引:B+树索引B+树索引是传统意义上的索引,这是目前关系型数据库系统中查找最为常用和最为有效的索引。B+树索引的构造类似于二叉树,根据键值快速找到数据B树B+树是由B树演化而来的,在了解B+树之前,我们需要对B树有一点认知。B树全称Balance-
MySQL索引:B+树索引
2021-09-01

ElasticSearch之索引模板滚动索引实现详解

这篇文章主要为大家介绍了ElasticSearch之索引模板滚动索引实现详解,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪
2023-05-16

elasticsearch怎么创建索引

要创建一个索引,可以使用Elasticsearch提供的RESTful API或者Elasticsearch客户端库。使用RESTful API创建索引的步骤如下:1. 使用PUT请求来创建索引。例如,使用以下命令创建名为"my_index
2023-10-08

MySQL 索引

索引的概念不使用索引,要操作某些行时,需要遍历遍历整张表来找到匹配的行,很花时间,且有点耗资源。书:目录=>快速定位到指定章节,不用一页一页地找数据库:索引=>快速定位到指定记录,不用遍历数据表去找,索引相当于数据表的目录  索引的优缺点提高查询效率,尤其是记
MySQL  索引
2018-11-30

Mysql 索引

所谓聚簇索引,就是将索引和数据放到一起,找到索引也就找到了数据,B+树索引就是一种聚簇索引,而非聚簇索引就是将数据和索引分开,查找时需要先查找到索引,然后通过索引回表找到相应的数据。InnoDB有且只有一个聚簇索引,而MyISAM中都是非聚簇索引。 更多详细索
2018-06-24

MySQL索引

什么是索引?排好序快速查找的数据结构就是索引索引作用提高检索效率,降低数据库对IO成本;降低数据排序,减少cpu消耗索引类型单值索引:一个索引包含单个列,一个表可以有多个单值索引唯一索引:索引值必须唯一,但允许有空值复合索引:一个索引包含多个列基本语法创建索引
MySQL索引
2015-09-15

Mysql-索引

先创建表mysql> CREATE TABLE test( -> id INT, -> username VARCHAR(16), -> city VARCHAR(16), -> age INT -> );1.普通索引是最基本的索
Mysql-索引
2014-05-24

【Elasticsearch 7 探索之路】(三)倒排索引

上一篇,我们介绍了 ES 文档的基本 CURE 和批量操作。我们都知道倒排索引是搜索引擎非常重要的一种数据结构,什么是倒排索引,倒排索引的原理是什么。1 索引过程在讲解倒排索引前,我们先了解索引创建,下图是 Elasticsearch 中数据索引过程的流程。从
【Elasticsearch 7 探索之路】(三)倒排索引
2019-11-04

[MySQL]MySQL索引

[MySQL]MySQL索引 文章目录 [MySQL]MySQL索引1. 索引的概念2. 认识磁盘磁盘的内部结构磁盘中的一个盘片结构定位扇区磁盘随机访问与连续访问 3. MySQL与磁盘交互的基本单位4. 建立共识5. 索引的
2023-08-17

mysql中聚集索引、辅助索引、覆盖索引、联合索引怎么用

这篇文章主要介绍了mysql中聚集索引、辅助索引、覆盖索引、联合索引怎么用,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。聚集索引(Clustered Index)聚集索引就是
2023-06-29

MySQL 聚集索引和二级索引

Clustered and Secondary Indexes(聚集索引和二级索引)Every InnoDB table has a special index called the clustered index where the data for the
MySQL 聚集索引和二级索引
2022-03-11

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录