深入理解MySQL的索引

作者 : 开心源码 本文共3479个字,预计阅读时间需要9分钟 发布时间: 2022-05-12 共133人阅读

(一)关于存储引擎?

? ? ? ?创立合适的索引是SQL性能调优中最重要的技术之一。在学习创立索引之前,要先理解MySql的架构细节,包括在硬盘上面如何组织的,索引和内存使用法和操作方式,以及存储引擎的差异如何影响到索引的选择。

? ? ? ?MySQL有很多种衍生版本,这些衍生版本支持更多不同种类的存储引擎。本文主要探讨三种MySQL引擎。

?MyISAM一种非事务性的存储引擎,是MySQL 5.5之前版本默认的存储引擎。

InnoDB ?最流行的事务性存储引擎,从5.5版开始成为MySQL默认的引擎。

?Memory?基于内存的,非事务性的以及非持久性的存储引擎。

注意:

? ? ? ? 从5.5版本开始,MySQL表的默认存储引擎从MyISAM换成InnoDB,将会用户安装那些依赖默认设置或者者专门为MyISAM编写的软件包时带来很大的影响。

(二)MySQL索引类型

? ? ?? ?MySQL支持在所有关系数据库表中创立主键、唯一键、不唯一的非主码索引等多种类型的索引。此外MySQL还支持纯文本和空间索引类型。

? ? ? ?MySQL内置的存储引擎对各种索引技术有不同的实现方式,包括:B-树,B+树,R-树以及散列类型。

? ? ? ?索引数据结构理论:

??1.B-树

? ??B-树中有两种节点类型:索引节点和叶子节点。叶子节点是使用来存储数据的,而索引节点则使用来告诉使用户存储在叶子节点中的数据顺序,并帮助使用户找到相应的数据。

? ? ? ?B-树的搜索,从根节点开始,对节点内的关键字有序进行二分查找,假如命中则结束,否则进入查询关键字所属范围的儿子节点,重复。直到所对应的儿子指针为空,或者已经是叶子节点。

? ? ? ?B-树是一种多路搜索树:

? ? ? ?(1). 定义任意非叶子节点最多有M个儿子,且M>2;

? ? ? ?(2). 根节点的儿子数为[2,M];

? ? ? ?(3). 除根节点以外的非叶子节点的儿子数为[M/2,M];

? ? ? ?(4). 每个节点存放至少M/2-1(取上整)和至多M-1个关键字;

? ? ?? (5). 非叶子节点的关键字个数=指向儿子节点的指针的个数-1; ?

? ? ? ?(6). 非叶子节点的关键字:k[i]

? ? ? ?(7). 非叶子节点的指针:p[1],p[2],·····,p[M];其中p[1]指向的关键字小于k[1]的子树,p[M]指向的关键字大于K[m-1]的子树;

? ? ? ?(8). 所有的叶子节点位于同一层;?

? ? ?2.B+树

? ??B+树数据结构是B-树实现的加强版本。虽然B+树支持B-树索引的所有特性,它们之间最明显的不同点在于B+树中底层数据是根据被提及的索引列进行排序的。B+树还通过叶子节点之间的附加引使用来优化扫描性能。

? ? ? ?B+搜索和B-搜索不同,区别是B+树只有达到叶子节点才命中(B-树可以在非叶子节点命中),其性能等价于关键字全集做一次二分搜索。

? ? ? B+树的特性:

? ? ?(1)所有关键字都出现在叶子节点的链表中,叶子节点相当于存储数据的数据层。

? ? ?(2)不可能在非叶子节点上命中。

? ? ?(3)非叶子节点相当于是叶子节点的索引,叶子节点相当于数据层。

?3.散列

? ? ?散列表数据结构是一种很简单的概念,它将一种算法应使用到给定值中以在底层数据存储系统中返回一个唯一的指针或者位置。散列表的优点是始终以线性时间复杂度找到需要读取的行的位置,而不像B-树那样需要横跨多层节点来确定位置。

?4.通信R-树

? ? R-树数据结构支持基于数据类型对几何数据进行管理。目前只有MyISAM用R-树实现支持空间索引,用空间索引也有很多限制,比方只支持唯一的NOT NULL列等。

?5.全文本

? ? ?全文本结构也是一种MySQL采使用的基本数据结构。这种数据结构目前只有当前版本MySQL中的MyISAM存储引擎支持。5.6版本将要在InnoDB存储引擎中加入全文本功能。全文本索引在大型系统中并没有什么实使用的价值,由于大规模系统有很多专门的文件检索产品。所以不使用在详情。

MySQL实现

