Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >MySQL和Lucene(Elasticsearch)索引对比分析

MySQL和Lucene(Elasticsearch)索引对比分析

作者头像
王知无-import_bigdata
发布于 2020-12-18 09:49:19
发布于 2020-12-18 09:49:19
1.3K0
举报

前言

相比于大多数人熟悉的 MySQL 数据库的索引,Elasticsearch 的索引机制是完全不同于 MySQL 的 B+Tree 结构。索引会被压缩放入内存用于加速搜索过程,这一点在效率上是完爆 MySQL 数据库的。但是 Elasticsearch 会对全部 text 字段进行索引,必然会消耗巨大的内存,为此 Elasticsearch 针对索引进行了深度的优化。在保证执行效率的同时,尽量缩减内存空间的占用。这篇文章就深度解析了 Elasticsearch 索引原理,揭开搜索的神秘面纱。

MySQL索引实现

在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。

MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图:

图1是一个MyISAM表的主索引(Primary key)示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。B+Tree的所有叶子节点包含所有关键字且是按照升序排列的。

MyISAM表的索引和数据是分离的,索引保存在”表名.MYI”文件内,而数据保存在“表名.MYD”文件内。

MyISAM的索引方式也叫做“非聚集”的,之所以这么称呼是为了与InnoDB的聚集索引区分。

InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同。

第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道,MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。

图2是InnoDB主索引(同时也是数据文件)的示意图,可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整形。

第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说,InnoDB的所有辅助索引都引用主键作为data域。例如,图3为定义在Col3上的一个辅助索引:

这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助,例如知道了InnoDB的索引实现后,就很容易明白为什么不建议使用过长的字段作为主键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。再例如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB数据文件本身是一颗B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择。

Lucene索引实现

Lucene的索引不是B+Tree组织的,而是倒排索引,Lucene的倒排索引由Term index,Team Dictionary和Posting List组成。

有倒排索引(invertedindex)就有正排索引(forwardindex),正排索引就是文档(Document)和它的字段Fields正向对应的关系:

DocID

name

sex

age

1

jack

18

2

lucy

17

3

peter

17

倒排索引是字段Field和拥有这个Field的文档对应的关系:

Sex字段:

[1,3]

[2]

Age字段:

18

[1]

17

[2,3]

Jack,lucy或者17,18这些叫做term,而[1,3]就是posting list。Posting list就是一个int型的数组,存储了所有符合某个term的文档id。那么什么是Term index和Term dictionary?

如上,假设name字段有很多个term,比如:Carla,Sara,Elin,Ada,Patty,Kate,Selena

如果按照这样的顺序排列,找出某个特定的term一定很慢,因为term没有排序,需要全部过滤一遍才能找出特定的term。排序之后就变成了:Ada,Carla,Elin,Kate,Patty,Sara,Selena

这样就可以用二分查找的方式,比全遍历更快地找出目标的term。如何组织这些term的方式就是 Term dictionary,意思就是term的字典。有了Term dictionary之后,就可以用比较少的比较次数和磁盘读次数查找目标。但是磁盘的随机读操作仍然是非常昂贵的,所以尽量少的读磁盘,有必要把一些数据缓存到内存里。但是整个Term dictionary本身又太大了,无法完整地放到内存里。于是就有了Term index。Term index有点像一本字典的大的章节表。比如:

A开头的term ……………. Xxx页

C开头的term ……………. Xxx页

E开头的term ……………. Xxx页

如果所有的term都是英文字符的话,可能这个term index就真的是26个英文字符表构成的了。但是实际的情况是,term未必都是英文字符,term可以是任意的byte数组。而且26个英文字符也未必是每一个字符都有均等的term,比如x字符开头的term可能一个都没有,而s开头的term又特别多。实际的term index是一棵trie 树:

上图例子是一个包含 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的trie树。这棵树不会包含所有的term,它包含的是term的一些前缀。通过term index可以快速地定位到term dictionary的某个offset,然后从这个位置再往后顺序查找。再加上一些压缩技术(想了解更多,搜索 Lucene Finite State Transducers),Term index的尺寸可以只有所有term的尺寸的几十分之一,使得用内存缓存整个term index变成可能。整体上来说就是这样的效果:

由Term index到Term Dictionary,再到Posting List,通过某个字段的关键字去查询结果的过程就比较清楚了,通过多个关键字的Posting List进行AND或者OR进行交集或者并集的查询也简单了。

对比MySQL的B+Tree索引原理,可以发现:

1)Lucene的Term index和Term Dictionary其实对应的就是MySQL的B+Tree的功能,为关键字key提供索引。Lucene的inverted index可以比MySQL的b-tree检索更快。

