一、索引的概念

1、什么是索引？

MySQL 官方对索引的定义为：索引（Index）是帮助 MySQL 高效获取数据的数据结构。从官方的定义可以得到索引的本质：索引是数据结构，可以简单理解为索引就是一种数据结构，它可以帮助我们快速的从数据库查询到数据。索引就类似于一本书的目录，通过目录可以快速找到需要查找对内容。

在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。下图就是一种可能的索引方式示例：

左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址 。 为了加快 Col2 的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指 针，这样就可以运用二叉查找在一定的复杂度内获取到相应数据，从而快速的检索出符合条件的记录。一般来说索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。

2、索引的优缺点分析？

优势

• 提高查询效率：提高对数据的检索效率，降低数据库的IO成本。
• 天生排序：通过索引对数据进行排序，降低数据的排序成本，从而降低了CPU的消耗。

劣势

• 降低更新表的速度：虽然索引大大提高了查询速度，同时却会降低更新表的速度，如对表进行INSERT、UPDATE和DELETE。因为更新表时，MySQL不仅要保存数据，还要保存一下索引文件每次更新添加了索引列的字段，都会调整因为更新所带来的键值变化后的索引信息。因此，如果你的表INSERT/UPDATE/DELETE操作比较多的话还是不建议使用索引，这样反而会降低数据库的速度。
• 占用额外的空间：实际上索引也是一张表，该表保存了主键与索引字段，并指向实体表的记录，所以索引列也是要占用空间的。

二、索引的数据结构

索引是在MySQL的存储引擎层实现的，所以每种存储引擎支持的缩影都不一定完全相同，也不是所有的存储引擎都支持所有的索引类型，MySQL目前提供了以下4中数据类型的索引：

• B+树索引：最常见的索引类型，大部分存储引擎都支持BTREE索引。
• Hash索引：只有Memory引擎支持，使用场景比较简单。
• R-tree索引（空间索引）：空间索引是MyISAM引擎的一个特殊索引类型，通常使用较少。
• Full-text索引（全文索引）：全文索引也是MyISAM支持的一种特殊索引类型，主要用于全文索引，InnoDB从MySQL5.6开始也支持全文索引。

我们平常所说的索引，没有特殊说明，都是指**B+树（多路搜索树）**结构组织组织的索引。下面我们就来详细了解一下B树索引。

这里经常可能会有面试问B+树和Hash索引的区别，这里总结一下。

• Hash索引的底层数据结构就是hash表，它适用于等值查询，不适用于范围查询；
• Hash索引没有办法实现排序，但是B+树索引就有这方面的优点；
• Hash索引不支持多列复合索引的最左前缀规则，如果有大量重复键值得情况下，哈希索引的效率会很低，因为存在哈希碰撞问题

1、B树结构

B树又叫多路平衡搜索树，一颗m叉的B树具有如下特性：

• 每个节点最多可以存储m-1个关键字。
• 根节点最少要有1个关键字；非根节点至少有m/2个关键字。
• 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
• 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。
• 每个非叶子节点有n个key与n+1个指针组成，其中m/2向上取整-1<=n<=m-1。

以5叉B树为例，key的个数范围就是：2<=n<=4。当n>4的时候，中间节点分裂成父节点，两边结点做子节点。

这里我们以插入C N G A H E K Q M F W L T Z D P R X Y S数据为例。

插入过程分析

B树的插入，我们只需要记住一个规则：判断当前结点key的个数是否小于等于m-1，如果满足，直接插入即可，如果不满足，将节点的中间的key将这个节点分为左右两部分，中间的节点放到父节点中即可。并且在插入中是根据关键字大小来决定一个关键字位置的。

（1）插入前4个字母：C N G A，结点key的个数<=4，key只需要按字典序排好位置就可以了

（2）插入H ，此时n>4了，中间的结点G应该分裂成为父节点，其余结点按大小分裂到两边做子节点

（3）插入E K Q 不需要分裂

（4）插入M，中间元素M分裂到父节点

（5）插入F W L T不需要分裂

（6）插入Z，中间节点T分裂到父节点

（7）插入D时，中间节点D分裂到父节点，之后接着插入P R X Y都不会导致节点分裂

（8）最后插入S，NPQR节点个数>4了，中间接单Q向上分裂，但是分裂后父节点的关键字个数也大于4了，此时父节点中间元素M再次分裂

