一、介绍

索引是帮助mysql高效获取数据的排好序的数据结构。

二、索引数据结构

二叉树、红黑树、hash表、B-Tree

ps：后面所有示例均以以下图片数据表结构为例子作讨论。

场景一：无索引，如果要查找col2=89的记录，那么需要每行数据去查找，也就是需要查询6次才可以。

二-1、二叉树

特点：二叉树左边的节点数据比上一级小，右边的节点数据大于等于上一级。

缺点：当数据量大的时候，仍然需要查询很多层才能查询出数据。

场景二：用col1做二叉树索引，则如下图：

场景三、用col2做二叉树索引，则如下图：

说明：如上图，建立二叉树索引后，只需要查询2次即可查出col2=89的数据。     

二-2、红黑树

特点：在二叉树的基础上自动平衡

场景四、如用id做红黑树索引如下图：

说明：结构会自动平衡，不会像场景二一样，一条直线结构。

二-3、B+Tree（B-Tree的变种）

特点：

1、数据从左到右递增。

2、非最底层节点不存储data，只存储索引（冗余），可以存放更多索引。

3、最底层节点包含所有索引字段。

4、最底层节点用双向指针连接，提高区间访问的性能。

5、B+Tree相对比B-Tree：添加指针，把data从非最底层节点挪到最底层节点。

场景五、以下是一个用int整型做B+Tree索引的B+Tree结构示例。已知mysql内定限制每个节点最大占用内存是16kb。假设每个索引占用8b内存，黄色涂鸦部分占用6b内存，最底层每个索引包括data占用1kb，那么最多可以存储多少个索引？

解答：

第一层节点索引数量=16kb/(8b+6b)=1170个，那么同理，

第二层每个节点都有1170个索引，而第一层共有1170个索引，所有第二层所有索引数量=1170*1170

第三层每个索引占用1Kb，mysql内定限制每个节点占用16kb，所有第三层每个节点有16个所有，而第二层索引数量是1170*1170，所以第三层所有索引数量=1170*1170*16，大概是两千万个索引。

说明：

1、索引从左到右递增，如15、56、77

2、第二层节点索引数据是15、20、49，但是这几个索引在第三层也出现，那么在第二层出现则是索引冗余，用来构建B+Tree结构。

3、最底层节点包含所有索引字段，且包含data（其他字段信息）

4、图中黄色涂鸦部分是保存下级节点位置信息占用的内存，实际上最底层指针两端也有隐藏的保存左右节点位置信息占用的内存

5、蓝色指针为隐藏的指针，即最底层指针是双向的，这样才可以方便的查询出左右两边的节点信息。

PS：如查找id=30的记录流程如下：首先在第一层节点查询，核对30在15-56区间后会根据15-56的黄色位置查找子节点的磁盘位置；在第二层节点查询，核对30在20-49区间后会根据20-49的黄色位置查找第三层磁盘位置；在第三层根据RAM算法自动查找30所在的磁盘位置。（使用RAM算法的好处：不占用磁盘I/O，耗能低）

二-4、hash表索引

特点：通过hash算法操作索引

缺点：只能精准定位到某条信息，无法快速查询范围值。

场景六、如id=7做hash索引，即hash（7）=val1，val1可以快速定位id=7的数据所在的磁盘位置；比如需要查找id>3的数据所在磁盘信息则无法查找，因为只能通过hash算法查找出id=3的数据所在的磁盘信息。

三、联合索引        

特点：使用多个字段作为联合索引，同样遵循B+Tree从左到右递增的数据结构。

场景七、以下是一个以id、员工、日期三个字段作为联合索引的B+Tree数据结构图，

查询sql是select* from table where 员工=‘Engineer’能否正常使用索引查询出结果呢？

 解答：不能。首先知道B+Tree数据结构是从左到右递增的，比如上图：10001-10003-10004，10001节点的第二个字段是A-E-S，那么如果查询条件不把id作为条件的话，10001-10003-10004这个排序即相当于失去了意义，后面也可能存在10005，而10005节点的第二个字段也可能是Engineer（如下图），那么数据结构即不遵从从左到右递增的规则，所以无法使用索引查出数据。

场景八、使用name、age、position作为联合索引，只有最后一条sql才能使用索引查询，前面两条sql不能使用索引查询。

四、MyIsm引擎的数据表

四-1、MyIsam数据表在磁盘中的保存格式

四-2、MyIsam数据表索引过程详解

比如查询col=30的数据：

第一步：先判断col是否是索引字段

第二步：去索引文件按照B+Tree结构从根节点快速查找，定位到15-56区间

第三步：再在第二层节点定位到20-49区间

第四步：再在最底层对比获取30的data信息，即0XF3

第五步：用0XF3去MYD文件获取信息

五、Innodb引擎的数据表

五-1、Innodb数据表在磁盘中的保存格式

问题一：为什么Innodb必须要有主键，而myIsam不需要？

答：因为Innodb本身数据以B+Tree结构保存，如果没有主键无法建立B+Tree数据结构；而myIsam即便没有主键，构建B+Tree的时候系统会自动把所有字段拿出来判断，把数据是唯一的字段去做B+Tree，如果所有字段都不唯一，那么系统将用系统自动为每行数据生成的唯一标识去做B+Tree

问题二：为什么推荐整型自增主键？

答：因为整型在B+Tree对比的时候比字符串快，占用空间小；自增原因：B+Tree遵循从左到右递增原则，如果是自增的话，每次增加数据的时候直接在右边增加就可以了，如果不是自增的话，有可能导致B+Tree再增加子节点。