2)Term index在内存中是以FST(finite state transducers)的形式保存的,其特点是非常节省内存。所以Lucene搜索一个关键字key的速度是非常快的,而MySQL的B+Tree需要读磁盘比较。

3)Term dictionary在磁盘上是以分block的方式保存的,一个block内部利用公共前缀压缩,比如都是Ab开头的单词就可以把Ab省去。这样Term dictionary可以比B-tree更节约磁盘空间。

4)Lucene对不同的数据类型采用了不同的索引方式,上面分析是针对field为字符串的,比如针对int,有TrieIntField类型,针对经纬度,就可以用GeoHash编码。

5)在 Mysql中给两个字段独立建立的索引无法联合起来使用,必须对联合查询的场景建立复合索引,而Lucene可以任何AND或者OR组合使用索引进行检索。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-12-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 大数据技术与架构 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
技术译文 | MySQL 8 需要多大的 innodb_buffer_pool_instances 值(下)
本文来源:https://www.percona.com/blog/2020/08/13/how-many-innodb_buffer_pool_instances-do-you-need-in-mysql-8/
爱可生开源社区
2020/08/21
2.3K0
技术译文 | MySQL 8 需要多大的 innodb_buffer_pool_instances 值(下)
二进制日志和文件系统是如何影响MySQL的性能的(译自Percona)
https://www.percona.com/blog/how-binary-logs-and-filesystems-affect-mysql-performance/
姚远OracleACE
2023/04/06
6630
二进制日志和文件系统是如何影响MySQL的性能的(译自Percona)
Percona Server 5.7 有哪些性能提升?
从Percona Server 5.6发布以来,我们引入了几个重要的更新,有助于高并发I/O负载场景下的性能瓶颈定位。我们(在性能方面的)某些研究和提升在目前最好的MySQL版本5.7下被重新实现了。但即使MySQL 5.7在扩展性和性能等方面都有所提升,我们还是发现了可以增进I/O工作负载性能的一些地方。
阿炳数记
2019/02/27
4600
Percona Server 5.7 有哪些性能提升?
【译】MySQL挑战:建立10万连接
本文的目的是探索一种在一台MySQL服务器上建立10w个连接的方法。我们要建立的是可以执行查询的连接,而不是10w个空闲连接。
猿哥
2019/03/19
1.1K0
MySQL 性能:使用 MySQL 5.7 实现每秒 50 万查询
使用UNIX socket来运行Point-Selects测试的Sysbench命令如下(在parallel中启动8个进程):
zhangdd
2018/08/01
7420
优化Mysql:3个简单的调整
前言 调整下面3项参数配置可以起到很好的优化效果,简单实用。 1. 使用 InnoDB 存储引擎 如果你还在使用 MyISAM 存储引擎,强烈建议改为 InnoDB,InnoDB 的优越性有很多,举个简单的例子: MyISAM:只在内存中存放索引 InnoDB:在内存中存索引和数据 修改的方法: ALTER TABLE table_name ENGINE=InnoDB; 2. 让 InnoDB 使用全部内存 innodb_buffer_pool_size参数指定了 InnoDB 可以使用的内存总量。 建议设
dys
2018/04/04
8840
Percona Server 5.7有哪些性能提升?
In this blog post, we’ll be discussing Percona Server 5.7 performance improvements.
阿炳数记
2019/04/24
7050
Percona Server 5.7有哪些性能提升?
MySQL性能基准测试对比:MySQL 5.7与MySQL 8.0
版权声明:本文由腾讯云数据库产品团队整理,页面原始内容来自于db weekly英文官网,若转载请注明出处。翻译目的在于传递更多全球最新数据库领域相关信息,并不意味着腾讯云数据库产品团队赞同其观点或证实其内容的真实性。如果其他媒体、网站或其他任何形式的法律实体和个人使用,必须经过著作权人合法书面授权并自负全部法律责任。不得擅自使用腾讯云数据库团队的名义进行转载,或盗用腾讯云数据库团队名义发布信息。
腾讯技术工程官方号
2019/03/05
7K0
MySQL性能基准测试对比:MySQL 5.7与MySQL 8.0
xfs vs ext4 性能压测对比
最近忙着给YOUZAN的数据库服务器升级系统版本,从centos6 升级到centos7。centos/redhat 7 默认将文件系统设置为xfs。咨询了很多DBA朋友,他们已经升级到7 并且使用xfs很久。于是我们也随大流打算使用xfs文件系统。
用户1278550
2019/07/10
47.3K1
xfs vs ext4 性能压测对比
技术译文 | How Can ScaleFlux Handle MySQL Workload?
本文是一篇译文,介绍 Percona 的工程师对 ScaleFlux 的性能压测报告。
爱可生开源社区
2020/08/21
5090
技术译文 | How Can ScaleFlux Handle MySQL Workload?
针对 MySQL/InnoDB 刷盘调优
这篇文章是讲述 InnoDB 刷盘策略系列文章的第三篇。本文主要讲述 性能调优。另外2篇文章参考
用户1278550
2022/07/30
2.1K0
MySQL 8.0 首个自适应参数横空出世
MySQL8.0推出一个号称可以自适应服务器的参数,保证在各种不同的服务器、虚拟机、容器下自动适配服务器资源,让我们一起来看看到底它能做到什么地步。
沃趣科技
2018/07/02
1K0
MySQL 8.0 首个自适应参数横空出世
来自MySQL顾问公司Percona的MySQL数据库优化建议
本文是Aurimas Mikalauskas在参加Zabbix2014年大会之后根据演讲内容整理而成。
Zabbix
2021/02/03
1.2K0
MySQL性能测试 : 新的InnoDB Double Write Buffer
新的MySQL8.0.20版本重新设计了InnoDB Double Write(DBLWR),确实是一个大的历史烦人的事情。为什么在过去这么痛苦,让我们付出了这么多精力,我无法更好地解释,因为从2018年开始,我已经在下面一篇关于MySQL基于IO负载的文章中说过了。这个故事并不完整,因为它缺少2019年的那一篇(稍后再讲),但是如果你(重新)读过上面的这篇文章提到的内容,您会更好理解接下来的内容。
田帅萌
2020/05/20
2.7K0
为 Zabbix 优化 MySQL
Zabbix 和 MySQL 在大型的 Zabbix 环境中,遇到的挑战大部分是 MySQL 以及更具体的说是 MySQL 磁盘 IO。 考虑到这一点,我将提出一些优化,这将有助于你的 MySQL 最好的使用磁盘(必然的将帮助你的 Zabbix 最好的利用 MySQL)和可用的硬件资源。 SSD 是一个转折 “MySQL 在 SSD 上是否会运行的更好?”我已经一次次的在公共场合或私人场合听到这个问题。 我可以毫不怀疑的告诉你,如果 IO 是你当前的瓶颈 - 要么因为一些查询花费了太多时间和直到查询完成(
小小科
2018/05/02
1.8K0
InnoDB Buffer Pool巧配置全解
InnoDB 维护了一个缓存数据和索引信息到内存的存储区叫做 Buffer Pool,它会将最近访问的数据缓存到缓冲区。我们通过配置各个 Buffer Pool 的参数,可以显著提高 MySQL 的性能。
阿炳数记
2019/02/27
2.4K0
技术译文 | MySQL 社区经理:MySQL 8.4 InnoDB 参数默认值为什么要这么改?
2024 年 4 月 30 日,MySQL 8.4(第一个 LTS 版)正式发布,也验证了 Oracle 官方在之前宣布的 MySQL 版本发布节奏。
爱可生开源社区
2024/05/11
3260
技术译文 | MySQL 社区经理:MySQL 8.4 InnoDB 参数默认值为什么要这么改?
认识InnoDB的Buffer Pool
对于innoDB存储引擎来说,数据是存储在磁盘上,而执行引擎想要操作数据,必须先将磁盘的数据加载到内存中才能操作。当数据从磁盘中取出后,缓存内存中,下次查询同样的数据的时候,直接从内存中读取,这样大大提高了查询性能。
小许code
2023/06/05
5310
认识InnoDB的Buffer Pool
MySQL 8.4: 突破创新,全新特性揭秘
MySQL最新发布的MySQL8.4LTS,"LTS" 代表 "Long-Term Support"(长期支持),是软件行业常用的术语之一。在软件开发中,LTS 版本是指那些经过特别维护并提供长期支持的版本。通常,LTS 版本会获得更长时间的更新和安全补丁支持,以确保它们能够在较长的时间内保持稳定和可靠。
DBA实战
2024/09/06
3580
MySQL 8.4: 突破创新,全新特性揭秘
多个buffer Pool实例 (3)—Buffer Pool(五十六)
前面说了lru链表,为了防止mysql的预读和全表查询刷新pool的频率太高,所以把lru链表分为young区域和old区域,但是频繁的移动lru链表也影响性能,所以当在young后半部1/4区域的时候,才会移动到最前面。初始数据从磁盘刷新到内存中,先是进入old区域,当超过1S之后继续访问,则会移动到young区域。预读分为两种,第一种是当mysql检测到执行语句按顺序查询超过一定值,则会吧下一个区的所有页全部都预先刷新到缓存页里,第二种就是13个页在同一个区,这时候会吧这个区的数据全部刷新到缓存页。
keying
2022/07/29
5150
相关推荐
技术译文 | MySQL 8 需要多大的 innodb_buffer_pool_instances 值(下)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档