所有文章 分类 标签 笔记 文档 关于 简体中文

目录

Mysql索引笔记

KKKPSJKEY 收录于 Back 笔记
   约 6591 字   预计阅读 14 分钟    次阅读  
/mysql-index-note/featured-image.jpg

B+ 树的优缺点

优点

  1. 单次请求涉及的磁盘IO次数少（出度d大，且非叶子节点不包含表数据，树的高度小）；
  2. 查询效率稳定（任何关键字的查询必须走从根结点到叶子结点，查询路径长度相同）；
  3. 遍历效率高（从符合条件的某个叶子节点开始遍历即可）；

在B+树中， 由于底层的各个叶子节点都通过指针组织成一个双向链表， 结构如下图所示。 因此，只需要从跟节点到叶子节点定位到第一个满足条件的Key, 然后不断在叶子节点迭代next指针即可实现遍历，此时相当于顺序IO。相反，如果通过每次从根节点查找进行遍历，相当于进行随机IO，效率低下，如下图所示：

./1.png

./2.png

缺点

B+树最大的性能问题在于会产生大量的随机IO，主要存在以下两种情况：

  1. 主键不是有序递增的，导致每次插入数据产生大量的数据迁移和空间碎片；
  2. 即使主键是有序递增的，大量写请求的分布仍是随机的；

mysql的索引底层原理

什么是索引

概念：索引是提高mysql查询效率的数据结构。总的一句话概括就是索引是一种数据结构。

数据库查询是数据库的最主要功能之一。设计者们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如：有顺序查找、折半查找、快速查找等。

但是每种查找算法都只能应用于特定的数据结构之上，例如顺序查找依赖于顺序结构，折半查找通过二叉查找树或红黑树实现二分搜索。因此在数据之外，数据库系统还维护着满足特定查找算法的数据结构。这种数据结构，就是索引。

Mysql索引原理

目前大多数数据库系统及文件系统都采用 B-Tree 或其变种 B+Tree 作为索引结构。B+ 树索引是 B+ 树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。

从最早的平衡二叉树演化而来的。B+ 树是由二叉查找树、平衡二叉树（AVLTree）和平衡多路查找树（B-Tree）逐步优化而来。

那么为什么mysql的索引选择B+数呢？

红黑树也可以作为数据结构也可以用来实现索引，但是文件系统以及数据库系统普遍采用B树或者B+树，这里结合计算的组成原理来深入的分析。

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储在磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，硬盘I/O存取的消耗要高几个数量级，查找过程中磁盘I/O的存取次数。

为什么硬盘的存取会如此的慢呢？

这个就要讲硬盘的读写原理，硬盘有很多种，但是都是由盘片、磁头、盘片主轴、控制电机、磁头控制器、数据转换器、接口、缓存等几个部分组成。

所有的盘片都固定在一条轴上，那条轴叫做盘片主轴，所有的盘片都是绝对平行的，也形成一个柱体，每个盘片上都有一个磁头，每个磁头都在同意轴线上，就是从上方往下看，磁头是绝对重叠的。

所有的磁头连在一个磁头控制器上，由磁头控制器负责各个磁头的运动，磁头可沿盘片的半径方向移动，实际上是斜切运动，每个磁头同一时刻必须是同轴的盘片以每分钟数千转到上万转的速度在高速运转，这样磁头就能对盘片上的指定位置进行数据的读写操作。结构图如下：

./3.gif

磁盘数据的读写原理

盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。

当磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。

为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。

即一次磁盘的读写操作完成过程由三个动作组成：

  1. 寻道（时间）：磁头移动定位到指定磁道。
  2. 旋转延迟（时间）：等待指定扇区从磁头下旋转经过。
  3. 数据传输（时间）：数据在磁盘与内存之间的实际传输

