MySQL——索引实现原理

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

MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构。

MyISAM会按照数据插入的顺序分配行号,从0开始,然后按照数据插入的顺序存储在磁盘上。因为行是定长的,所以可以从表的开头跳过相应的字节找到需要的行。

MyISAM的一级索引(主键索引),一个节点包含多个内部节点,索引中的每个叶子节点包含“行号”。假设我们以col1为主键,则下图是一个MyISAM表的主索引(Primary key)示意。

可以看出MyISAM的索引文件仅仅保存数据记录的行号,然后通过此行号回表查询需要的数据。

那col2列上的索引(辅助索引)又会怎么样呢?有什么特别之处吗?答案是否定的,和一级索引(主键索引)没有什么区别。在MyISAM中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。如果我们在col2上建立一个辅助索引,则此索引的结构如下图所示:

因此,MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。MyISAM的索引方式索引和数据存放是分开的,非聚集”的,所以也叫做非聚集索引。

InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同。因为InnoDB支持聚簇索引(主键索引),聚簇索引就是表,所以InnoDB不用像MyISAM那样需要独立的行存储。也就是说,InnoDB的数据文件本身就是索引文件。

聚簇索引的每一个叶子节点都包含了主键值、事务ID、用于事务和MVCC的回滚指针以及所有的剩余列。假设我们以col1为主键,则下图是一个InnoDB表的聚簇索引(主键索引)(Primary key)示意。

与MyISAM不同的是,InnoDB的二级索引和聚簇索引很不相同。InnoDB的二级索引的叶子节点存储的不是行号(行指针),而是主键列。这种策略的缺点是二级索引需要两次索引查找,第一次在二级索引中查找主键,第二次在聚簇索引中通过主键查找需要的数据行。

画外音:可以通过我们前面提到过的索引覆盖来避免回表查询,这样就只需要一次回表查询,对于InnoDB而言,就是只需要一次索引查找就可以查询到需要的数据记录,因为需要的数据记录已经被索引到二级索引中,直接就可以找到。

好处是InnoDB在移动行时无需更新一级索引中的这个”指针“,因为主键是不会改变的,但是行指针却会改变。

InnoDB的二级索引示意如图:

使用InnoDB主键应该知道的事项

因为InnoDB的索引的方式通过主键聚集数据,严重依赖主键。索引如果没有定义主键,那么InnoDB会选择一个唯一的非空索引代替。如果没有这样的索引,InnoDB会隐式定义一个主键来作为聚簇索引。

聚簇索引的优点有:

1.可以把相关数据存储在一起,减少数据查询时的磁盘I/O

2.数据访问更快,因为聚簇索引就是表,索引和数据保存在一个B+Tree中

3.使用索引覆盖的查询时可以直接使用页节点中的主键值

聚簇索引的缺点有:

1.插入速度严重依赖插入顺序

2.更新聚簇索引列的代价很高,因为会强制InnoDB把更新的列移动到新的位置

3.基于聚簇索引的表在插入新行,或者主键被更新导致需要移动行的时候,可能会导致“页分裂”。当行的主键值要求必须将这一行插入到已满的页中时,存储引擎会将该页分裂为两个页面来容纳该行,这就是一次页分裂操作,页分裂会导致表占用更多的存储空间。

画外音:关于,我们在上一篇文章中也提到过。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页。存和磁盘以页为单位交换数据。数据库系统的设计者巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次磁盘I/O就可以完全载入

基于聚簇索引以上的这些特点,在InnoDB中,我们应该尽量使用和应用无关的主键,例如自增主键,这样可以保证数据行是按照顺序写入的。而不是使用GUID、UUID生成随机的主键。

向聚簇索引中插入顺序的索引值:

每条新纪录总是在前一条记录的后面插入:

当页被插满后,继续插入到新的页:

向聚簇索引中插入随机的索引值:

新的记录可能被插入到之前记录的中间,导致需要强制移动之前的记录:

被写满且已经刷到磁盘上的页可能会被重新读取用于再次插入,此时还需要进行页分裂:

总结

MyISAM和InnoDB两个存储引擎的索引虽然都是使用的B+Tree数据结构,但是在具体实现上还是存在不小差别的。InnoDB支持聚簇索引,聚簇索引就是表,所以InnoDB不用像MyISAM那样需要独立的行存储。也就是说,InnoDB的数据文件本身就是索引文件。而MyISAM的数据文件和索引文件是分开存储的。可以通过MyISAM和InnoDB如何存放表的抽象图帮助快速理解。

InnoDB(聚簇)表分布:

MyISAM(非聚簇)表分布:

原文发布于微信公众号 - 撸码那些事(lumanxs)

原文发表时间:2018-08-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PHP在线

性能调优之MYSQL高并发优化

一、数据库结构的设计 表的设计具体注意的问题: 1、数据行的长度不要超过8020字节,如果超过这个长度的话在物理页中这条数据会占用两行从而造成存储碎片,降低查询...

4557
来自专栏数据和云

层层升入:SQL极限调优之一次更新操作的N种优化可能

杨廷琨,网名 yangtingkun 云和恩墨技术总监,Oracle ACE Director,ACOUG 核心专家 最近进行了一次更新操作,整个处理和优化的过...

3028
来自专栏Linyb极客之路

深入理解MySQL索引原理和实现——为什么索引可以加速查询?

说到索引,很多人都知道“索引是一个排序的列表,在这个列表中存储着索引的值和包含这个值的数据所在行的物理地址,在数据十分庞大的时候,索引可以大大加快查询的速度,这...

1313
来自专栏极客慕白的成长之路

MySQL从安装到使用

Columns 列;Indexes 索引;Views 视图;Events 事件;Fields 字段;

794
来自专栏zingpLiu

python【第十二篇】Mysql基础

数据库(Database)是按照数据结构来组织、存储和管理数据的仓库,每个数据库都有一个或多个不同的API用于创建,访问,管理,搜索和复制所保存的数据。我们也可...

962
来自专栏desperate633

MySQL索引实现原理分析

目前大部分数据库系统及文件系统都采用 B-Tree(B 树)或其变种 B+Tree(B+树)作为索引结构。B+Tree 是数据库系统实现索引的首选数据结构。

943
来自专栏Java进阶干货

MySQL命令,一篇文章替你全部搞定

MySQL的基本操作可以包括两个方面:MySQL常用语句如高频率使用的增删改查(CRUD)语句和MySQL高级功能,如存储过程,触发器,事务处理等。而这两个方面...

2032
来自专栏Java帮帮-微信公众号-技术文章全总结

MySQL全部知识点(2)

6 聚合函数 聚合函数是用来做纵向运算的函数: l COUNT():统计指定列不为NULL的记录行数; l MAX():计算指定列的最大值,如果指定列是字符串类...

3487
来自专栏文渊之博

mysql表分区简述

数据库分区是一种物理数据库设计技术。虽然分区技术可以实现很多效果,但其主要目的是为了在特定的SQL操作中减少数据读写的总量以缩减sql语句的响应时间,同时对于应...

1043
来自专栏Java修行之道

四种简单的sql语句(增删改查语句)

2924

扫码关注云+社区