至此，B树的构建就完成了，B树相对于二叉树来说，B树的搜索效率更高，因为兑入同等两级的数量，B树的层数更少，因此比较的次数就越少。

B树的查找过程分析 下面展示的是一个3层B树的结构图，

实例图说明: 每个节点占用一个磁盘块，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例。关键字为16和34, P1指针指向的子树的数据范围为小于16, P2 指针指向的子树的数据范围为16~34，P3指针指向的子树的数据范围为大于34。比如要找75这个数据块，那么查找关键字的过程如下：

（1）根据根节点找到磁盘块1，读入内存。【第一次I/O】

（2）比较关键字75在大于34，找到磁盘块的1的指针p3。

（3）根据p3指针找到磁盘块4，读入内存。【第二次I/O 】

（4）比较关键字75在64~88之间，找到磁盘块4的指针p2。

（5）根据p2指针找到磁盘块10，读入内存。【第三次I/O 】

（6）比较关键字，在磁盘块10找到了关键字75

简单分析一下B树的性能：

我们都知道计算机在存储数据的时候，有最小存储单元，这就好比我们今天进行现金的流通最小单位是一毛。在计算机中磁盘存储数据最小单元是扇区，一个扇区的大小是512字节，而文件系统（例如XFS/EXT4）他的最小单元是块，一个块的大小是4k，而对于我们的InnoDB存储引擎也有自己的最小储存单元——页（Page），一个页的大小是16K。

磁盘扇区、文件系统、InnoDB存储引擎都有各自的最小存储单元。

在MySQL中我们的InnoDB页的大小默认是16k，当然也可以通过参数设置：

现在假设每个磁盘块中只有data占用空间，并且一条行记录占用1k的空间，那么一个磁盘块中就可以存储16条数据，那么3层B树理论上就可以存储：16*16*16=4096条记录。当数据继续增加的时候，B树的层数还会增加，层数增加那就意味则I\O次数增加，那效率就慢下来了。为了解决这个问题，B+树就应运而生了，简单来说就是，把在B树中每个结点存储的data去掉，只存储指针，这样一来每个磁盘块就可以存储更多的指针了。

2、B+树结构

B+树是B树的变种，他与B树的区别如下：

• B+树有两种类型的节点：内部结点（也称索引结点）和叶子结点。内部节点就是非叶子节点，内部节点不存储数据，只存储索引（本质是指针），数据都存储在叶子节点。
• 内部结点中的key也按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
• 每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。
• 父节点存有右孩子的第一个元素的索引。

下图所示就是一个B+树结构，上面两层节点都不存数据的，只是一个索引，只在最后一层叶子节点存数据。

B+树性能分析：一棵3层的B+树可以存放多少行数据？ 上文分析B树的时候我们已经说明InnoDB单个叶子节点（页）中的记录数=16K/1K=16。（这里假设一行记录的数据大小为1k，实际上现在很多互联网业务数据记录大小通常就是1K左右）。

那么现在我们需要计算出非叶子节点能存放多少指针？ 其实这也很好算，我们假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，这样一共14字节，我们一个页中能存放多少这样的单元，其实就代表有多少指针，即16384/14=1170。

那么现在我们就可计算出3层B+树可以存放：1170*1170*16=21902400条这样的记录。

所以在InnoDB中B+树高度一般为3层，它就能满足千万级的数据存储。在查找数据时一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。

通过上面的分析我们就可以明白一个道理，为什么要求MySQL的主键应该尽量的小，因为更小的主键可以允许InnoDB一页可以存储更多的索引，这也就可以存储更多的记录。

思考：为什么B+树更适合实际操作系统的文件索引或数据库的索引?

现在这个问题的复杂版本可以参考本文；

他的简单版本回答是： （1）B+树的磁盘读写代价更低。

B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对 B 树更小。如果把所有同一内部结点 的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说 IO 读写次数也就降低了。

（2）B+树的查询效率更稳定。

由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当

3、哈希索引

除了B+树之外，还有一种常见的是哈希索引。

哈希索引就是采用一定的哈希算法，把键值换算成新的哈希值，检索时不需要类似B+树那样从根节点到叶子节点逐级查找，只需一次哈希算法即可立刻定位到相应的位置，速度非常快。

本质上就是把键值换算成新的哈希值，根据这个哈希值来定位。

看起来哈希索引很牛逼啊，但其实哈希索引有好几个局限(根据他本质的原理可得)：

