开篇之前，先介绍给大家一个数据结构可视化的网站，里面可以对各种数据结构进行可视化的操作。便于对底层的原理进行理解。

索引的涵义

大家小学时候，都有过使用字典的经历，要查某个字 ，我们一般会通过拼音或者偏旁部首在字典前面的索引页进行查找。查到相关联的字所在的页码，再跳转到相应的页码进行查找。大大增加了查询的效率。

使用字典的场景，就体现了索引的思想。简单的说，索引就是在大量数据里面检索特定数据时，为了提升检索效率，而提供的按某种结构组织的“中间”数据。我们查询时，先去查“中间”数据，然后根据“中间”数据得到最终目标数据的“地址”，去这个地址把我们要找的数据拿出来。

当我们使用MySQL数据库的时候，也是同样的道理，如果表里面有百万级甚至千万级的数据时，如果没有索引，那我们想要检索特定的一行数据，效率将极其低下。

效率低下的本质：大量的IO操作！这里大家一定要注意，如果数据在内存里面，单纯的比对操作是很快的。问题在于每次的查询需要把磁盘数据加载到内存进行计算，这才是我们要用索引的根本所在！

在MySQL数据库里，索引是帮助MySQL高效获取数据的排好序的数据结构

• 索引满足某种数据结构
• 索引本身是有排序的
• 索引本质也是数据

索引的数据结构选择

二叉树

举个例子，看下面的这张表，两列字段：

假设我们需要根据第二个字段作为查询条件，查询第一条满足’col2=89‘的数据，如下语句

select * from t where col2=89 limit 1;

• 假设没有任何索引，则Mysql会逐条查找，比对col2的值是否是89，直到匹配到’col2=89‘的行。这个例子中将比对6次，完成查询。
• 假设为col2这一列建立了索引，索引结构为普通的二叉树，即把col2的数据放入二叉树的结构里，二叉树的每个节点存放一个键值对（key-value），key存放字段的值，value存放该行记录对应的磁盘存储地址（如第一行对应的是地址是0x07）。此时再进行查找时，数据库会根据查询条件带入的值，从索引数据结构的根节点开始查找，根节点对应的值34<89，所以往右子节点继续查，第一个右子节点为89，即满足查询条件。拿出该节点对应的value（即为存储地址），去磁盘拿取该行数据。这次只对比了2次，即完成了查询。

上面的例子，体现了使用二叉树作为的索引时，往往能够加快检索效率。但是我们还不能拿二叉树作为MySQL的索引数据结构类型，因为它有致命的缺陷。比如我们用二叉树对第一列（即自增长的id主键字段）建立索引，看看会有什么问题，这了可以在数据结构可视化的网站进行模拟操作，便会得到下面的索引数据：

大家一眼就能看出问题，由于二叉树结构特点，若子节点大于父节点，则在父节点右边；反之则在父节点左边。我们发现像ID这种单边增长的数据，其二叉树的索引数据结构最终演变成了链表，当根据这个索引进行查找时，本质又是逐条查找。

红黑树

由上面的反例，大家可以看见普通的二叉查找树在极端情况下可退化成链表，此时的增删查效率都会比较低下。为了解决这种情况，就出现了一些自平衡的查找树，比如 AVL，红黑树等。这些自平衡的查找树通过定义一些性质，将任意节点的左右子树高度差控制在规定范围内，以达到平衡状态。
以红黑树为例，红黑树通过如下的性质定义实现自平衡：

节点是红色或黑色。
根是黑色。
所有叶子都是黑色（叶子是NIL节点）。
每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（简称黑高）。

这里就不对红黑树的具体原理做展开讨论，只需要记住一点，它会自动平衡节点左右子树高度差，所以就不会出现上面的那种极端情况。对具体原理感兴趣的朋友可以查看这篇帖子：一文带你彻底读懂红黑树。

在这里我们通过可视化的展示，来感性地看看红黑树怎么解决自增长字段的索引问题的：