额外知识： （1）盘面：硬盘的每一个盘片都有上下两个盘面，一般每个盘面都会得到利用，都可以存储数据，盘面号又叫磁头号，因为每一个有效盘面都有一个对应的读写磁头。 （2）磁道：磁盘在格式化时被划分成许多同心圆，这些同心圆轨迹叫做磁道，磁道从外向内从 0 开始顺序编号，信息以脉冲串的形式记录在这些轨迹中，这些同心圆不是连续记录数据，而是被划分成一段段的圆弧。 （3）所有盘面上的同一磁道构成一个圆柱，通常称作柱面。所有盘面上的同一磁道构成一个圆柱，通常称作柱面。数据的读 / 写按柱面进行，而不按盘面进行，当一个磁道写满数据后，就在同一柱面的下一个盘面来写，一个柱面写满后，才移到下一个扇区开始写数据，读数据也按照这种方式进行，这样就提高了硬盘的读 / 写效率。

提高磁盘数据读写原理

局部性原理与磁盘预读。由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。

为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。

这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。

所以，程序运行期间所需要的数据通常应当比较集中。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

预读的长度一般为页（page）4k的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。

当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

在硬盘中由于涉及到机械运动，所以一次的磁盘IO消耗的时间是非常大的，于内存的读取速度相比，就好比光速与声速的比较。那么回到我们的主题上为什么使用B+树作为数据结构呢？

B树、B-树、B+树、红黑树性能分析

对于B树和、B-树、B+树这里只做简单的介绍，详细的特性请看着一篇[]。

B树性能分析：B树是二叉查找平衡树，但是B树一个节点只存一个关键字，在大量数据的时候，B树树高非常大，性能低下。

B-树性能分析：B-树对B树性能做了很大优化，但是B-树在大量数据的时候，也会访问到叶子节点，这样性能也是大大降低。

根据B-Tree的定义，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。

B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存）。一般实际应用中，出度d（树中各个节点的度的最大值）是非常大的数字，通常超过100，因此树高h非常小（通常不超过3）。

./4.jpg

模拟查找关键字 36 的过程：

  1. 根据根节点找到磁盘块 1，读入内存。【磁盘 I/O 操作第 1 次】
  2. 比较关键字 36在区间（17,35），找到磁盘块 1 的指针 P3。
  3. 根据 P3指针找到磁盘块 4，读入内存。【磁盘 I/O 操作第 2 次】
  4. 比较关键字 36在区间（65,87），找到磁盘块 4 的指针 P1。
  5. 根据 P1 指针找到磁盘块 9，读入内存。【磁盘 I/O 操作第 3 次】
  6. 在磁盘块 98中的关键字列表中找到关键字 36。

分析上面过程，发现需要 3 次磁盘 I/O 操作，和 3 次内存查找操作。而 3 次磁盘 I/O 操作是影响整个 B-Tree 查找效率的决定因素。

红黑树性能分析：而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。

B+树性能分析：B+Tree 是在 B-Tree 基础上的一种优化，使其更适合实现外存储索引结构，InnoDB 存储引擎就是用 B+Tree 实现其索引结构。

在 B+Tree 中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储 key 值信息，这样可以大大加大每个节点存储的 key 值数量，降低 B+Tree 的高度。

B+Tree更适合外存索引，从上面分析可以看到，d越大索引的性能越好，而出度的上限取决于节点内key和data的大小。

在B+树的结构中，只在叶子节点存储数据，在非叶子节点中只存储的索引，在非叶子节点中可以有更大的空间储存更多的索引，这样B+树的出度d就可以大大的增加，从而降低的B+树的高度h，B树中一个节点的大小为一个page的大小，也就是一次IO的读取，h越小IO的次数就可以减少：

dmax=floor(pagesize/(keysize+datasize+pointsize))

floor表示向下取整。由于B+Tree内节点去掉了data域，因此可以拥有更大的出度，拥有更好的性能。

Mysql的InnoDB的索引的结构如下图所示：

./5.jpg