• 哈希索引也没办法利用索引完成排序
• 不支持最左匹配原则
• 在有大量重复键值情况下，哈希索引的效率也是极低的---->哈希碰撞问题。
• 不支持范围查询

三、MySQL的索引分类

索引从数据存储方式上说，分成两类：聚簇索引和非聚簇索引

从功能上说分为6种：单值索引、唯一索引、主键索引、复合索引、外键索引和全文索引

1、聚簇索引和非聚簇索引

（1）聚簇索引

聚簇索引就是按照每张表的主键构造一颗B+树，同时叶子节点中存放的就是整张表的行记录数据，也将聚集索引的叶子节点称为数据页。这个特性决定了索引组织表中数据也是索引的一部分，每张表只能拥有一个聚簇索引。

Innodb通过主键聚集数据，如果没有定义主键，innodb会选择非空的唯一索引代替。如果没有这样的索引，innodb会隐式的定义一个主键来作为聚簇索引。

聚簇索引的优缺点

• 优点：

　　　　1.数据访问更快，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快

　　　　2.聚簇索引对于主键的排序查找和范围查找速度非常快

• 缺点：

　　　　1.插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键 　　　　2.更新主键的代价很高，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新。 　　　　3.二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据。

（2）非聚簇索引 非聚簇索引就是以非主键构建的B+树，非聚簇索引访问数据总是需要二次查找。非聚簇索引叶子节点存储的不再是行的物理位置，而是主键值。通过辅助索引首先找到的是主键值，再通过主键值找到数据行的数据页，再通过数据页中的Page Directory找到数据行。

　　Innodb辅助索引的叶子节点并不包含行记录的全部数据，叶子节点除了包含键值外，还包含了相应行数据的聚簇索引键。

　　辅助索引的存在不影响数据在聚簇索引中的组织，所以一张表可以有多个辅助索引。在innodb中有时也称辅助索引为二级索引。

2、单值索引、唯一索引、主键索引、复合索引、外键索引、全文索引

2.1 单值索引

概念：即一个索引只包含单个列，一个表可以有多个单列索引。

语法：

2.2 唯一索引

概念： 索引列的值必须唯一，但允许有空值

语法：

2.3 主键索引

概念： 特殊的唯一索引，不允许有空值。设定为主键后数据库会自动建立索引，innodb为聚簇索引。主键索引会随着表的创建而创建。

2.4 复合索引

概念：一个索引中包含多个列。

语法：

在mysql建立复合索引时会遵循最左前缀匹配的原则，即最左优先，在检索数据时从复合索引的最左边开始匹配。比如上面这个索引语句其实就是创建了（customer_no）、（customer_no,customer_name）以及（customer_no,customer_name,customer_age）是三个索引。简单来说复合索引有以下几个好处：

（1）**可以减少开销。**每多一个索引，都会增加写操作的开销和磁盘空间的开销。对于大量数据的表，使用联合索引会大大的减少开销！

（2）覆盖索引。MySQL可以直接通过遍历索引取得数据，而无需回表，这减少了很多的随机io操作。减少io操作，特别的随机io其实是dba主要的优化策略。所以，在真正的实际应用中，覆盖索引是主要的提升性能的优化手段之一。

（3）效率高。索引列越多，通过索引筛选出的数据越少。

四、索引的设计原则

索引的设计可以遵循一些已有的原则，创建索引的时候请尽量考虑复合这些原则，便于提升索引的使用效率，更高效的使用索引。

• （1）对查询频次高，且数据量适量的表建立索引。一般来说，小表使用全表扫描更快，中大表才使用索引。超级大表索引基本无效。
• （2）索引字段的选择，最佳候选列应当从where子句的条件中提取，如果where子句中的组合比较多，那么应当挑选最常用，过滤效果最好的列的组合。
• （3）尽量使用唯一性高的字段作为索引，字段区分度越高，索引的效率越高。
• （4）索引可以有效的提高数据查询的效率，但事事都是物极必反的，过多的索引不仅会占用大量的磁盘空间，还会增加数据库系统维护索引的代价。
• （5）使用短索引，索引的字段的内容应该尽可能少，不然索引也会占用过多的磁盘空间。
• （6）利用最左前缀原则，N个列组合而成的复合索引，相当于创建了N个索引，如果查询时where子句中使用了组成该索引的前几个字段，那么查询效率会大大提升。