通过上面的动画演示，大家可以发现，当我们试图不断为节点增加右子节点时，红黑树会通过旋转操作，自动平衡节点左右子树的高度。这样一来，就解决了上述的在极端情况下，二叉树退化为链表的情况。

这样一来红黑树就完美了吗？其实不然，它也有缺陷，红黑树的本质还是二叉树的范畴，所以当表里面的数据比较多的时候，树的高度就比较大。比如表里有100万条数据，我们对ID做索引，则树的高度大约是20。（树高的计算方法：2^n=100w，其中的n就是树高），此时查询的效率就比较差了，因为大部分的数据在树的底层，一次查询从根节点逐层比对到目标节点，往往要经历十几次的比对，也就是十几次的磁盘IO操作，注意磁盘的IO操作是个很耗时的动作。极大的影响了查询的性能。

B树 / B+树

MySQL的索引支持两种数据结构，B+树便是其中的一种，也是最常用的。

由上面的二叉树的缺陷，我们比较容易想到，如果要控制树结构的查询效率（比如一次查询的磁盘IO次数控制5次以内），就必须要控制树的高度。当表记录总量不变的情况下，要控制树的高度，那就需要在一个节点存放更多的索引元素，这就是B树。

• 叶节点具有相同的深度，叶节点的指针为空
• 所有索引元素不重复
• 节点中的数据索引从左到右递增排列

B树已经能够较好的解决了上面的问题，但是这里我们不打算对B树做过多的讨论。因为精益求精的MySQL研发工程师对B树做了进一步优化，得到了B+树，这才是MySQL的索引结构。

• 叶子节点包含所有索引字段，并且是根据索引字段的值排好序的
• 非叶子节点不存储data，只存储索引（冗余），可以放更多的索引
• 叶子节点用指针链接，提高区间访问的性能

下面我们对B+树的上述三条性质做详细解释：
由于我们每个节点能够存放的数据容量是有限制的，这个容量限制默认的设置是16k，可以通过下面的语句查看：

SHOW GLOBAL STATUS like 'Innodb_page_size';

由于非叶子结点不存储data，就能存储更多的索引元素，每两个索引元素之间还存储着一个指向子节点的指针（占用的大小为6byte），该指针指向的子节点的所有索引元素≥指针左边的索引元素且<指针右边的索引元素。
现在回顾上面的例子，假设我们用bigint来存储ID字段，bigint占8byte，加上每个指针6byte，则一个ID索引元素占用的存储为14byte，则一个非叶子结点最大可以存储16kb/14b=1170条。
对于叶子节点，不存在指向下一级的指针，省去了6byte，但是里面要存储data，这个data根据不同的MySQL存储引擎，里面可能存放的是索引数据所在行的磁盘存储地址，也可能是索引所在行的其他字段合集。（关于存储引擎，下文会介绍。）这里先假设一个索引的data占1k，则一个叶子节点可以存储大约16个索引字段，在树高为三层的情况下，B+树的结构可以存放的索引总量为1170117016=21902400。现在来看B+树的结构确实很完美，三层的高度，就能容纳千万级的数据索引。同时也可以看到每个节点的默认大小为16k也是非常合适的。

叶子节点之间用指针链接的好处在于，当我们进行区间查找时，效率会大大提高，比如我们要执行如下语句

select * from t where id>15 and id<30;

MySQL会从根节点开始查询，查询到第一个节点，找到满足条件的’ID=18‘的记录，再通过指针跳到第二个节点，继续查找，找到满足条件的’id=20‘的记录。试想如果叶子节点之间没有通过指针相连，那么就要回到上一级的父节点甚至是根节点去继续查找。

下面我们可视化的看下B+树创建索引的过程：

我们再来根据B+树建立的索引来查找第六行记录：

select * from t where col1=6;

此时会用6来与根节点比较，注意根节点的元素往往是预先加载到内存里面的，经过比较，发现6比根节点所有的元素都大，则直接跳转去它的最后一个子节点，即把第三个子节点的数据加载到内存进行比较，可以很快定位到对应的数据。（这里大家要注意，任何的索引结构形式，都不可能预先把所有索引数据都加载到内存中的）。