? ? ? ?对B-树,B+树和散列等数据结构的基本概念有了少量理解之后,我们即可以开始探讨MySQL通过支持它们的存储引擎如何实现不同的算法。同时每种实现也对磁盘和内存用情况有不同的影响,这一点在大型数据库系统中是非常重要的考虑因素。

1.MyISAM的B-树

??? ?MyISAM存储引擎用B-树数据结构来实现主码索引、唯一索引以及非主码索引。在MyISAM实现数据目录和数据库模式子目录中,使用户可以找到和每个MySQL表对应的.MYD和.MYI文件。数据库表上定义的索引信息就存储在MYI文件中,该文件的块大小是1024字节。这个大小是可以通过myisam-block-size系统变量分配。

? ? $ ?ls -1h /var/lib/mysql/book/source_words.MY*

? ? -rw-rw—- 1 mysql mysql ?9.2M 2015-05-07 19:08

? ? source_words.MYD

? ?-rw-rw—- 1 mysql mysql ?7.8M 2015-05-07 19:08

? ? source_words.MYI

? ? ?这些文件结构的内部格式可以从MySQL免费源代码中找到,也可以查看MySQL内部手册。

在MyISAM中,非主码索引的B-树结构存储索引值和一个指向主码数据的指针,这是MyISAM和InnoDB的一个明显区别。这一点导致了两个存储引擎的索引的不同工作方式。

? ? ?MyISAM索引是在内存的一个公共缓存中管理的,这个缓存的大小可以通过key_buffer_size或者者其余命名键缓存来定义。这是根据统计和规划的表索引的大小来设定缓存大小时主要的考虑因素。

2. InnoDB的B+树聚簇主码

? ? ? InnoDB存储引擎在它的主码索引(也被称为聚簇主码)中用了B+树,这种结构把所有数据都和对应的主码组织在一起,并且在叶子节点这一层上增加额外的向前和向后的指针,这样即可以更方便地进行范围扫描。

? ? ? 在文件系统层面,所有InnoDB数据和索引信息都默认在公共InnoDB表空间中管理,否则管理员就通过innodb_data_file_path这个变量指定文件路径。这是一个叫ibdatal文件。

? ? ? 因为InnoDB使用聚簇主码存储数据,底层信息占使用的磁盘空间的大小很大程度上取决于页面的填充因子。对于按序排列的主码,InnoDB会使用16K页面的15/16作为填充因子。对于不是按序排列的主码,默认情况下InnoDB会插入初始数据的时候为每一个页面分配50%作为填充因子。

? ? ??在改索引的实现方式中B+树的叶子节点上是data就是数据本身,key为主键,假如是一般索引的话,data便会指向对应的主索引。在B+树的每一个叶子节点上面添加一个指向相邻叶子节点的指针,就形成了带有顺序访问指针的B+树。其目的是提高区间访问的性能。

3.InnoDB的B-树非主码

InnoDB中的非主码索引用了B-树数据结构,但InnoDB中的B-树结构实现和MyISAM中并不一样。在InnoDB中,非主码索引存储的是主码的实际值。而MyISAM中,非主码索引存储的包含主码值的数据指针。这一点很重要。首先,当定义很大的主码的时候,InnoDB的非主码索引可能回更大,随着非主码索引数量的添加,索引之间大小差别可能会变得很大。另一个不同点在于非主码索引当前可以包含主键的值,并且可以不是索引必需有的部分。

4.内存散列索引

? ? 在默认MySQL的引擎索引中,只有MEMORY引擎支持散列数据结构,散列结构的强度可以表示为直接键查找的简单性,散列索引的类似度模式匹配查询比直接查询慢。也可以为MEMORY引擎指定一个B-树索引实现。

5.内存B-树索引

? ?对于大型MEMORY表来说,用散列索引进行索引范围搜索的效率很低,B-树索引在执行直接键查询时的确比用默认的散列索引快。根据B-树的不同深度,B-树索引在个别操作中确实可能比散列算法快。

6.InnoDB内部散列索引

?InnoDB存储引擎在聚簇B+树索引中存储主码:但在InnoDB内部还是用内存中的散列表来更高效地进行主码查询。这个机制有InnoDB存储引擎来管理,使用户只能通过innodb_adaptive_hash_index配置项来选择能否启使用这个唯一的配置选项。

欢迎工作一到五年的Java工程师朋友们加入Java架构开发:744677563

本群提供免费的学习指导 架构资料 以及免费的解答

不懂得问题都可以在本群提出来 之后还会有职业生涯规划以及面试指导

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 深入理解MySQL的索引

发表回复