在MySQL中，不同存储引擎对索引的实现方式是不同的，Mysql有MyISAM和InnoDB两个存储引擎的索引实现方式，下面就来分别介绍这两种存储引擎。

Mysql引擎

MyISAM

在MyISAM储存引擎中，数据和索引文件试试分开储存的，Myisam 的存储文件有三个，后缀名分别是 .frm、.MYD、MYI，其中 .frm 是表的定义文件，.MYD 是数据文件，.MYI 是索引文件。

./6.png

Myisam 只支持表锁，且不支持事务。Myisam 由于有单独的索引文件，在读取数据方面的性能很高 。

Myisam 也是B+树结构，但是MyISAM索引的叶子节点的数据保存的是行数据的地址。因此，MyISAM中索引检索的算法首先在索引树中找到行数据的地址，然后根据地址找到对应的行数据。

./7.jpg

可以看出MyISAM的索引文件仅仅保存数据记录的地址。主键索引和辅助索引，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的如下图：

./8.jpg

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

InnoDB

在InnoDB中，数据和索引文件是合起来储存的，如图所示，InnoDB 的存储文件有两个，后缀名分别是 .frm 和 .idb，其中 .frm 是表的定义文件，而 idb 是数据文件。

./9.png

在InnoDB虽然底层也是B+树实现的方式，当时与MyISAM却有明显的区别，在InnoDB实现的索引结构中，索引文件和数据文件是一起的，InnoDB中索引文件中的key就是数据表中的主键索引，因此InnoDB的索引文件也是主索引文件。如下图所示：

./10.jpg

在InnoDB中的叶子节点中把保存和完整的数据，这就是聚集索引。因为InnoDB是按照主键聚集的，要是InnoDB没有主键就会找数据表中的位置标志的字段作为主键，要是没有这种字段就会隐世的生成唯一标识的主键，生成的主键默认为长整型，6个字节。

而MyISAM可以要求没有主键，这是这两者的一个明显的区别。另一个区别就是辅助索引的叶子节点的data域存储的是主键的值，而不是行数据。

所以，当查询不是按照主键查询时候就会先在辅助索引树上先找到主键的值，然后再到主索引树找到对应的行数据的值，这叫做回表，回表降低了表的查询效率。

如果给另一个字段指定为普通索引，则普通索引树的结构如下图所示：

./11.jpg

知道了索引的底层原理的实现还是有很大的帮助的，例如：主键至不要过大，因为所有的普通索引都引用主索引，索引本身是占内存的，若是索引过大，这样就会大大影响查询的效率。

InnoDB其它特点： 在InnoDB 中存在表锁和行锁，不过行锁是在命中索引的情况下才会起作用，当索引失效时行锁也会失效。InnoDB 支持事务，且支持四种隔离级别（读未提交、读已提交、可重复读、串行化），默认的为可重复读；而在 Oracle 数据库中，只支持串行化级别和读已提交这两种级别，其中默认的为读已提交级别。

Mysql索引最左匹配原则的理解

1
2
3
4
5
6
7
8

CREATE TABLE `student` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL,
  `cid` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `name_cid_INX` (`name`,`cid`),
  KEY `name_INX` (`name`)
) ENGINE=InnoDB AUTO_INCREMENT=8 DEFAULT CHARSET=utf8

执行1

1

EXPLAIN SELECT * FROM student WHERE    name='小红';

./12.png

执行2

1

EXPLAIN SELECT * FROM student WHERE   cid=1;

./13.png

1

EXPLAIN SELECT * FROM student WHERE   cid=1 AND name='小红';

./14.png

为什么还能匹配索引？

你的疑问是：sql查询用到索引的条件是必须要遵守最左前缀原则，为什么上面两个查询还能用到索引？

讲上面问题之前，我先补充一些知识，因为我觉得你对索引理解是狭隘的：

上述你的两个查询的explain结果中显示用到索引的情况类型是不一样的。,可观察explain结果中的type字段。你的查询中分别是：

  1. type: index
  2. type: ref