上面的例子比较简单，表数据比较少，但是道理是一样的，即使表的数据达到千万级，使用B+树的索引结构，仍然可以把树高控制在3-5层，所以至多只需要4-5次的io操作即可检索到所求的记录。

Hash表

MySQL的索引支持两种数据结构，Hash便是其中的一种，在一些特殊的场景有其独特优势。

Hash（散列、杂凑）函数: 是将任意长度的数据映射到有限长度的域上。直观解释起来，就是对一串数据m进行杂糅，输出另一段固定长度的数据h，作为这段数据的特征（指纹）。
也就是说，无论数据块m有多大，其输出值h为固定长度。比如我们常用的MD5，SHA等都是Hash函数。

哈希表是根据设定的哈希函数H（key）和处理冲突方法将一组关键字映射到一个有限的地址区间上，并以关键字在地址区间中的象作为记录在表中的存储位置，这种表称为哈希表或散列，所得存储位置称为哈希地址或散列地址。作为线性数据结构与表格和队列等相比，哈希表无疑是查找速度比较快的一种。

当我们对表字段建立Hash结构的索引时，MySQL会对字段的值做Hash运算，把得到的散列值连同该行记录磁盘地址存到hash映射表：

Hash索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位，不像B-Tree索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以Hash索引的查询效率要远高于B-Tree索引。

但是Hash索引也有其缺陷：

• Hash索引仅仅能满足"=","IN"和"<=>"查询，不能使用范围查询。
• Hash索引无法被用来避免数据的排序操作。
  由于Hash索引中存放的是经过Hash计算之后的Hash值，而且Hash值的大小关系并不一定和 Hash运算前的键值完全一样，所以数据库无法利用索引的数据来避免任何排序运算;
• Hash索引不能利用部分索引键查询
  对于组合索引，Hash索引在计算Hash值的时候是组合索引键合并后再一起计算Hash值，而不是单独计算Hash值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash索引也无法被利用。
• Hash索引在任何时候都不能避免表扫描
  Hash索引是将索引键通过Hash运算之后，将 Hash运算结果的Hash值和所对应的行指针信息存放于一个Hash表中，由于不同索引键存在相同Hash值，所以即使取满足某个Hash键值的数据的记录条数，也无法从Hash索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。
• Hash索引遇到大量Hash值相等的情况后性能并不一定就会比BTree索引高
  对于选择性比较低的索引键，如果创建Hash索引，那么将会存在大量记录指针信息存于同一个Hash值相关联。这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下。

存储引擎

MySQL数据库里面的数据最终是以文件的形式存放在磁盘上，就和我们磁盘上的其他文件一样，不管是word文件还是文本文件，都需要一种存储方式。这就需要存储引擎，它的功能就是按照一定的规则在磁盘上组织文件。

MySQL支持多种存储引擎，其中MyISAM和InnoDB是最常见的两种。

这里通过建立两张表举例，一张表名叫teacher，使用MyISAM存储引擎；一张表名叫student，使用InnoDB存储引擎；我们可以进入到mysql安装目录下，去看下这两张表对应的文件：

# ls -l
total 144
-rw-rw---- 1 mysql mysql     65 Jan 21 02:27 db.opt
-rw-rw---- 1 mysql mysql   8586 Jan 21 05:54 student.frm
-rw-rw---- 1 mysql mysql 114688 Jan 21 05:54 student.ibd
-rw-rw---- 1 mysql mysql      0 Jan 22 01:38 teacher.MYD
-rw-rw---- 1 mysql mysql   1024 Jan 22 01:38 teacher.MYI
-rw-rw---- 1 mysql mysql   8586 Jan 22 01:38 teacher.frm

可以看到：

• 使用MyISAM存储引擎的表在磁盘上生成了三个文件：teacher.frm，teacher.MYI，teacher.MYD；
• 使用InnoDB存储引擎的表在磁盘上生成了两个文件：student.frm，student.ibd；

MyISAM

• .frm ： 是frame的缩写，意为“框架、结构”，这个文件存储表的结构定义；
• .MYI ： 是MyISAM Index的缩写，这个文件存储表的索引数据；
• .MYD ：是MyISAM Data的缩写，这个文件存储表里面的内容数据；

使用MyISAM作存储引擎，索引文件和数据文件是分离的，所以这种索引也叫做非聚集索引。

非聚集索引的叶子节点里面的data存放的是行记录的磁盘存储地址，这样索引数据比较轻量，但根据索引查询时，并不能直接得到结果，需要根据索引得到的记录地址，去额外进行一次IO操作。

InnoDB

• .frm ： 是frame的缩写，意为“框架、结构”，这个文件存储表的结构定义；
• .ibd ： 是InnoDB Data的缩写，这个文件存储表的索引和数据；

InnoDB表有如下几个性质：

• InnoDB表必须有主键，并且推荐使用整型的自增主键
• 表数据文件本身就是按B+树组织的一个索引结构文件
• 聚集索引-叶节点包含了完整的数据记录
• 辅助索引结构叶子节点存储的是主键值

为什么InnoDB表必须有主键？ 有人可能会说：“我在建表的时候，没有指定主键，照样创建成功了啊”。你可能不知道，如果没手动建主键 ，mysql会找一列唯一数据的列当做主键，或者加一列主键（mysql自动加的主键列是你看不到的）。并以此主键字段将表数据按照B+树组织起来：

为什么要整型自增？ 不妨假设用32位的UUID作为主键，我们来看看效果：

• B+树里做查询时，在节点里面的元素有大小的比较，用字符串比较是比较慢的，字符串的比较是先转换为ACSII码，然后根据ACSII码的排序去比较大小。用整型就不一样了，数字的比较是很快的，同时整型占用字节数也少。
  为什么要自增
• B+树里做插入时，由于UUID是随机生成的，所以新生成的UUID往往不是最大的，所以不是追加到尾部，而很可能要插入中间的某个叶子节点，那么可能这个叶子节点已经存储满，这时就需要后面的叶子节点一起变动，这是有较大的性能开销的。我们通过可视化工具演示下，当插入的主键不是自增时发生的情况。假设主键的值已经有：1、2、3、4、5、6、7、9、10，然后插入新的主键值：8，看看会发生什么：

上面的动画可以看到，新增的主键值8，按照大小排序的规则，插入了最后一个叶子节点的第二个位置，由于达到了该叶子节点的存储上限，则B+树根据内部的优化规则，进行了树的重构，不仅叶子节点的布局发生了变化，树的高度也发生了变化，这是很耗性能的。

索引和数据是在一个文件中组织的，所以这种索引也叫做聚集索引。上面讨论的主键索引就是聚集索引。
由于聚集索引只在一个ibd文件中操作，所以效率更高。

辅助索引（Secondary Index）也叫 二级索引 或 非主键索引 ，它跟主键索引很相似，唯一的不同就是叶子节点的data部分存储的不是该行的记录值，而是对应的主键值。

辅助索引的叶子节点这么设计有两点好处：

• 节省存储空间，表里面的数据只需要存一份在主键索引里即可；
• 便于数据一致性的维护，当表数据有变动时，只要变动主键索引里面的即可；

辅助索引的缺点也很明显：

• 需要先根据辅助索引找到对应主键值，再根据主键值去主键索引里面去检索。

InnoDB对Hash的支持

由上面的Hash索引结构，我们知道，Hash表里面的值存放的是行记录对应的磁盘存储地址，所以它的索引文件和数据文件是分开的。而InnoDB存储引擎的设计，是将索引和数据存放在同一个文件中。所以使用InnoDB作为存储引擎时，我们是无法创建Hash结构的索引的，此时只能用B+树；

但是我们上面有说了，对于某些特殊的场景，Hash的性能是优于B+树的，鱼和熊掌就不可兼得么？
其实不然，mysql的InnoDB存储引擎是支持Hash索引的，不过它的Hash索引是自适应的，就是说InnoDB会根据表的使用情况自动为表生成Hash索引，这个过程是不能被认为干预的。

联合索引

未完待续。。。