解释

​ index：这种类型表示是mysql会对整个该索引进行扫描。

​ 要想用到这种类型的索引，对这个索引并无特别要求，只要是索引，或者某个复合索引的一部分，mysql都可能会采用index类型的方式扫描。

​ 但是呢，缺点是效率不高，mysql会从索引中的第一个数据一个个的查找到最后一个数据，直到找到符合判断条件的某个索引。

所以

对于你的第一条语句：

1

EXPLAIN SELECT * FROM student WHERE   cid=1;

判断条件是cid=1,而cid是(name,cid)复合索引的一部分，没有问题，可以进行index类型的索引扫描方式。explain显示结果使用到了索引，是index类型的方式。

ref

​ 这种类型表示mysql会根据特定的算法快速查找到某个符合条件的索引，而不是会对索引中每一个数据都进行一 一的扫描判断，也就是所谓你平常理解的使用索引查询会更快的取出数据。

​ 而要想实现这种查找，索引却是有要求的，要实现这种能快速查找的算法，索引就要满足特定的数据结构。

​ 简单说，也就是索引字段的数据必须是有序的，才能实现这种类型的查找，才能利用到索引。

有些了解的人可能会问，索引不都是一个有序排列的数据结构么。不过答案说的还不够完善，那只是针对单个索引，而复合索引的情况有些同学可能就不太了解了。

下面就说下复合索引： 以该表的(name,cid)复合索引为例,它内部结构简单说就是下面这样排列的：

./15.png

mysql创建复合索引的规则是首先会对复合索引的最左边的，也就是第一个name字段的数据进行排序，在第一个字段的排序基础上，然后再对后面第二个的cid字段进行排序。

其实就相当于实现了类似 order by name cid这样一种排序规则。

所以

​ 第一个name字段是绝对有序的，而第二字段就是无序的了。

​ 所以通常情况下，直接使用第二个cid字段进行条件判断是用不到索引的，当然，可能会出现上面的使用index类型的索引。

​ 这就是所谓的mysql为什么要强调最左前缀原则的原因。

那么什么时候才能用到呢?

​ 当然是cid字段的索引数据也是有序的情况下才能使用咯，什么时候才是有序的呢？

​ 观察可知，当然是在name字段是等值匹配的情况下，cid才是有序的。

​ 发现没有，观察两个name名字为 c 的cid字段是不是有序的呢。从上往下分别是4 5。

​ 这也就是Mysql索引规则中要求复合索引要想使用第二个索引，必须先使用第一个索引的原因。（而且第一个索引必须是等值匹配）。

所以对于你的这条sql查询：

1

EXPLAIN SELECT * FROM student WHERE   cid=1 AND name='小红';

没有错，而且复合索引中的两个索引字段都能很好的利用到了！因为语句中最左面的name字段进行了等值匹配，所以cid是有序的，也可以利用到索引了。

你可能会问

​ 我建的索引是(name,cid)。

​ 而我查询的语句是cid=1 AND name=‘小红’; 我是先查询cid，再查询name的，不是先从最左面查的呀？

​ 好吧，我再解释一下这个问题：首先可以肯定的是把条件判断反过来变成这样 name=‘小红’ and cid=1; 最后所查询的结果是一样的。

​ 那么问题产生了？既然结果是一样的，到底以何种顺序的查询方式最好呢？

所以　　

​ 而此时那就是我们的Mysql查询优化器该登场了，Mysql查询优化器会判断纠正这条Sql语句该以什么样的顺序执行效率最高，最后才生成真正的执行计划。

​ 所以，当然是我们能尽量的利用到索引时的查询顺序效率最高咯，所以mysql查询优化器会最终以这种顺序进行查询执行。

更新于 2022-06-06
阅读原始文档
 DataBase, Mysql , Index, MysqlNote
返回 | 主页